[알고리즘] 동적 프로그래밍
1. 어떤 문제를 동적 프로그래밍으로 푸는가
- 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 재귀적 중복을 해결하는 방법을 뜻함.
- 피보나치 수 구하기에 동적 프로그래밍의 개념을 이해할 수 있는 핵심이 모두 들어있음.
f(n) = f(n-1) + f(n-2)
f(1) = f(2) = 1
- n의 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치 수를 포함하고 있음.
- 이처럼 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조를 가졌다고 함.
- 동적 프로그래밍을 적용하려면 문제가 일단 이 성질을 가져야 함.
- 간명하지만 때때로 엄청난 비효율을 초래할 수 있음.
- 문제의 크기가 커지면 중복 호출이 증가하는 정도를 보이고, 중복 호출 횟수 자체가 다시 피보나치 수열을 이룸.
- 증가 속도는 Ω(2^n/2), 적어도 2^n/2 이상의 비율로 증가해 지수 함수적임.
- 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생하는 경우가 동적 프로그래밍을 사용하기 적합한 두 번째 조건임.
정리
- 다음 두 성질이 있는 문제에 대해 적절한 저장 방법으로 중복 호출의 비효율을 제거한 것을 동적 프로그래밍이라 함.
1. 최적 부분 구조를 이룸.
2. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생함.
피보나치 수 ( 동적 프로그래밍 1 )
- 아래에서 위로 구하면 선형 시간에 구해짐.
- 배열 f[]에 작은 것부터 저장해가면서 계산하는 방식
fibonacci(n)
{
f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i-1] + f[i-2];
return f[n];
}
- for 루프를 순환하는 것이 수행 시간을 좌우하므로 선형 시간 알고리즘.
- for 루프가 한 번 돌 때마다 앞에서 구해 저장해놓은 피보나치 수 두 개를 배열에서 가져다 더하기만 하면 됨.
피보나치 수 ( 동적 프로그래밍 2 )
// 배열 f[]의 모든 원소를 0으로 초기화되어 있고, 0이라면 아직 수행되지 않았음을 의미함.
fib(n)
{
if ( f[n] ≠ 0 ) then return f[n];
else {
if ( n = 1 or n = 2 )
then f[n] <- 1;
else f[n] <- fib(n-1) + fib (n-2);
return f[n];
}
}
- 이전에 호출되었는지 여부는 f[i] 값이 아직 0으로 남아 있는지만 확인해보면 알 수 있음.
- 재귀호출을 사용하되 한 번 호출된 것은 메모 해둠으로써 중복 호출을 피함. <- 이것도 동적 프로그래밍
- 중복된 재귀호출을 피하는 이런 방법의 동적 프로그래밍에는 메모하기(Memoization)라는 이름이 붙어 있음.
- 탑다운 방식의 동적 프로그래밍으로 하향식 방법임.
- 아래에서 위로 저장해가면서 해를 구해나가는 것은 바텀업 방식의 동적 프로그래밍으로 상향식 방법임.
2. 행렬 경로 문제
- 양수로 이루어진 n * n 행렬이 주어짐. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달함.
- 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합.
이동 규칙
1. 오른쪽이나 아래쪽으로만 이동할 수 있음
2. 왼쪽, 위쪽, 대각선 이동은 허용하지 않음.
- 행렬의 모든 경로의 점수 중 가장 높은 점수를 구하는 문제임.
- 가능한 모든 이동 경로를 따져본 다음 가장 높은 점수를 구할 수는 있으나 지수함수적인 시간이 걸림.
최적 부분 구조의 존재를 확인
- 원소 (i,j)에 도달하기 직전에 방문할 수 있는 원소는 (i-1,j)와 (i,j-1) 단 두개.
- 원소 (i,j)는 방문하므로 원소(i,j)의 값은 반드시 더해짐.
- 두 가지의 경우 중에 점수가 높은 쪽을 선택하면 됨.
- (i-1,j)까지 도달하는 최고 점수와 (i, j-1)까지 도달하는 최고 점수 중 큰 것에 원소 (i, j)의 점수를 더하면 원소 (i,j)까지 도달하는 최고 점수가 됨.
- 문제 (i, j)의 점수를 더하면 원소 (i,j)까지 도달하는 최고 점수가 됨.
- 문제 (i, j)의 최적해는 문제 (i-1,j)의 최적해와 문제 (i,j-1)의 최적해로 설명됨.
- 즉, 자신의 부분 문제에 대한 최적해를 자신의 최적해를 구성하는 데 사용함.
최적 부분 구조를 재귀적 관계로 나타냄
matrixPath(i,j)
{
if ( i = 0 or j = 0 ) then return 0;
else return (mij + (max(matrixPath(i-1,j), matrixPath(i,j-1))));
}
- 중복 호출이 일어남.
- 문제가 커지면 중복 호출이 지수 함수적으로 일어나게됨.
행렬 경로 문제(동적 프로그래밍)
matrixPath(n)
{
for i <- 0 to n
c[i,0] <- 0;
for j <- 1 to n
c[0,j] <- 0;
---①---
for i <- 1 to n
for j <- 1 to n
②c[i,j] <- mij + max( c[i-1,j], c[i,j-1]);
--------
return c[n,n];
}
- 수행 시간은 ①의 for 루프가 지배함. ②는 배열의 두 원소 중 큰 것을 고르는 작업과 덧셈이라서 상수 시간이 듦.
- 그러므로 알고리즘의 총 수행 시간은 Θ(n²)임.
- 행렬의 원소 수(n²)에 대해서는 선형 시간.
3. 돌 놓기 문제
- 3 x n 테이블의 각 칸에 숫자가 쓰여 있음.
- 테이블의 각 칸 중 일부에 제한조건을 만족하는 방법으로 돌을 놓아 돌이 놓인 곳에 있는 수의 합을 최대로 하는 문제
돌을 놓는 제한조건
- 가로나 세로로 인접한 두 칸에 동시에 돌이 놓일 수 없음.
- 각 열에는 적어도 하나 이상의 돌을 놓음.
- 합법적인 예는 제한조건을 만족하고, 합법적이지 않은 예는 제한조건을 만족하지 않음.
- 돌을 놓는 모든 경우의 수를 따져본 다음 가장 높은 점수를 구할 수는 있으나 지수 함수적인 시간이 걸림.
최적 부분 구조의 존재 확인
- n열 중 1열부터 i열까지 돌을 놓는 경우에 1열부터 i열까지 합의 최고치를 생각하면 i열에는 네 가지 패턴 중 하나로 돌이 놓일 것
- i열까지 최적해는 i-1열까지 최적해를 포함.
- 자신보다 크기가 하나 작은 문제의 최적해를 자신의 최적해를 구성하는 데 사용함.
pebble(i,p)
{
if (i=1)
then return w[1,p];
else {
max <- -∞;
for q <- 1 to 4
if (패턴 q가 패턴 p와 양립) then {
tmp <- pebble (i-1,q);
if ( tmp > max) then max <- tmp;
}
return (max + w[i,p]);
}
}
- 최종적으로 pebble(n, 1)~pebble(n,4)의 결과 중 최댓값이 답임.
- 이는 상당한 중복 호출이 관찰됨.
- 문제가 커지면 지수 함수적으로 중복 호출이 일어남.
- 이 문제에 존재하는 부분 문제를 모두 나열하면 총 4n개.
- 함수 pebble()을 한 번 호출하는 것은 부분 문제 한 개와 대응됨.
- 이 4n개를 아래에서부터 저장해가면서 구하면 중복을 피할 수 있음.
돌 놓기 문제(동적 프로그래밍)
pebble(n)
{
for p <- 1 to 4
peb[1,p] <- w[1,p];
---①---
for i <- 2 to n
for p <- 1 to 4
peb[i,p] <- max{ peb[i-1,q]} + w[i,p];
---------
return max{peb[n,p]};
}
- 이 알고리즘의 수행 시간은 ①의 for 루프가 지배함.
- 바깥쪽의 for 루프는 n-1번 반복되고, 각 반복마다 안쪽의 for 루프는 4번만 반복되므로 중첩된 for 루프는 4(n-1)번 반복됨.
- 수행시간은 Θ(n)
4. 행렬 곱셈 순서 문제
- n개의 행렬이 주어지고 이들의 곱을 계산할 때 3개의 행렬을 한꺼번에 곱할 수 없으므로 한 번에 2개씩 곱해서 1개의 행렬을 구해야함.
- 가장 단순한 방법은 앞에서부터 차례로 곱해나가는 것.
- A1A2를 구하고, 여기에 A3을 곱해 (A1A2)A3을 구하고, 이런 식으로 계속하여 마지막으로 (A1A2 ... An-1)과 An을 곱해서 구함.
- 행렬의 곱셈은 결합 법칙이 성립함. 즉, (AB)C = A(BC)
- 괄호를 묶는 방법은 여러가지 존재하지만 어떤 순서로 수행하는 총 3번의 행렬 곱셈을 하게 됨.
- 일반적으로 행렬 곱셈에 대해서는 총 n-1번의 곱셈을 함.
- 두 행렬 A, B가 각각 p × q, q × r 행렬이라면 두 행렬의 곱은 pqr번의 수의 곱셈이 일어남. 이것이 곱셈 시간을 좌우함.
- 일반적으로 n개의 행렬을 곱하는 경우에는 이 차이가 엄청나게 증폭될 수 있음.
- n개의 행렬을 곱하기 위해 괄호로 묶는 방법의 총 가짓수는 Ω(2ⁿ), 즉 적어도 2의 지수 함수 이상에 비례함.
- 행렬 곱셈 순서 문제는 n개의 행렬이 주어졌을 때 이들을 어떤 순서로 곱하는 것이 가장 시간을 적게 사용하는지 알아내는 문제임.
최적 부분 구조의 존재 확인
- 행렬이 구해지는 마지막 행렬 곱셈이 어떻게 이루어지느냐에 따라 n-1가지로 나눌 수 있음.
rMatrixChain(i,j)
{
if (i=j) then return 0;
min <- ∞;
for k <- i to j-1 {
①q <- rMatrixChain(i, k) + rMatrixChain(k+1,j) + pi-1 pk pj;
if ( q < min ) then min <- q;
}
return min;
}
- 이 알고리즘은 앞의 관계식을 정확하게 구현하지만 재귀호출의 중복이 심해서 Ω(2ⁿ)시간이 소요됨.
matrixChain(n)
{
for i <- 1 to n
m[i,i] <- 0;
for r <- 1 to n-1
for i <-1 to n-r {
j <- i+r;
m[i,j] <- min { m[i,k] + m[k+1,j] + pi-1 pk pj };
}
return m[1,n];
}
- 알고리즘은 2개의 for루프가 중첩되어 있고, 안쪽의 for 루프에서 m[i,j]를 구하기 위해서 총 r가지 경우를 비교해보아야함.
- 이 중첩된 for 루프로 수행 시간의 부담은 Θ(n³)