오늘 푼 문제는 동적 계획법을 다루는 문제였다. 개념에 대해 다시 한 번 정리해보고자 한다.
다이나믹 프로그래밍은, 시간 복잡도는 줄여주지만 공간 복잡도는 클 수 있다.
동적 계획법은 복잡한 문제를 작은 하위 문제들로 나누고, 그 결과를 저장하여(메모이제이션) 중복 계산을 줄이는 최적화 기법이다. 주로 최적화 문제(최대값, 최소값)와 결정 문제(가능 여부)를 해결하는 데 사용된다.
핵심 개념
작은 문제로 분할 (Divide and Conquer):
문제를 더 작은 하위 문제로 나누고, 이 하위 문제들을 해결한다.
하위 문제들이 서로 겹친다면 중복 계산을 피할 수 있다.
중복 계산 방지 (Memoization):
한 번 계산한 결과를 저장해두고, 같은 하위 문제가 나올 때 다시 계산하지 않고 저장된 값을 사용합니다.
메모이제이션(Top-Down) 또는 테이블화(Bottom-Up) 방식으로 구현된다.
최적 부분 구조 (Optimal Substructure):
문제의 최적해가 하위 문제들의 최적해로 구성될 수 있을 때 DP를 사용할 수 있다.
예: 최단 경로 문제에서 특정 경로의 최단 거리는 이전까지의 최단 경로의 연장선이다.
DP의 두 가지 접근 방법
메모이제이션 (Memoization, Top-Down 방식)
재귀를 사용하여 문제를 해결하며, 계산된 값을 저장한다.
코드가 더 직관적이지만, 스택 오버플로우의 위험이 있다.
int fib(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // 이미 계산된 값 사용
return memo[n] = fib(n-1, memo) + fib(n-2, memo); // 결과 저장
}테이블화 (Tabulation, Bottom-Up 방식)
작은 문제부터 차례대로 해결하며, 결과를 테이블에 저장한다.
메모리와 시간 효율이 더 좋은 경우가 많다.
int fib(int n) {
vector<int> dp(n+1, 0);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}DP를 적용하기 위한 조건
최적 부분 구조 (Optimal Substructure):
문제를 더 작은 하위 문제로 나눌 수 있어야 하며, 하위 문제의 결과를 결합해 원래 문제를 해결할 수 있어야 한다.
예: 최단 경로 문제, 최대 이익 문제
중복되는 하위 문제 (Overlapping Subproblems):
동일한 하위 문제가 여러 번 반복해서 나타나야 한다.
예: 피보나치 수열, Knapsack 문제
동적 계획법의 구현 과정
문제 정의:
최적화하려는 목표와 DP 배열(또는 메모이제이션 테이블)을 정의한다.
예: dp[i] = i번째까지의 최적 해답.
점화식(Recurrence Relation) 도출:
현재 상태를 이전 상태로 표현하는 점화식을 세운다.
예: 피보나치 수열에서 fib(n) = fib(n-1) + fib(n-2).
기저 조건(Base Case) 설정:
가장 작은 하위 문제의 결과를 직접 설정한다.
예: 피보나치 수열에서 fib(0) = 0, fib(1) = 1.
구현:
메모이제이션(Top-Down) 또는 테이블화(Bottom-Up) 방식 중 하나를 선택하여 구현한다.
