Dynamic Programming
:동적 계획법 알고리즘 ➡️ 최적화 해결법
Dynamic programming(동적 계획법)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 디자인 기법 중 하나입니다.
이를 위해 일반적으로 큰 문제를 작은 문제로 쪼개고, 작은 문제의 결과를 저장하고 재활용하여 연산량을 줄입니다. 이를 메모이제이션(Memoization)이라고도 부릅니다.
이러한 방식은 다음과 같은 구조를 가집니다.
1) 작은 부분 문제로 나눕니다.
2) 작은 부분 문제의 결과를 저장합니다.
3) 작은 부분 문제의 결과를 이용해 큰 문제를 해결합니다.
이때, 작은 부분 문제의 결과가 일정한 패턴을 가지는 경우에는 재귀 함수나 반복문을 이용해 해결할 수 있습니다.
Dynamic programming은 최단 경로 문제, 배낭 문제, 그리드 문제 등 다양한 문제에서 적용됩니다. 이를 통해 연산 시간을 줄이면서, 효율적으로 문제를 해결할 수 있습니다.
Development of a DP Algorithm
- Characterize the structure of an optimal solution
- Recursively define the value of an optimal solution
- Compute the value of an optimal solution in a bottom-up fashion
- Construct an optimal solution from the information conputed in Step3
Elements of dynamic programming
- Optimal sub-structures 최적의 하위 구조
Optimal substructure는 DP의 핵심 개념 중 하나로, 큰 문제를 작은 문제들로 나눌 수 있으며 작은 문제들의 최적해를 이용해 전체 문제의 최적해를 구할 수 있는 구조를 의미합니다.
- Overlapping sub-problems 하위 문제의 반복 계산
Overlapping sub-problems는 Dynamic Programming에서 중요한 개념 중 하나입니다. 이는 큰 문제를 해결하는 동안에 작은 부분 문제가 반복되는 경우를 의미합니다.
예를 들어, 피보나치 수열을 구하는 문제를 생각해보겠습니다. 피보나치 수열은 0과 1로 시작하고, 이전 두 개의 수를 더하여 다음 수를 만들어가는 수열입니다. 따라서, 0, 1, 1, 2, 3, 5, 8, 13, ... 과 같이 진행됩니다.
이 문제를 DP로 해결하면, 다음과 같은 코드를 작성할 수 있습니다.
def fibonacci(n):
if n < 0:
return -1
elif n == 0:
return 0
elif n == 1:
return 1
else:
memo = [-1] * (n+1)
memo[0] = 0
memo[1] = 1
for i in range(2, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]이 코드에서 memo 배열은 각 인덱스가 해당 인덱스에 대한 피보나치 수를 의미하며, 한 번 계산된 값을 저장하기 위해 사용됩니다. 이를 통해, 이전에 계산한 값을 다시 계산하지 않고 해당 값을 참조하여 계산 속도를 높일 수 있습니다.
이 예시에서 memo[2]를 계산할 때, memo[0]과 memo[1]의 값이 필요합니다. 따라서 이전에 계산한 값들이 중복적으로 사용되는 것을 알 수 있습니다. 이렇게 하위 문제의 계산 결과가 중복되는 경우, DP를 사용하여 중복 계산을 피하고 효율적인 계산을 할 수 있습니다.
- Memoization and reuse
- 메모화 전략
Memoization은 DP의 구현 방법 중 하나로, 계산된 값을 저장하고 재사용함으로써 반복 계산을 피하는 방법입니다. Memoization을 사용하면 한 번 계산한 값을 저장해 둠으로써 동일한 값을 다시 계산하지 않아도 됩니다.
Memoization은 일반적으로 재귀적인 DP 알고리즘에서 많이 사용됩니다. 예를 들어, Fibonacci 수열을 구하는 재귀 함수에서 이전에 계산한 값을 저장해 둔다면, 같은 값이 여러 번 계산되지 않고 한 번만 계산되어 실행 시간을 줄일 수 있습니다.
아래는 Fibonacci 수열을 구하는 재귀 함수를 Memoization으로 개선한 예시입니다.
def fibonacci(n, memo):
if n in memo:
return memo[n]
if n <= 2:
return 1
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
EX) 실행 예시
n = 10
memo = {}
print(fibonacci(n, memo)) # 출력: 55위의 예시에서 memo는 이미 계산된 값들을 저장하는 딕셔너리입니다. 만약 n이 memo에 이미 있다면 저장된 값을 반환하고, 없다면 fibonacci() 함수를 재귀적으로 호출하여 값을 계산하고 memo에 저장합니다. 이렇게 하면 n이 같은 경우에는 값이 계산되지 않고 memo에서 값을 가져와 실행 시간을 단축할 수 있습니다.
Memoization은 중복 계산을 피하기 때문에 실행 시간을 단축시킬 수 있지만, 저장된 값들이 메모리를 차지하기 때문에 메모리 사용량이 증가할 수 있습니다. 따라서, Memoization을 사용할 때에는 적절한 저장 방법과 저장 시기를 고려해야 합니다.
minimum cost between stations
주어진 출발역과 도착역 사이에 여러 역이 있을 때, 각 역마다 지불하는 비용이 주어졌을 때 출발역에서 도착역까지 가는 최소 비용을 구하는 문제입니다.
이 문제를 동적 계획법으로 해결하려면 다음과 같은 방법을 사용할 수 있습니다.
1) 부분 문제 정의
출발역 s와 도착역 t 사이에 k개의 역이 있을 때, s에서 t까지 가는 최소 비용을 C[s][t]라고 정의합니다. 이 때, k는 0부터 n-2까지의 값을 가질 수 있으며, n은 전체 역의 수입니다.
2) 부분 문제 해결
문제 해결을 위해 최적 부분 구조와 중복 부분 문제를 활용합니다. 이 때, 중복 부분 문제를 해결하기 위해 메모이제이션 기법을 사용합니다.
C[s][t]는 다음과 같은 점화식으로 정의됩니다.
C[s][t] = min(C[s][i] + C[i][t]), s < i < t
이 점화식은 출발역에서 도착역까지 가는 최소 비용을 출발역과 도착역을 거쳐가는 최소 비용으로 나누어 해결하는 것입니다. 출발역과 도착역을 제외한 중간 역 i를 기준으로 나누어 해결합니다.
3) 기저 사례 처리
C[s][s] = 0 (출발역에서 출발역까지 가는 최소 비용은 0입니다.)
4) 최종 해 계산
C[s][t]를 계산한 후, 출발역 s와 도착역 t 사이의 최소 비용을 구할 수 있습니다.
function minCost(s, d)
if(s == d || s == d - 1)
return cost[s][d];
minValue = cost[s][d];
for i = s+1 to d-1
temp = minCost(s, i) + minCost(i, d);
if(temp < minValue)
minValue = temp;
return minValue;1) s와 d가 인접한 경우(즉, s == d 또는 s == d - 1인 경우): cost[s][d]를 반환합니다.
2) s와 d 사이에 또 다른 중간 역이 있는 경우: s와 d 사이의 모든 중간 역을 확인하여 그 중 최소 비용을 계산합니다.
if(s == d || s == d - 1): s와 d가 인접한 경우(즉, s == d 또는 s == d - 1인 경우)에는 cost[s][d]를 반환합니다.
minValue = cost[s][d];: minValue 변수를 초기화합니다. s와 d 사이의 경로 중 가장 적은 비용을 저장할 변수입니다.
for i = s+1 to d-1: s와 d 사이의 모든 중간 역에 대해 반복합니다.
temp = minCost(s, i) + minCost(i, d);: s에서 i까지의 최소 비용과 i에서 d까지의 최소 비용을 더하여 temp에 저장합니다.
if(temp < minValue): temp가 현재까지의 minValue보다 작은 경우 minValue를 temp로 업데이트합니다.
return minValue;: 모든 중간 역에 대해 검사한 후, s에서 d까지의 최소 비용을 반환합니다.
Memoization
- 이것도 재귀호출하는 것은 맞으나, 오버래핑은 안한다!
Memoization: Fibonacci
🔻의사코드
memo[N] = {0};
function fib(n)
if (memo[n] != 0)
return memo[n];
if (n == 1 || n == 2)
memo[n] = 1;
else
memo[n] = fib(n-1) + fib(n-2);
return memo[n];Memoization: minCost
🔻의사코드
memo[N][N] = {0};
function minCost(s, d)
if(s == d || s == d - 1) return cost[s][d];
if(memo[s][d] == 0)
minValue = cost[s][d];
for i = s+1 to d-1
temp = minCost(s, i) + minCost(i, d);
if(temp < minValue)
minValue = temp;
memo[s][d] = minValue;
return memo[s][d];
🔻C언어 코드
#include <stdio.h>
#include <stdlib.h>
#define N 5
int cost[N][N] = { // 인접 행렬로 나타낸 그래프의 각 가중치 값을 저장하는 2차원 배열
{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}
};
int memo[N][N] = { 0 };
int minValue;
int minCost(int s, int d) {
// minCost() 함수는 s부터 d까지 가는 최소 비용을 반환하는 함수입니다. s와 d가 인접한 경우와 거리가 1인 경우는 각각 가중치 값을 반환하고, 나머지 경우에는 DP 알고리즘을 이용하여 최소 비용을 계산
if (s == d || s == d - 1)
return cost[s][d];
if (memo[s][d] == 0)
{ // 현재 범위(s, d)가 메모이제이션 배열에 저장되어 있는지 확인합니다. 저장되어 있지 않은 경우 최소 비용을 계산하고, 계산한 값을 메모이제이션 배열에 저장
int minvalue = cost[s][d];
for (int i = s + 1; i < d; i++)
{ // 범위(s, d) 내에서 i번째 지점에서 경유하여 가는 경우의 최소 비용을 계산
int temp = minCost(s, i) + minCost(i, d); // s부터 i까지 가는 최소 비용과 i부터 d까지 가는 최소 비용을 더한 값을 temp에 저장
if (temp < minvalue) //temp 값이 현재 저장된 최소 비용보다 작으면 minValue 값을 갱신
minValue = temp;
}
memo[s][d] = minValue; // DP 알고리즘을 통해 계산한 최소 비용 값을 메모이제이션 배열에 저장
}
return memo[s][d]; // 범위(s, d) 내에서 가장 작은 비용을 반환
}
int main() {
printf("%d\n", minCost(0, 4)); // s=0, d=4로 초기 설정하고, minCost 함수를 호출하여 최소 비용을 출력
}🔻C언어 코드
#include <stdio.h>
#include <stdlib.h>
#define N 5
int cost[N][N] = { // 인접 행렬로 나타낸 그래프의 각 가중치 값을 저장하는 2차원 배열
{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}
};
int memo[N][N] = { 0 };
int minValue;
int minCost(int s, int d) {
int minValue[N];
minValue[0] = 0;
minValue[1] = cost[0][1];
for (int i = 2; i < N; i++) {
minValue[i] = cost[0][i];
for (int j = 1; j < i; j++)
if (minValue[i] > minValue[j] + cost[j][i])
minValue[i] = minValue[j] + cost[j][i];
}
for (int i = 0; i < N; i++)
printf("[%d]", minValue[i]);
printf("\n");
}
int main() {
printf("%d\n", minValue[4]); // s=0, d=4로 초기 설정하고, minCost 함수를 호출하여 최소 비용을 출력
}- Top-Down Dynamic Programming
: memoization(메모이제이션) - Bottom-Up Dynamic Programming
: Tabulation(테이블 이용 동적프로그래밍)
결론
Divide and Conquer(분할 정복) ➡️ Optimal sub-structure & Overlapping sub-problem
➕ Divide and Conquer(분할 정복)은 문제를 작은 부분으로 나누어 해결하는 알고리즘 설계 기법입니다. 큰 문제를 해결하기 어려운 경우에 작은 문제로 분할하고, 작은 문제를 각각 해결한 후에 결과를 합쳐서 원래 문제를 해결하는 방법입니다.
Divide and Conquer 알고리즘은 일반적으로 세 단계로 구성됩니다.
1) Divide(분할) : 해결하고자 하는 문제를 작은 크기의 동일한 부분 문제로 분할합니다.
2) Conquer(정복) : 부분 문제를 재귀적으로 해결합니다. 부분 문제의 크기가 충분히 작으면 해를 구할 수 있습니다.
3) Combine(결합) : 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 구합니다.
Divide and Conquer는 주로 정렬, 최적화, 검색 등 다양한 분야에서 활용됩니다. 대표적인 예시로는 병합 정렬(merge sort), 퀵 정렬(quick sort) 등이 있습니다. 이러한 알고리즘은 대부분 재귀적으로 구현되며, 분할 단계에서 배열을 둘 이상의 작은 배열로 분할하고, 정복 단계에서 각각의 작은 배열을 정렬하고, 결합 단계에서 정렬된 작은 배열들을 하나로 합칩니다.
Divide and Conquer 알고리즘은 일반적으로 재귀적인 방법을 사용하기 때문에, 재귀 호출의 오버헤드가 큰 경우에는 비효율적일 수 있습니다. 또한 부분 문제들 간의 연관성이 높은 경우에는 분할 단계에서 문제를 나누기 어려울 수 있습니다. 그러나 적절히 설계된 Divide and Conquer 알고리즘은 효율적인 알고리즘 설계의 대표적인 방법 중 하나입니다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX(a,b) ((a) > (b) ? (a) : (b))
int knapSack(int W[], int V[], int n, int w) {
int n;
int grid[n + 1][n + 1];
for (int i = 0; i <= n; i++)
grid[i][0] = 0;
for (int j = 0; j <= w; j++)
grid[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= w; j++)
{
if (W[i - 1] <= j)
{
int x = j - W[i - 1];
grid[i][j] = MAX(grid[i - 1][j], V[i - 1] + grid[i - 1][x]);
}
else
grid[i][j] = grid[i - 1][j];
}
}
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= w; j++)
printf("%2d ", grid[i][j]);
printf("\n");
}
}
int main(){
int W[3] = { 1,4,3 };
int V[3] = { 15, 30, 20 };
knapSack(W, V, 3, 4);
return 0;
};