안 쓰던 블로그

[두부모판 자르기](backtracking 기법)KOI 두부 공장에서 만들어내는 크기가 n*n(n은 11이하의 자연수)인 두부 모판이 있다.이 모판을 1*1크기의 단위두부가 2개 붙어있는 형태의 포장단위 (즉, 1*2 혹은 2*1크기)로 잘라서 판매한다.그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 잘려진포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 다음과 같이 정해진다. A B C F A 100 70 40 0 B 70 50 30 0 C 40 30 20 0 F 0 0 0 0 포장 단위에 있는 두 단위두부가 [A, A]급이면 100원을 받고, [A, B]급이면 70원을 받는 식이다.F급이 하나라도 있으면 한 푼도 받을 수 없다.두..

7차시 동적테이블의 응용2 [색상환 문제] N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003으로 나눈 나머지 출력 빨간색부터 시작하면 인접한 연지, 주황을 선택 못하게 되니 빨강-> 다홍부터 시작하고 빨간색이 아니라면 주황색부터 하면 됨 탐색함수solve(a, b)=현재 a번 색상에 대해 고려하는 상태이며, 지금까지 규칙에 맞도록 b개의 색깔을 이미 선택한 상태 -> X빨간색을 선택하면 나오는 문제를 인식할 수 없음 solve(a, b)=현재 a번 색상에 대해 고려하는 상태이며, 지금까지 규칙에 맞도록 b개의 색깔을 이미 선택했고, c가 참이면 마지막색을 고를 수 없는 상태 1234567891011121314151617181920212..

1차시 관계기반 알고리즘 설계정보/과학 분야의 수학적 귀납법은 문제 증명이 아닌, 문제 해결의 방법으로 쓰이고 있다.수학의 수학적 귀납법-1. P(1)이 성립함을 보인다.2. P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. 정보/과학 분야의 수학적 귀납법-1. 입력값이 n인 문제의 해를 f(n)으로 정의한다. (이 부분이 다르다)2. f(1)을 직접 구하여 출력한다.3. f(k)를 이미 구해두었다고 가정하고 f(k)를 통해 f(n)을 구하여 출력한다. 2차시 재귀함수의 설계[숫자 뒤집기]방법1. solve(n)을 이용한 재귀호출을 이용1. n을 입력받고2. n%10 출력, solve(n/10) 호출3. n이 0이 아니면 반복 12345int solve(int n){ if(n==0) retu..

123456789101112131415161718192021222324252627282930313233343536373839404142434445#include int n, m[3000][3000], res[3]; void solve(int x, int y, int size) { int paper = m[y][x]; int same = true; for (int i = y; (i

12345678910111213141516171819202122232425262728293031323334353637#include int n, q[64][64]; void tree(int x, int y, int size) { int pic = q[y][x]; int same = true; for (int i = y; (i

12345678910111213141516#include #define NM 1000int n, dp[NM+1]; int f(int a /*i*/) { if (a == 0 || a == 1) return 1; if (a

12345678910111213141516#include #define NM 1000int n, dp[NM+1]; int f(int a /*i*/) { if (a == 0 || a == 1) return 1; if (a