#fill tiles
-
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p149)알고리즘 2017. 2. 2. 12:22
이 문제는 앞선 포스트에서도 재귀적 방법으로 풀어 본적이 있는 문제이다. 그러나 숫자가 커짐에 따라 기하급수적으로 계산량이 늘어날 수 있으므로, 여기서는 가장 효율적인 방법으로 접근해 보려고 한다. 책에서도 점화식을 n, n-1, n-2 사이의 관계와 n과 n/2사이의 관계를 설명하고 있다. 지금까지 문제 풀이 방법으로 보았을때, 상향식 동적 계획법 (Dynamic Programming)이 가장 빠른 접근 방법이나 책에서는 보여주지 않고 있다. 따라서 이 방법을 풀이해 보고자 한다. 중요한 것은 점화식을 유도해 내는 과정을 잘 이해하는 것이라고 생각된다. 1) n이 짝수이면, 절반씩 나눠 채우는 방법과 1칸씩을 내어논 상태에서 채운 다음 2칸을 채울 수 있는 2가지 방법을 곱한다. 2) n이 홀수이면, ..