어떤 수열의 길이 n에서 만들 수 있는 수열의 가지 수가 f(n)가지라고 가정해보자.
모든 0보다 큰 n에 대해 f(n)=f(n−1)+f(n−2)이다.
길이가 n−1인 수열에는 1을 추가해서 길이가 n인 수열을 만들 수 있고
길이가 n−2인 수열에는 00을 추가해서 길이가 n인 수열을 만들 수 있다.
11도 추가할 수 있다고 생각할 수 있지만 해당 경우는 n−1에 포함된 경우이므로 제외해야 한다.
길이가 n−3인 수열부터는 n−1,n−2에 포함되는 경우들이므로 포함하지 않는다.
점화식을 구했으니 기저 사례를 확인해보자. ( 점화식을 먼저 구하든, 기저 사례를 먼저 구하든 순서는 상관 없다. )
기저 사례는 당연히 n=1,n=2인 경우 두가지다.
각각 1가지, 2가지의 수열을 가진다.
코드
이 풀이를 실제로 구현할 때 2가지 방식:Top-Down/Bottom-Up이 있다.
반드시 이것을 써야 한다 강제되는 경우는 거의 없고 문제를 풀 때 마다 유동적으로 선택하면 된다.
1. Top-Down 방식
Top-Down 방식은 가장 큰 문제를 분해하는 과정을 직접 거치는 방식을 뜻한다.
호출 트리를 떠올리면 가장 위에서 아래로 내려가며 주어진 부분 문제들을 해결하고 다시 호출한 부모로 리턴하는 식이기 때문에 Top-Down 방식으로 불린다.
재귀 호출로 구현하며, 코드를 작성할 때 비교적 직관적으로 작성할 수 있다는 장점이 있다.
단점은, 함수 호출을 많이 사용하는 만큼 호출 계층 제한 때문에 N이 큰 경우나 탐색이 깊이 들어가는 입력 케이스가 있으면 사용하기 애매하다. 또한 함수 호출 자체가 일반적인 반복문 보다는 비용이 크기 때문에 속도면에서 아주 살짝 불리하다.
Top-Down 방식 코드 구현
#include <iostream>#include <vector>using namespace std;const int mod = 15746;vector<int> dp;int r(int n) { if(dp[n] != -1) return dp[n]; // 메모이제이션 if(n == 1) return dp[n] = 1; // 기저 사례 확인 if(n == 2) return dp[n] = 2; // 기저 사례 확인 return dp[n] = (r(n - 1) + r(n - 2)) % mod; // 문제를 n - 1 과 n - 2로 분리}int main() { int n; cin >> n; dp = vector<int>(n + 1, -1); cout << r(n); return 0;}
가장 큰 문제인 r(n) 에서 시작해 재귀적으로 r(n - 1) 와 r(n - 2)를 호출하며 문제를 분리하고 다시 합치는 과정을 볼 수 있다.
2. Bottom-Up 방식
Bottom-Up 방식은 문제 분리 과정을 생략하고 처음부터 기저 사례에서 시작해 부분 문제들을 조립해가며 답을 구하는 방식을 뜻한다. 재귀 호출에서 봤던 트리 구조의 호출구조가 아닌 기저 사례부터 조립해 올라가 최종 답을 구하는 방식이기 때문에 Bottom-Up 방식으로 불린다. 반복문으로 구현하며, 코드가 간결하다는 장점이 있다.
단점은, 코드가 직관적이지 않기 때문에 점화식을 모르면 코드 이해가 비교적 어렵다.
지금 문제는 사실 인자가 1개 밖에 없기 때문에 비슷해보이지만 나중에 인자가 많은 문제들을 Bottom-Up 방식으로 구현할 경우 모르는 사람이 봤을 때 이해하기 쉽지 않다.
풀이 자체도 Bottom-Up 방식으로 떠올리는 쪽이 더 어렵다.
만약 두 방식 모두 사용 가능한 문제를 푼다면 Top-Down 방식으로 구현하는게 더 쉬울 확률이 높다.