타일 채우기
-
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p149)알고리즘 2017. 2. 2. 12:22
이 문제는 앞선 포스트에서도 재귀적 방법으로 풀어 본적이 있는 문제이다. 그러나 숫자가 커짐에 따라 기하급수적으로 계산량이 늘어날 수 있으므로, 여기서는 가장 효율적인 방법으로 접근해 보려고 한다. 책에서도 점화식을 n, n-1, n-2 사이의 관계와 n과 n/2사이의 관계를 설명하고 있다. 지금까지 문제 풀이 방법으로 보았을때, 상향식 동적 계획법 (Dynamic Programming)이 가장 빠른 접근 방법이나 책에서는 보여주지 않고 있다. 따라서 이 방법을 풀이해 보고자 한다. 중요한 것은 점화식을 유도해 내는 과정을 잘 이해하는 것이라고 생각된다. 1) n이 짝수이면, 절반씩 나눠 채우는 방법과 1칸씩을 내어논 상태에서 채운 다음 2칸을 채울 수 있는 2가지 방법을 곱한다. 2) n이 홀수이면, ..
-
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p35)알고리즘 2016. 9. 16. 19:13
이 문제에서 익혀야 할 핵심은 점화식을 만들때, n번째 항과 n-1번째 항과의 관계식을 구하는 것이 아니라, n번째 항과 n/2번째 항과의 관계를 구하는 방법이다. 이를 통해 굉장히 효율적인 점화식을 만들 수 있기 때문이다. 특히 n이 홀수일 때와 n이 짝수일 때를 점화식을 유도하는 방법을 잘 익히는 것이 필요해 보인다. import java.util.Scanner; public class FillTilesSol45 { public static int n; public static int m; public static long f(int k) { if (k0) return (f(k/2)*f(k/2+1)+2*f(k/2)*f(k/2-1))%m; // k가 짝수일 때 else return (f(k/2)*f(k..