소개
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작고 단순한 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 방법은 중복되는 계산을 줄이고 효율적으로 최적해를 찾는데 사용됩니다. 동적 계획법은 최적화 문제, 그래프 알고리즘, 문자열 처리 등 다양한 분야에서 활용되며, 특히 최단 경로 찾기, 배낭 문제, 시퀀스 정렬 등의 문제 해결에 효과적입니다. 이 기법은 복잡한 문제를 체계적이고 효율적으로 해결할 수 있게 해주어, 알고리즘 설계와 최적화에 있어 중요한 도구로 자리잡고 있습니다.
알고리즘 개념 설명
동적 계획법의 핵심 아이디어는 문제를 여러 개의 하위 문제로 나누고, 이들의 해결책을 저장해 재사용함으로써 전체 문제의 해를 효율적으로 찾는 것입니다. 이 방법은 두 가지 중요한 특성을 가진 문제에 적용됩니다:
1.
최적 부분 구조(Optimal Substructure): 문제의 최적해가 하위 문제의 최적해로부터 구성될 수 있는 특성
2.
중복되는 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 반복되는 특성
동적 계획법의 작동 원리는 다음과 같습니다:
1.
문제를 하위 문제로 분할합니다.
2.
가장 작은 하위 문제부터 해결하기 시작합니다.
3.
하위 문제의 해를 저장합니다(메모이제이션).
4.
저장된 결과를 이용해 상위 문제를 해결합니다.
5.
최종적으로 원래 문제의 해를 구합니다.
예를 들어, 피보나치 수열을 구하는 문제를 살펴보겠습니다. n번째 피보나치 수는 F(n) = F(n-1) + F(n-2)로 정의됩니다. 이 문제는 작은 하위 문제(F(n-1), F(n-2))의 해를 이용해 큰 문제(F(n))를 해결할 수 있으며, 동일한 하위 문제(예: F(5))가 여러 번 계산될 수 있습니다. 동적 계획법을 사용하면 각 하위 문제의 결과를 저장하고 재사용하여 중복 계산을 피할 수 있습니다.
의사코드 (pseudo-code)
피보나치 수열을 구하는 동적 계획법 알고리즘의 의사코드는 다음과 같습니다:
function fibonacci(n):
if n <= 1:
return n
// 결과를 저장할 배열 초기화
dp = array of size (n+1)
dp[0] = 0
dp[1] = 1
// 반복적으로 하위 문제 해결
for i from 2 to n:
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Plain Text
복사
이 의사코드에서 dp 배열은 각 하위 문제의 결과를 저장하는 메모이제이션 기법을 구현합니다. 이를 통해 중복 계산을 피하고 효율적으로 n번째 피보나치 수를 계산할 수 있습니다.
간단한 구현 예시
다음은 C++로 구현한 피보나치 수열을 구하는 동적 계획법 알고리즘입니다:
#include <vector>
class Solution {
public:
int fibonacci(int n) {
if (n <= 1) return n;
// 결과를 저장할 벡터 초기화
std::vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
// 반복적으로 하위 문제 해결
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
C++
복사
이 구현에서는 std::vector를 사용하여 동적으로 메모리를 할당하고 각 하위 문제의 결과를 저장합니다. 반복문을 통해 작은 하위 문제부터 차례로 해결하며, 최종적으로 n번째 피보나치 수를 반환합니다.
시간 복잡도 및 공간 복잡도 분석
동적 계획법을 사용한 피보나치 수열 알고리즘의 복잡도는 다음과 같습니다:
•
시간 복잡도: O(n)
◦
각 하위 문제를 한 번씩만 계산하므로, n개의 하위 문제에 대해 상수 시간 연산을 수행합니다.
•
공간 복잡도: O(n)
◦
n+1 크기의 배열을 사용하여 각 하위 문제의 결과를 저장합니다.
이는 재귀적 접근법(시간 복잡도 O(2^n))에 비해 매우 효율적입니다. 최선, 평균, 최악의 경우 모두 동일한 복잡도를 가집니다. 이 알고리즘은 입력 크기에 비례하여 선형적으로 증가하는 시간과 공간을 사용합니다.
결론
동적 계획법은 복잡한 문제를 효율적으로 해결할 수 있는 강력한 알고리즘 기법입니다. 중복 계산을 피하고 최적 부분 구조를 활용하여 시간 복잡도를 크게 개선할 수 있습니다. 그러나 메모리 사용량이 증가할 수 있다는 단점이 있습니다.
