Dynamic Programming(DP) 알고리즘
-입력 크기가 작은 부분 문제들을 해결한 후에
-그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해어
-최종적으로 원래 주어진 입력의 문제를 해결
[문제]
n개의 원소를 갖는 문제
같은 형태로 문제를 해결해나가지만 n개보다 작은 값으로 (작은 문제로 ) 만들어서 푸는 방법
(1) 최적의 하위구조 특성
k < n 인 k개의 원소를 갖는 문제를 정의하고 문제를 풀었더니 그것이 최적의 풀이법이고 점점점 작은 문제들을 결합해서 최종 풀이법이 완성되어지는 형태의 특성을 갖는 문제를 “최적의 하위구조 특성을 갖는 문제”라고 부른다.
예시) 두 도시를 자동차로 갈 수 있는 최단 경로
A도시 B도시 C도시가 있는데 A에서 C로 가기 위해서는 A-B의 최단 경로를 구하고 B-C의 최단 경로를 구한 것이다.
즉, A-C 최단 경로를 구하는 문제에 A-B 최단 경로를 구하는 문제가 포함이 되며 재귀적인 접근 방법으로 문제를 해결할 수 있다는 의미라고 할 수 있다. (문제를 잘게 나누어서 해결하는 방법이므로)
(2) 하위 문제의 반복 계산 특성
어떤 문제가 최적의 하위구조 특성을 가지고 있는데 sub problem들을 계산하는데 계속해서 반복해서 풀어야 한다면 이는 하위 문제의 반복 계산 특성이라고 할 수 있다. 이 때문에 오버헤드가 발생하게 된다면 반드시 DP알고리즘으로 해결해야 하는 문제이다.
(재귀 조건 방식을 썼는데 반복계산이 필요하다면 하위 문제의 반복 계산 특성이라고 할 수 있다)
이렇게 최적의 하위구조 특성과 하위 문제의 반복 계산 특성을 갖는 문제라고 판단된다면
이에 대한 해결 방안은 DP알고리즘이다.
동적 계획 알고리즘 설계원칙
(1) 문제의 해를 구할 수 있는 재귀적인 성질을 설정한다.
(2) 상향식 접근 방법에 의해 크기가 작은 문제를 먼저 해결한 후 크기가 큰 문제를 나중에 해결한다.
(3) 크기가 큰 문제의 해결을 효율적으로 하기 위하여 크기가 작은 문제의 해는 테이블에 저장한다. (이는 같은 크기의 문제의 해를 다시 계산하는 과정을 피하기 위해서이다)
재귀조건 방법과 DP문제
DP의 첫 단계는 주어진 점화식을 작성하거나 최적의 하위구조를 정의하는 것이 첫번째 단계이다. 점화식을 작성하거나 최적의 하위구조를 정의하는 것은 재귀 접근 방식으로부터 시작된다. 즉, 문제 자체가 재귀 조건 방법에서 시작하여 DP방법으로 오는 것이라고 볼 수 있다.
어떤 문제가 재귀적으로 정의되어 있지 않다면 이것을 DP로 적용한다는 것은 매우 어려운 것이다.
*재귀 혹은 점화식을 이용해서 문제를 푼 다음에 여기서 해결했던 로직을 DP의 관점에서 상향식으로 접근하는 것이 가장 좋은 방법이다.
[재귀 접근 방식] = 하위 문제를 발생시켜서 하위 문제들을 점점 더 하위문제들로 파생시키고 이것을 반복하면서 문제를 해결하는 방법이다.
메모리 전략 기법
메모 전략도 재귀 접근 방법이다. 하지만 반복 계산을 방지하여 메모 전략을 성능 향상의 측면에서 재귀 접근 방법에 비해 강력한 기법이라고 볼 수 있다.
(1) 재귀 함수에서 발생하는 하위 호출의 반복 계산의 부작용을 피하면서
(2) 문제의 구체화 및 하향식 문제 해결이라는 장점을 제공한다.
재귀호출의 장점 + 캐시(메모리)를 추가적으로 사용하지만
하위 문제의 반복 계산을 제거하여 재귀 호출에 비해서 실행 시간의 측면에서 성능을 향상시킨다.
그럼에도 메모 전략 자체가 재귀적인 방법이므로 함수의 재귀적 호출에서 발생되는 오버헤드는 피할 수 없다. (재귀 호출로 인한 시스템 스택에 저장되는 정보들이 별도의 오버헤드를 발생시켰기 때문에)
따라서 이 메모리 전략에서 조금 더 나아진 최적화 방법은 DP프로그래밍이다.
동적 계획 알고리즘(다이나믹 프로그래밍)
= 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
*메모리 전략도 다이나믹 프로그래밍이 된다. 그러면 이는 문제 해결 순서로 구분한다.
메모 전략 혹은 재귀호출의 경우 하향식 접근 방식을 사용한다 하지만 DP는 상향식 접근 방법을 사용한다.
(어떤 문헌에서는 메모 전략을 하향식 DP프로그래밍이라고 부르기도 한다)
* 메모리 전략 방법 보다 DP가 더 나은 이유
재귀 호출로 인한 시스템 스택에 저장되는 정보들이 별도의 오버헤드를 발생시킨다. 하지만 이 방법은 함수 호출이 1번만 시스템 스택에 올라가기 때문에 효율성이 더 좋다고 할 수 있다.
동적 계획 알고리즘과 분할 정복 알고리즘의 차이점
분할 정복 방식이 주어진 문제를 크기가 작은 여러 개의 부분 문제로 분할하여 부분 문제들의 해를 구한 후에 그 해들을 결함하여 원래 문제에 대한 해를 구하는 것처럼, 동적 계획법도 크기가 작은 부분 문제들의 해들을 결합하여 문제를 해결한다.
다만, 두 방법의 차이점을 보면, 분할 정복 방식은 문제를 크기가 작은 부분 문제로 분할하고 분할된 부분 문제들을 서로 독립적으로 해결한 후 그 해들을 결합하여 원래 문제의 해를 구한다. 하지만 동적 계획법은 부분 문제를 해결하여 그 해를 테이블에 저장한 후에 다시 그 부분 문제에 다시 그 부분 문제를 풀어야 할 때 다시 풀지 않고 테이블에 저장된 결과를 사용하는 방법이다. ( = 상향식 접근 방법)
→ 부분 문제를 풀어야 할 때 다시 풀지 않고 테이블에 저장된 결과를 사용하는 방법이다.
따라서, 분할 정복 방식에서는 서로 공유되는 같은 부분 문제가 있다고 하더라도 독립적으로 반복적인 계산을 하지만 동적 계획법에서는 이러한 반복적인 계산을 피할 수 있으므로 효율적으로 문제를 해결할 수 있다.
[ 예제로 적용 ]
역 (station)과 역 사이의 최소 비용을 구하는 문제를 각각 (1) 메모리 전략 기법과 (2) 동적 계획 알고리즘 방식으로 풀 수 있다.
먼저, 문제 자체를 설명하자면 역과 역사이에는 비용이 발생하는데 이 비용을 최소화하는 방향으로 역들을 선택하여 이동하는 문제이다.
[알고리즘]
- minCost[0]의 일차원 배열이 있다.
- 이 배열을 0번에서부터 시작하는 것인데 전체의 역들 사이의 거리들의 최소값을 배열에 저장한 것이다. (각 역들까지의 최소 비용)
- 이 역과 역사이의 모든 거리들은 cost라고 하는 2차원 배열에 저장되어 있다.
(1) 0 ~ n-1까지 N개의 역이 존재
(2) 한 방향으로만 이동가능
요금 = cost[i][j] => i번 역에서 j번 역까지의 요금
- i = j일 경우 출발지와 목적지가 같으므로 0원이다.
보기 예시
cost[4][4] =
{ (0, 10, 75, 94), // 0에서 출발하는 비용
(-1, 0, 31, 50), //1에서 출발하는 비용
(-1, -1, 0, 80), //2에서 출발하는 비용
(-1, -1, -1, 0),
예를 들어 0번에서 2번으로 이동한다고 하자
그러면 0에서 바로 2번으로 가는 비용은 75이고
0번 -> 1번 -> 2번으로 가는 경우의 비용은 10 + 38 = 45이다.
최소 요금을 재귀적으로 계산을 해본다면
(1) 재귀적인 방법
최소 요금을 구하기 위해서 중간 역들 사이의 최소 요금을 구하고 있음 → "최적의 하위 구조의 특성"
minCost ( 0, N-1) 0에서 N-1로 가는 경우 중에서 가장 작은 값을 구해보자
= MIN{ → 다음의 경우의 수 중에서 가장 작은 경우를 고르는 것임
cost[0][0-N] ,
cost[0][1] + minCost(1, N-1),
minCost(0, 2) + minCost(2, N-1), → 0에서 2번까지 가는 경우의 수는 많은데 그 중 최솟값을 고른다는 의미
...
minCost(0, N-2) + cost[N-2][N-1]
}
이는 minCost를 재귀적으로 호출하는 것임
#include <stdio.h>
#define N 4
int cost[N][N] = {
{0, 10, 75, 94},
{-1, 0, 35, 50},
{-1, -1, 0, 80},
{-1, -1, -1, 0}
};
int minCost(int s, int d)
{
if (s == d || s == d - 1) // 출발역과 도착역이 같거나 출발역과 도착역 전이라면 이미 비용은 하나의 경우밖에 없음
return cost[s][d];
int minValue = cost[s][d]; //최소값을 찾기 위해 일단 다이렉트로 가는 방법을 minValue라고 해놓고 다른 방법이 더 최솟값이라면 값을 바꾸자
for (int i = s + 1; i < d; i++)
{
int temp = minCost(s, i) + minCost(i, d); //s에서 d까지 가는데 중간에 i번째를 경우하는 방법을 고려한다.
if (temp < minValue) // 경유하는 방법 중에 최솟값이 있다면 변경
minValue = temp;
}
return minValue;
}
int main()
{
printf("%d : %d\\n", minCost(0, 3));
return 0;
}
(2) 메모리 전략 기법
2차원 배열로 계산 결과를 저장할 메모리를 추가한다.
#include <stdio.h>
#define N 4
int memo[N][N] = { 0 }; // 모든 값을 0으로 초기화 한다.
int cost[N][N] = {
{0, 10, 75, 94},
{-1, 0, 35, 50},
{-1, -1, 0, 80},
{-1, -1, -1, 0}
};
int minCost(int s, int d)
{
if (s == d || s == d - 1) // 출발역과 도착역이 같거나 출발역과 도착역 전이라면 이미 비용은 하나의 경우밖에 없음
return cost[s][d];
if (memo[s][d] == 0) //값이 없다면 계산하자
{
int minValue = cost[s][d]; //최소값을 찾기 위해 일단 다이렉트로 가는 방법을 minValue라고 해놓고 다른 방법이 더 최솟값이라면 값을 바꾸자
for (int i = s + 1; i < d; i++)
{
int temp = minCost(s, i) + minCost(i, d); //s에서 d까지 가는데 중간에 i번째를 경우하는 방법을 고려한다.
if (temp < minValue) // 경유하는 방법 중에 최솟값이 있다면 변경
minValue = temp;
}
memo[s][d] = minValue;
}
return memo[s][d];
}
//시간 복잡도를 따지면 O(n^3)만큼이다. 지수시간에 비해 크게 개선되었다.
int main()
{
printf("%d : %d\\n", minCost(0, 3));
return 0;
}
DP문제
*위의 그림처럼 모든 DP문제는 그리드 격자 테이블로 시작한다.
각각 0번 역 -0번 역, 0번 역→1번 역, 0번 역 →2번 역 , 0번 역 → 3번 역, 0번 역 → 4번 역으로 가는 방법이라고 할 수 있다.(일차원 배열)
여기서 0 → 3으로 가는 방법을 보자면
- minCost[0] + cost[0][3] → 앞에서 minCost[0]로 가는 방법(0)을 이미 구해놨다.
- minCost[1] + cost[1][3] → 앞에서 이미 0 → 1로 가는 최소의 방법(10)을 이미 구했다.
- minCost[2] + cost[2][3] → 앞에서 이미 0 → 2로 가는 최소의 방법(45)을 이미 구했다.
#include <stdio.h>
#define N 5
int cost[N][N] = {
{0, 10, 75, 94, 110},
{-1, 0, 35, 50, 85},
{-1, -1, 0, 30, 50},
{-1, -1, -1, 0, 30 },
{-1, -1, -1, -1, 0}
};
void minCost()
{
int minValue[N];
minValue[0] = 0;
minValue[1] = cost[0][1]; //0~1의 방법은 1가지 밖에 없음
for (int i = 2; i < N; i++)
{
minValue[i] = cost[0][i]; //일단 다이렉트로 오는 것을 minValue라고 해놓고
for (int j = 1; j < i; j++) // 여기서 i는 몇번째 역까지의 최솟값인지 구하는 것임
if (minValue[i] > minValue[j] + cost[j][i]) //직접 가는 것보다 j번째 역을 경유해서 가는 경우
minValue[i] = minValue[j] + cost[j][i];
}
for (int i = 0; i < N; i++)
{
printf("[%d]", minValue[i]);
}
printf("\n");
}
int main()
{
minCost();
return 0;
}
참고 = 「컴퓨터 알고리즘의 이해」 (이상호)
'CS > 알고리즘' 카테고리의 다른 글
| Chap 5-2.연속 행렬 곱셈 (0) | 2022.05.26 |
|---|---|
| Chap 5-1. 0-1 배낭 문제 (0) | 2022.05.06 |
| Chap 4-7. 허프만 압축 (0) | 2022.05.04 |
| Chap4-6. 작업스케줄링(Job scheduling) (0) | 2022.04.15 |
| Chap4-2. 최소 신장 트리 (0) | 2022.04.11 |
