알고리즘 강좌 2회
- 다이나믹 #1 -
|
1. 동적계획법의 특징 |
다이나믹 프로그래밍(dynamic programming : 이하 동적계획법) 이란 무엇일까. 이 역시 문제를 푸는 알고리즘의 일종이다. 다이나믹의 가장 큰 특징은 이것이다.
"작은 문제들을 해결한 다음 이 결과들을 바탕으로 더 큰 문제의 해답을 찾는 방법이다."
물론 이 말 한마디만으로 동적계획법에 대해 알수는 없다. 동적계획법의 특징들을 하나씩 살펴보자. 우선, 동적계획법은 작은문제를 먼저 해결하고 그 결과를 저장한 다음, 나중에 그 결과가 필요할때 다시 계산하는 대신 저장된 결과를 이용한다. 탑을 쌓을때 밑둥부터 차근차근 쌓아가는 것 처럼, 그 전의 결과를 바탕으로 새로운 결과를 만들어 낸다. 이를 상향식 접근방법이라고 한다. 나중에 배우게 될 분할정복과는 정 반대의 방법이다.(분할정복은 하향식 방법이라 부른다)
여기서 동적계획법의 특징이 하나 더 생기게 된다. 위의 파란색으로 쓴 문장안에 이런 글귀가 있다.
"그 결과를 저장한 다음..."
작은문제들을 해결해서 얻어낸 결과를 프로그램 상에서는 배열을 선언해서 저장해 두어야 한다는 것이다. 이미 계산해낸 결과들은 다음에 그 결과가 필요할때 그걸 빼서 쓰기만 하면 된다. 이러한 특성때문에 동적계획법에서는 배열을 어떻게 잡는가 하는것도 꽤 중요한 문제이다.
동적계획법의 또 하나의 중요한 특징은 작은 문제의 결과에서 큰 문제의 결과를 끌어내기위한 재귀 관계식(recursive property)을 세워야 한다는 것이다. 이러한 재귀 관계식을 '점화식'이라고 부르기도 한다.(여기서도 그냥 '점화식'이라 칭한다. '재귀 관계식'은 말이 너무 기니까.)
그냥 이론적으로만 주저리 주저리 써 놓았기 때문에 이해가 잘 안 갈 것 같다.(글 쓴 나
도 좀 알아보기가 힘들다-_-a) 다음 절에서 동적계획법을 실제로 써 보기로 하자.
|
2. 동적계획법의 실제 #1 |
우선 너무나도 유명한 동적계획법 예제인 '피보나치 수열의 n항 구하기'를 해보자.
피보나치 수열은 다음과 같이 나가는 수열을 말한다.
1 1 2 3 5 8 13 21 34 .........
이 수열을 자세히 보면 한가지 느끼는 바가 있을 것이다.
"음, 이 수열의 어떤 숫자는 그 숫자 바로 앞에 붙어있는 두 숫자의 합과 같군! 음홧홧홧 난 역시 똑똑해.."
똑똑하신(-_-;;) 여러분이 느낀 그대로다. 이 수열 F의 n번째 숫자 Fn은 그 전에 붙어있는 두 숫자 Fn-1과 Fn-2의 합으로 정해진다. 이것을 좀 수학적으로 나타내 보자.
F1 = 1 , F2 = 1
Fn = Fn-1 + Fn-2 (단, n≥3)
이것이 앞으로 우리가 이용해야 할 '점화식'이다. 사실 이런 류의 동적계획법 문제를 풀 때마다 이렇게 수학적인 식을 써야할 필요는 없다. 대충 '이 결과를 이렇게 더하면 저 결과가 되겠지'라고 머릿속으로 생각해놓고 코딩을 해도 답만 제대로 다온다면야 전혀 상관없다. 여기서는 여러분의 이해를 돕기위해 수학적으로 좀 놀아봤을 뿐이다.(-_-;;;)
그리고 여기서 하나 생각해 봐야 될 것이, 어떻게 답을 구해나갈 것인가 하는 점이다. 동적계획법은 이미 계산된 값을 가지고 그 다음 결과를 계산하기 때문에, 계산된 결과를 어떤 순서로 배열에 채워넣을 것인가 하는 것도 생각해 봐야 한다.
이 문제에서는 그냥 1부터 n까지 순서대로 쭉 구해 나가면 된다. (점화식을 보면 알겠지만 뒤에서부터 계산할 수는 없기 때문이다... 혹시 당신은 뒤에서부터 구하는 법을 알고있나?) 이 정도면 대충 감이 잡혔으리라 믿는다. 그럼 프로그램을 보자.
program Fibonacci;
const
n=10;
var
F : array[1..100] of integer;
i : integer;
begin
F[1]:=1;F[2]:=1; {점화식 이용}
for i:=3 to n do
F[i]:=F[i-1]+F[i-2]; {점화식 이용}
writeln(F[n]); {정답 출력}
end.
이 프로그램에서는 아까 잘 만들어 뒀던 점화식을 그대로 사용하고 있는 것을 알 수 있다.
|
3. 동적계획법의 실제 #2 |
이번에는 다른 문제를 하나 풀어보도록 하자. 이번 예제도 역시 너무 유명하다. '파스칼
의 삼각형 구하기'를 해보자. 혹시 파스칼의 삼각형을 모르는 사람은 있겠지.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
.
.
.
이런 모양의 숫자로 이루어진 삼각형이 다름 아닌 '파스칼의 삼각형'이다. 원래 이 삼각형은 이항정리와 관계있는 경우의 수를 구한 것이다. 하지만 이 이야기는 어려우니까 넘어가고. 우리는 본래의 목적에 충실해보자.
위 삼각형에서도 규칙을 찾을 수 있는가? 찾기 어렵다면 삼각형을 몇대 때려보자.
1 1
1 1 2
1 2 1 3
1 3 3 1 4
1 4 6 4 1 5
.
.
1 2 3 4 5
삼각형을 좀 찌그러지게 해 놓고 보니 규칙성이 보이는 것 같다.
일단 이 삼각형을 배열에 넣었다고 생각해 보자. 옆과 밑에 빨간 글씨로 써 놓은 숫자들은 배열의 첨자를 나타낸다. 배열첨자가 [4,3] 이면 4번째 줄 3번째에 위치한 숫자가 된다고 가정하자. 즉 이 삼각형 T에서 맨 꼭대기에 있는 1은 T[1,1]이고, 제일 밑에서 폼잡고 있는 6은 T[5,3]이 된다. 이렇게 되면 머릿속으로 점화식을 어떻게 세워야 할지 알 수 있을 것이다.
T[i,j] = 0 < j < i 일때 T[i,j] = T[i-1,j] + T[i-1,j-1]
j = 0 또는 j = i 일때 T[i,j]=1
점화식은 이렇게 만들어질 것이다.
그럼 이 식을 이용해서 배열을 어떻게 채워나가야 할까? 이것도 피보나치 수열처럼 첫번째 줄부터 마지막 줄까지 쭉 구해 나가야 할 것이다. 다음은 1부터 n번째 줄까지의 파스칼의 삼각형을 구하는 프로그램이다.
program pascal;
const
n=10;
var
T : array[1..100,1..100] of integer;
i,j : integer;
begin
for i:=1 to n do begin
for j:=1 to i do begin
if (j=1) or (j=i) then T[i,j]:=1 else T[i,j]:=T[i-1,j] + T[i-1,j-1]; {점화식 이용}
write(T[i,j]:5); {출력}
end;
writeln;
end;
end.
이번 프로그램 역시 점화식를 그대로 따라간다. 이해하는데는 별다른 어려움이 없을것이다.
|
4. 동적계획법과 최적화 원칙 |
이 세상 모든 문제들이 위와같은 방식으로 풀리면 얼마나 좋으랴. 그러나 세상은 그렇게 만만하지 않은 모양이다. 불행히도 세상에는 동적계획법으로 풀리지 않는 문제가 더 많다. 아무거나 동적계획법으로 풀면 안된다는 소리다.
그럼 동적계획법으로 풀 수 있는 문제와 풀지 못하는 문제를 어떻게 구분해야 잘 구분했다고 소문이 날까? 여기서 하나 알아둬야 할 것이 최적화의 원칙(principle of optimality)이다.
최적화의 원칙 : 어떤 큰 문제의 최적해는 그 문제에 속하는 부분문제의 최적해를 항상 포함한다.
이게 뭔 소린가는 예를 들어 설명하는 편이 더 쉬울것이다. 두 도시를 연결하는 최단경
로를 구하는 문제를 생각해보자. 밑의 그림을 보자.이 거대한 그림(그리다가 보니 그렇게 됐다-_-;;)을 보자. A도시에서 D도시까지 가는 최단경로는 파란색 실선이다. 그리고, 이 그림에서는 A에서 D까지 가는 최단경로가 "큰 문제"가 된다. 그렇다면 "그 문제에 속하는 부분문제"란 A에서 B까지, B에서 D까지 가는 경로가 될 것이다.
그리고 A에서 B까지 가는 경로나 A에서 D까지 가는 경로도 역시 따로따로 보면 최단경로다. 즉 이 문제는 최적화의 원칙이 성립하는것이다.
하지만 짜증스럽게도 최적화의 원칙이 성립하지 않는 문제도 많다. 옆의 그림에서 A에서 D까지의 최단경로가 아닌, A에서 출발해 다른 모든 소리를 한번씩 거쳐서 다시 A로 돌아오는 전국일주관광을 한다고 생각해보자. 이런 문제는 최적화의 원칙이 성립하지 않는다.(조금만 생각해 보면 알것이다)
항상 동적계획법으로 문제를 풀고자 할때는 최적화의 원칙이 성립하는지, 즉 동적계획법으로 풀 수 있는 문제인지를 미리 확인해야한다. 이는 동적계획법뿐만 아니라 모든 다른 알고리즘을 적용하려 할때도 마찬가지다. 어떤 알고리즘을 적용하려면 그 알고리즘을 적용할 수 있는 문제인가 하는것을 미리 생각해 봐야한다.
다음 회에서는 동적계획법을 이용해 문제를 푸는 방법을 좀더 자세히 알아보도록 하겠다.