동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 해결한 뒤, 그 결과를 저장해 두었다가 필요할 때 다시 사용(메모이제이션)하여 전체 문제의 해결 시간을 단축시키는 방법입니다. 이번 글에서는 피보나치 수열 계산에 동적 계획법을 적용해 보는 방법을 살펴보겠습니다.
메모이제이션(Memoization) 적용 예제
먼저, C++ 예제 코드에 메모이제이션 기법을 적용해 보겠습니다. 이를 위해 피보나치 수열의 계산 결과를 저장할 배열을 사용합니다. 이 배열은 각 피보나치 수를 인덱스로 하여 해당 값이 계산되었는지 여부와 계산된 값을 저장합니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <vector> // 메모이제이션을 위한 배열을 선언합니다. std::vector<int> memo; // 메모이제이션을 활용한 피보나치 수열을 계산하는 함수를 정의합니다. int fibonacci(int n) { // 이미 계산된 경우, 저장된 값을 반환합니다. if (memo[n] != -1) { return memo[n]; } // 계산이 필요한 경우, 재귀 호출을 통해 값을 계산합니다. if (n <= 1) { memo[n] = n; } else { memo[n] = fibonacci(n - 1) + fibonacci(n - 2); } return memo[n]; } int main() { int n; std::cout << "Enter a positive integer: "; std::cin >> n; // 메모이제이션 배열을 -1로 초기화합니다. memo.resize(n + 1, -1); // 사용자로부터 입력받은 n에 대한 피보나치 수를 계산하고 출력합니다. std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl; return 0; } |
이 코드에서 memo 배열은 처음에 모든 원소를 -1로 초기화하여, 아직 어떤 피보나치 수도 계산되지 않았음을 나타냅니다. fibonacci 함수는 n에 대한 피보나치 수를 계산할 때, 먼저 memo 배열에서 해당 값을 찾아보고, 이미 계산된 값이 있으면 바로 반환합니다. 그렇지 않은 경우에만 재귀 호출을 통해 값을 계산하고, 이를 memo 배열에 저장한 후 반환합니다.
동적 계획법에 관련된 추가 내용
동적 계획법을 적용할 때는 두 가지 주요 접근 방식이 있습니다: 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식입니다.
- 탑다운(Top-Down) 방식은 위 예제에서 본 것처럼, 재귀 호출을 사용하여 큰 문제에서 시작해 작은 하위 문제로 나아가는 방식입니다. 이 과정에서 메모이제이션을 사용하여 중복 계산을 방지합니다.
- 바텀업(Bottom-Up) 방식은 가장 작은 하위 문제들부터 시작하여 점차 큰 문제로 나아가며 해를 구하는 방식입니다. 이 방식에서는 일반적으로 반복문을 사용하며, 이전에 계산된 하위 문제의 결과를 활용하여 다음 문제를 해결합니다.
동적 계획법의 핵심은 문제를 분할하여 접근하는 동시에, 이미 해결한 하위 문제의 해를 재활용함으로써 전체적인 계산 효율을 높이는 것입니다. 이는 피보나치 수열 뿐만 아니라 다양한 최적화 문제에 널리 적용될 수 있는 강력한 기법입니다.
