1. 동적 계획법의 개념 및 분할정복과의 차이
•
분할정복:
부분문제 간 상관관계가 없는 경우에 효과적.
(예: mergesort, quicksort)
•
피보나치 수열 등:
부분문제 결과가 여러 번 재사용됨(중복 계산 발생), 분할정복 비효율적
2. 피보나치 수열 계산
2.1 분할정복식(비효율)
cpp
CopyEdit
int fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
C++
복사
•
중복 계산 존재, 시간복잡도 O(2ⁿ)
2.2 메모이제이션(memoization, top-down)
cpp
CopyEdit
int memo[MAX]; // memo[i] = -1로 초기화
int fib(int n) {
if (n <= 1) return n;
if (memo[n] == -1)
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
C++
복사
•
중복 계산 제거, 각 값을 한 번만 계산
2.3 테이블 채우기(tabulation, bottom-up)
cpp
CopyEdit
int fib(int n) {
int dp[0..n];
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++
복사
•
작은 문제부터 큰 문제로 계산, 반복문 기반
3. Memoization vs Tabulation
Memoization | Tabulation | |
방식 | Top-down (재귀) | Bottom-up (반복) |
계산 | 큰 문제 → 작은 문제 | 작은 문제 → 큰 문제 |
저장 | 캐시에 필요할 때 저장 | 모든 값을 테이블에 저장 |
장점 | 코드 직관적, 구현 쉬움 | 실행 빠름, 메모리 절약 |
단점 | 재귀 오버헤드 있음 | 전체 문제를 다 계산함 |
4. 이항계수(Binomial Coefficient) 계산
4.1 재귀 관계식
(nk)={1if k=0 or k=n(n−1k−1)+(n−1k)if 0<k<n\binom{n}{k} =
\begin{cases}
1 & \text{if } k=0 \text{ or } k=n \\
\binom{n-1}{k-1} + \binom{n-1}{k} & \text{if } 0 < k < n
\end{cases}
(kn)={1(k−1n−1)+(kn−1)if k=0 or k=nif 0<k<n
4.2 분할정복(비효율)
cpp
CopyEdit
int bin(int n, int k) {
if (k==0 || n==k) return 1;
else return bin(n-1, k-1) + bin(n-1, k);
}
C++
복사
•
중복 계산 많음, 시간복잡도 O(2ⁿ) (k ≈ n/2)
4.3 동적계획법(DP) 알고리즘
•
2차원 배열 B[0..n][0..k] 채움
cpp
CopyEdit
int bin2(int n, int k) {
int B[0..n][0..k];
for (i=0; i<=n; i++)
for (j=0; j<=min(i,k); j++)
if (j==0 || j==i) B[i][j] = 1;
else B[i][j] = B[i-1][j-1] + B[i-1][j];
return B[n][k];
}
C++
복사
•
시간복잡도 Θ(nk)
5. 최단경로 (All-Pairs Shortest Paths) 문제
5.1 그래프와 경로
•
그래프: 정점(vertex), 간선(edge), 가중치(weight)
•
경로(path): 한 정점에서 다른 정점까지 이음선의 연속
•
단순 경로: 중복 없는 경로
•
길이: 경로 상의 weight 합
5.2 무작정(Brute-force) 알고리즘
•
모든 경로 탐색, 최단길이 선택
•
n개의 정점, (n–2)!개의 중간 경로
•
지수적 시간복잡도
6. 플로이드(Floyd) 최단경로 알고리즘
6.1 동적계획법 표현
•
인접행렬 W:
W[i][j] = (vi에서 vj로의 direct edge의 가중치, 없으면 ∞)
•
D(k)[i][j]:
{v₁,...,vₖ}만을 중간 정점으로 허용할 때, vi→vj의 최단경로 길이
6.2 점화식 (Recursive Property)
D(k)[i][j]=min(D(k−1)[i][j], D(k−1)[i][k]+D(k−1)[k][j])D^{(k)}[i][j] = \min \left( D^{(k-1)}[i][j],\ D^{(k-1)}[i][k] + D^{(k-1)}[k][j] \right)
D(k)[i][j]=min(D(k−1)[i][j], D(k−1)[i][k]+D(k−1)[k][j])
•
k=0일 때 D(0)[i][j]=W[i][j]
•
k=1부터 n까지 순차적으로 계산
6.3 알고리즘 (Pseudo code)
cpp
CopyEdit
void floyd(int n, const number W[][], number D[][]) {
D = W;
for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}
C++
복사
•
시간복잡도: Θ(n³)
7. 경로 추적 (Path Reconstruction)
•
배열 P[i][j]:
vi→vj의 최단경로에서 중간에 포함된 정점 중, 인덱스가 가장 큰 정점
없으면 0
cpp
CopyEdit
void floyd2(int n, const number W[][], number D[][], index P[][]) {
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
P[i][j] = 0;
D = W;
for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (D[i][k]+D[k][j] < D[i][j]) {
D[i][j] = D[i][k]+D[k][j];
P[i][j] = k;
}
}
C++
복사
•
최단경로 출력
cpp
CopyEdit
void path(index i, j) {
if (P[i][j] != 0) {
path(i, P[i][j]);
print P[i][j];
path(P[i][j], j);
}
}
C++
복사
8. 동적계획법 설계 절차
1.
재귀 관계식 설정
(작은 문제로 분할, 부분 해에서 전체 해 도출)
2.
상향식으로 배열 채움
(B[0][0] → B[n][k] 등)
3.
최종 결과 도출
(테이블 마지막 값에서 전체 문제 해석)
9. 최적의 원칙(Principle of Optimality)
•
정의:
문제의 최적해가, 그 부분문제의 최적해를 항상 포함하면 동적계획법 적용 가능
•
예시:
최단경로: vi→vj 경로의 임의의 vk가 전체 최적경로 위에 있다면, vi→vk와 vk→vj도 각각 최적이어야 한다.
•
적용 불가 예시:
Longest path(최장 경로) 등 일부 문제는 부분 최적해가 전체 최적에 포함되지 않아 DP 불가
Dynamic Programming#2
1. 동적계획법 설계 3단계
1.
재귀 관계식(recursive property) 설정
•
최적해가 되는 작은 하위문제들로 분할, 이들 간 재귀적 관계식 수립
2.
상향식 계산(tabulation)
•
작은 문제부터 차례로 해답 계산, 테이블(B[·][·] 등)에 저장하며 진행
3.
전체 문제의 해답 도출
•
테이블 마지막 값(B[n][k] 등)이 전체 최적해
2. 최적의 원칙 (Principle of Optimality)
•
정의:
전체 문제의 최적해가 부분 문제의 최적해를 항상 포함할 때, 해당 문제는 최적의 원칙이 적용됨
•
DP 적용 필요충분조건:
최적의 원칙이 반드시 성립해야 함
•
예시:
◦
최단경로 문제: 경로 내 임의 정점 vk에 대해, vi→vk, vk→vj 역시 각 구간의 최단경로여야 함
◦
부분문제로 분할 가능하고, 중복 계산이 존재해야 DP 효율적
•
적용 불가 예:
◦
최장경로(longest path) 문제: 전체 경로 내 부분 경로가 항상 최적인 게 아님(사이클 등)
3. 연쇄 행렬 곱셈 (Matrix-Chain Multiplication)
3.1 문제 정의
•
n개의 행렬 A₁, ..., Aₙ을 곱할 때
곱셈의 총 연산량(스칼라 곱셈 횟수)이 최소가 되도록 괄호(계산 순서)를 배치
•
행렬 Ai의 크기: d₍i–1₎ × dᵢ
→ 전체 행렬 곱: (d₀ × d₁), (d₁ × d₂), …, (dₙ₋₁ × dₙ)
3.2 연산량 분석
•
i × j 행렬과 j × k 행렬 곱: i × j × k 회 곱셈 필요
•
곱셈 순서(괄호 배치)에 따라 전체 연산 수가 달라짐
3.3 무작정(Brute-force) 방법
•
가능한 모든 곱셈 순서를 시도
•
순서 가지수 tₙ ≥ 2ⁿ⁻² = Θ(2ⁿ)
•
지수 시간복잡도 (실행 불가)
4. 동적계획법 설계 — 연쇄 행렬 곱셈
4.1 DP 테이블 및 점화식
•
M[i][j]:
Ai ~ Aj를 곱하는 최소 곱셈 횟수 (i ≤ j)
•
P[i][j]:
Ai~Aj에서 최적분할 위치(기점) k값 저장
•
점화식:M[i][j]=i≤k<jmin{M[i][k]+M[k+1][j]+di−1⋅dk⋅dj}
M[i][j]=mini≤k<j{M[i][k]+M[k+1][j]+di−1⋅dk⋅dj}M[i][j] = \min_{i \leq k < j} \{ M[i][k] + M[k+1][j] + d_{i-1} \cdot d_k \cdot d_j \}
(M[i][i] = 0, i=1,..,n)
•
풀이 순서:
◦
M[i][i]=0로 초기화
◦
구간 크기 2~n까지 대각선 순서로 채움(diagonal loop)
◦
P[i][j]는 최소값을 준 k값 저장
•
예시:
◦
(A₁A₂)A₃ vs. A₁(A₂A₃) 등
◦
괄호마다 곱셈 횟수 직접 계산
4.2 시간복잡도
•
삼중 루프: O(n³)
◦
diagonal(=길이-1): n–1
◦
i: n–diagonal
◦
k: 1 ~ (j–1)
•
각 구간/위치마다 비교(최소값 판단)
•
Θ(n³)
4.3 최적 곱셈 순서 복원
•
P[i][j]의 값 이용,
재귀적으로 분할 위치 k를 따라 괄호 구조 출력
cpp
CopyEdit
void order(index i, index j) {
if (i == j) print("A" + i);
else {
k = P[i][j];
print("(");
order(i, k);
order(k+1, j);
print(")");
}
}
C++
복사
•
실행 시간: Θ(n)
5. 최적 이진 검색 트리 (Optimal Binary Search Tree, OBST)
5.1 문제 정의
•
n개의 정렬된 키와 각 키의 검색확률 p₁, ..., pₙ이 주어질 때
평균 검색 비용이 최소가 되도록 이진검색트리 구성
5.2 평균 검색 비용
•
트리에서 키 kᵢ를 찾는데 걸리는 비교 횟수: depth(kᵢ)+1
•
평균 검색 시간:i=1∑npi⋅비교횟수(ki)
∑i=1npi⋅비교횟수(ki)\sum_{i=1}^{n} p_i \cdot \text{비교횟수}(k_i)
5.3 동적계획법 설계
•
A[i][j]:
Keyᵢ ~ Keyⱼ 부분집합의 최적 평균 검색시간
•
R[i][j]:
Keyᵢ ~ Keyⱼ에서 최적트리의 루트가 되는 키 인덱스
•
점화식:A[i][j]=i≤k≤jmin(A[i][k−1]+A[k+1][j]+m=i∑jpm)
A[i][j]=mini≤k≤j(A[i][k−1]+A[k+1][j]+∑m=ijpm)A[i][j] = \min_{i \leq k \leq j} \left( A[i][k-1] + A[k+1][j] + \sum_{m=i}^{j} p_m \right)
(A[i][i–1]=0, A[i][i]=p[i])
•
구간 크기(=diagonal) 1~n까지 대각선 순서로 채움
5.4 시간복잡도
•
삼중 루프(길이, 시작점, k값): Θ(n³)
5.5 트리 복원
•
R[i][j]의 값으로 트리 재귀 구축
cpp
CopyEdit
node_pointer tree(index i, index j) {
k = R[i][j];
if (k == 0) return NULL;
else {
p = new node;
p->key = Key[k];
p->left = tree(i, k-1);
p->right = tree(k+1, j);
return p;
}
}
C++
복사
6. 결론
•
DP는 최적의 원칙을 만족하는 문제(최단경로, 연쇄 행렬곱, OBST 등)에서 강력
•
연쇄 행렬곱, OBST 모두 Θ(n³)
•
DP 구조: 테이블 할당, 점화식, 대각선(구간 크기) 순으로 채움, 복원 배열(P, R 등) 통한 최적 구조 재귀적 복원
