알고리즘 설계- 동적 프로그래밍

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 분해하고, 그것으로부터 최적의 해결책을 찾는 알고리즘 기법이다. 이 방식은 각 부분 문제의 해를 저장하고 ("메모이제이션"이라고 함), 필요할 때 다시 사용해서 중복 계산을 방지한다.

동적 프로그래밍은 주로 최적화 문제에서 사용되며, 아래 두 가지 속성을 만족하는 문제에 적용할 수 있다:

1. **최적 부분 구조(Optimal Substructure)**: 큰 문제의 최적의 해를 그 문제의 작은 부분 문제들의 최적의 해로부터 구할 수 있어야 한다.

2. **중복되는 부분 문제(Overlapping Subproblems)**: 같은 부분 문제들이 여러 번 반복해서 나타나는 경우, 이 부분 문제들의 결과를 저장하고 재사용함으로써 중복 계산을 방지할 수 있어야 한다.

동적 프로그래밍의 기본적인 접근법은 다음과 같다:

1. 문제를 부분 문제로 분해한다.
2. 가장 작은 부분 문제부터 시작해 해결책을 찾고, 그것을 저장한다.
3. 그 다음으로 큰 부분 문제의 해결책을 찾기 위해 이전에 계산된 작은 부분 문제들의 해결책을 이용한다.
4. 모든 부분 문제의 해결책을 이용하여 원래의 문제를 해결한다.

동적 프로그래밍은 계산 복잡성을 줄이는 매우 효과적인 방법이다. 여러 문제, 예를 들어 배낭 문제(Knapsack Problem), 최장 공통 부분열(Longest Common Subsequence), 최단 경로 문제(Shortest Path Problem) 등에 사용된다. 그러나 모든 문제에 동적 프로그래밍을 적용할 수 있는 것은 아니다. 위에서 언급한 최적 부분 구조와 중복되는 부분 문제라는 조건을 만족하는 문제에만 적용할 수 있다.

 

---

이항 계수 구하기

이항계수 구하는 공식은 n!/k!*(n-k)! 이므로 팩토리얼 계산이 필요하다.

팩토리얼을 이용하지 않고 다음의 식을 이용한다.

(n,k)=(n-1,k-1)+(n-1,k)

if(k=0 | k=n) 1

 

>>분할정복법

int bin(int n,int k){
	if(k==0||n==k)
    	return 1;
    else
    	return bin(n-1,k-1)+bin(n-1,k);

}

이 방식은 같은 계산이 여러번 필요하기 때문에 비효율적이다.

 

>>동적 프로그래밍

int bin(int n,int k){
	index i,j;
    int B[n][k];
    for(int i=0;i<=n;i++)
    	for(int 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]B[j];
    return B[n][k];
}

---

합이 최대인 부분 리스트 구하기

 

int maxSubList(double[] A, int n){
	double[] B, max;
    B=new double[n];
    max=B[0] = A[0];
    for(int i=1;i<n;i++){
    	B[i]=(B[i-1]<=0)?A[i]:B[i-1]+A[i];
        if(max<B[i])
        	max=B[i];
    }
    return max;
}

B라는 배열에 누적합을 구하고,

매번 누적합을 갱신할 때마다 이전의 누적합 갱신값이 음수인지 체크한다. 음수가 아니라면 계속해서 누적하고,

음수라면 새롭게 부분리스트를 시작한다.

 

---

행렬 경로 문제

(0,0)에서 (n,n)으로 이동하고자 한다. 이동은 오른쪽 또는 아래로만 가능하다.

각 칸에는 이동에 필요한 비용이 적혀있다.

#include<stdio.h>
#define N 3  // 행렬의 크기를 N*N으로 정의합니다. 필요에 따라 N 값을 변경하세요.
#define INF 1000000000  // 무한대를 나타내는 값입니다.

int min(int x, int y){
    return (x < y)? x : y;
}

int minCost(int cost[N][N]) {
    int dp[N][N];
    dp[0][0] = cost[0][0];
    
    // 첫 번째 열 초기화
    for(int i = 1; i < N; i++)
        dp[i][0] = dp[i-1][0] + cost[i][0];
    
    // 첫 번째 행 초기화
    for(int j = 1; j < N; j++)
        dp[0][j] = dp[0][j-1] + cost[0][j];
    
    // 나머지 행렬 채우기
    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++)
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j];
    
    return dp[N-1][N-1];
}

int main() {
    int cost[N][N] = { {1, 3, 5},
                       {2, 1, 2},
                       {4, 3, 2} }; // 비용 행렬을 설정하십시오. 필요에 따라 값 변경
    printf("minimum cost to reach (N,N) is %d", minCost(cost));
    return 0;
}

---

최단거리(Floyd)

void floyd(int n,const number W[][],number D[][],index P[][]){
	for(int 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]){
                	P[i][j]=k;
                    D[i][j]=D[i][k]+D[k][j];
                }


}

---

외판원 문제(TSP)

한 정점에서 다른 모든 정점을 거쳐 다시 자기 자신으로 돌아오는 경로

 

....

D[vi][{vj,vk}] = min(W[i][j] + D[vj][vk], W[i][k] + D[vk][vj])

 

 

..............................

D[v1][{v2,v3,v4}] = min(W[1][2] + D[2][{v3,v4}],

 

W[1][3] + D[3][{v2,v4}],

W[1][4] + D[4][{v2,v3}])

 

..