이 글에서는 정수 n이 주어졌을 때 n번째 펠 수(Pell Number)인 Pn을 구하는 방법을 살펴보겠습니다. 펠 수는 다음 점화식으로 정의되는 수열의 항입니다.
Pn = 2 × Pn-1 + Pn-2
수열의 첫 두 항은 각각 P0 = 0, P1 = 1이며, 따라서 펠 수열은 0, 1, 2, 5, 12, 29, 70, ... 순으로 진행됩니다.
해결 접근 방법
이 문제는 크게 두 가지 방식으로 풀 수 있습니다. 하나는 재귀(Recursion)를 이용하는 방법이고, 다른 하나는 반복문(Iteration)을 이용하는 방법입니다.
재귀적 접근
재귀 방식에서는 펠 수의 점화식을 함수에 그대로 적용합니다. 즉, pell(n)을 구하기 위해 pell(n-1)과 pell(n-2)를 재귀적으로 호출하고, n이 2 이하가 되면 기저 사례(base case)로 처리합니다.
#include <iostream>
using namespace std;
int pell(int n) {
if(n <= 2)
return n;
return 2*pell(n-1) + pell(n-2);
}
int main() {
int n = 6; // 주어진 n
cout << pell(n) <<"\n"; // 해당 위치의 펠 수
return 0;
}실행 결과
70
코드 설명
위 코드는 n이 2 이하가 될 때까지 pell(n-1)과 pell(n-2)를 계속 호출하는 순수 재귀 방식입니다. n ≤ 2일 때는 해당 값 자체가 펠 수와 일치하므로(P0 = 0, P1 = 1, P2 = 2) 그대로 반환하면 됩니다. 다만 이 단순 재귀 구조는 같은 값을 중복 계산하기 때문에 시간 복잡도가 지수적으로 증가하여 약 O(2N)에 달합니다. 메모이제이션(memoization)을 적용하면 O(N)까지 개선할 수 있습니다.
반복문 접근
반복문 방식은 동일한 점화식을 사용하지만, 재귀 함수 대신 for 반복문으로 차례대로 값을 계산합니다. 이전 두 항만 저장해두면 되므로 공간 복잡도도 O(1)로 매우 효율적입니다.
#include <iostream>
using namespace std;
int main() {
int n = 6; // 주어진 n
int p0 = 0; // pn-2의 초기값
int p1 = 1; // pn-1의 초기값
int pn; // 최종 답
if(n <= 2) // n이 2 이하이면 n을 그대로 출력
cout << n <<"\n";
else {
for(int i = 2; i <= n; i++) { // 두 번째 항부터 n까지 계산
pn = 2*p1 + p0;
p0 = p1; // 새로운 i에서 pn-1이 pn-2가 됨
p1 = pn; // 새로운 i에서 pn이 pn-1이 됨
}
cout << pn << "\n";
}
return 0;
}실행 결과
70
코드 설명
이 프로그램은 2부터 n까지 반복하면서 매 단계마다 새로운 값 pn을 계산하고, 이전 두 변수(p0, p1)를 한 칸씩 밀어 업데이트합니다. 모든 반복이 끝나면 pn에 n번째 펠 수가 저장됩니다. 시간 복잡도는 O(N), 공간 복잡도는 O(1)로, 단순 재귀 방식보다 훨씬 효율적입니다.
마무리
이 글에서는 재귀와 반복문 두 가지 방법으로 n번째 펠 수를 구하는 문제를 해결했습니다. 단순 재귀는 직관적이지만 중복 계산으로 인해 비효율적일 수 있으므로, 실제 구현에서는 반복문 방식이나 메모이제이션을 활용하는 것이 좋습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다.