- Divide and Conquer의 한계: 분할 정복은 서로 독립적인 하위 문제를 나눌 때 효과적임. BUT 피보나치 수열처럼 같은 하위문제를 반복적으로 푸는 문제에서는 비효율적
ex. F(5) = F(4) + F(3) → F(3) 이 여러번 계산됨 → 중복 계산이 심함 → 비효율적
2. Dynamic Programming의 개념
- Bottom-up 방식으로 작은 문제부터 해결해서 결과를 배열에 저장해두고 필요할 때 재사용함.
- 이로 인해 중복 계산을 제거하고 성능을 대폭 향상시킴
두 단계 구조
재귀적 성질 (recursive property) 정립
작은 문제부터 순차적으로 (bottom-up) 해결
3. 이항계수 (Binomial Coefficient) 예제
직접 계산은 매우 비효율적재귀적 정의
이항계수 - Divide and Conquer 방식
int bin(int n, int k) {
if (k == 0 || n == k)
return 1;
else
return bin(n-1, k-1) + bin(n-1, k);
}
문제점: 동일한 값이 여러번 계산됨 → 계산량은 약 2^(n−k) - 1
이항계수 - Dynamic Programming 방식으로 개선
: 배열 B[i][j] 사용
- B[i][j] = B[i-1][j-1] + B[i-1][j]
- 기저 조건: j=0 또는 j=i → B[i][j]=1
→ 재귀호출이 아닌 반복문으로 계산 가능
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))
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];
}
시간 복잡도 분석: 이중 for문에서 총연산 Θ(nk)
3. Graph
- 그래프 구성요소: 정점, 간선, 방향/무방향, 가중치
- 경로: 연속된 정점들의 순서
- 사이클: 시작점과 끝점이 같은 경로
- 최단 경로: 경로상의 가중치 합이 최소
Brute-force 방식의 비효율성
- 모든 경로를 다 계산하고 최단 경로 선택
- 가능한 경로 수 = (n-2)! → 지수시간 → 실제 사용 불가
Floyd 알고리즘
: 모든 쌍 최단 경로
- 입력: 인접 행렬 W[i][j]
간선 있으면 가중치, 없으면 ∞, 자기자신은 0
- 출력: 배열 D[i][j]: i에서 j로 가는 최단 경로의 길이
void floyd(int n, const 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]);
}
// 추가 배열 P[i][j]: i에서 j로 가는 최단 경로 중 중간 정점의 인덱스 저장
if (D[i][k] + D[k][j] < D[i][j]) {
D[i][j] = D[i][k] + D[k][j];
P[i][j] = k;
}
시간복잡도 Θ(n³) , 공간복잡도 Θ(n²)
이후 path(i,j)를 재귀적으로 호출하여 경로 구성 가능
최적화 문제와 Optimality Principle
: 최적성의 원리(principle of optimality)
- 어떤 문제의 최적해가 있다면, 그 서브 문제들 역시 최적해여야 한다.
ex. 최단 경로 문제는 적용 가능
BUT, 최장 경로 문제는 최적성의 원리가 성립하지 않음 -> Dynamic Programming 사용 불가
TSP(Traveling Salesperson Problem)
: 모든 도시를 한 번씩만 방문하고 원래 도시로 돌아오는 경로 중 최단 경로 찾기
- Brute-force방식: n=20이면 경로수: 19! ≈ 10¹⁸ → 계산 불가
- Dynamic Programming 방식의 TSP
: D[i][A]: i번 정점에서 시작해 A 집합의 도시를 지나 1번 도시로 돌아오는 최단 거리
재귀 관계, base case: A가 빈 집합일때 D[i][∅] = W[i][1]
- TSP 최종 해
: 시간복잡도 Θ(n²·2ⁿ)
최소 경로 길이
→ 예: 20개 도시 → DP는 45초, Brute-force는 3,857년
4. LCS (Longest Common Subsequence)
: 두 문자열 X,Y의 공통 부분 수열 중 가장 긴 것을 찾는 문제
ex) X=ABCD, Y=BDCAB → LCD = BCB
LCS DP알고리즘
: 배열 c[i][j]에 X[1..i], Y[1..j]까지의 LCS 길이 저장
점화식
- 시간복잡도: O(mn)
실제 LCS 찾기 -> 예제문제는 꼭 강의 자료 참고
- c[m][n]부터 거꾸로 추적하여 문자를 수집
- c[i][j] = c[i-1][j-1]+1이면 X[i]를 LCS에 포함
LCS 예제 문제 - Dynamic Programming 요약 - 테이블은 bottom-up 방식으로 채운다 - 같으면 ↖ 대각선 +1, 다르면 위/왼쪽 중 큰 값 선택 - 역추적은 오른쪽 아래에서 ↖ 방향으로 이동 - 시간 복잡도는 O(mn) - 최종 LCS: B C B
5. Sequence Alignment
: DNA나 단백질 서열 비교를 위해 사용
- 정렬 방식에 따라 match, mismatch, indel(gap) 점수 부여
점수 계산 공식
Global vs Local alignment
- Global: 전체 서열 정렬 - Needleman-Wunsch
- Local: 부분 서열 정렬 - Smith-Waterman (최대 점수에서 시작, 0에서 멈춤)
