알고리즘 강좌 2회

알고리즘 강좌 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)이다.

 

최적화의 원칙 : 어떤 큰 문제의 최적해는 그 문제에 속하는 부분문제의 최적해를 항상 포함한다.

 

이게 뭔 소린가는 예를 들어 설명하는 편이 더 쉬울것이다. 두 도시를 연결하는 최단경

로를 구하는 문제를 생각해보자. 항상 동적계획법으로 문제를 풀고자 할때는 최적화의 원칙이 성립하는지, 즉 동적계획법으로 풀 수 있는 문제인지를 미리 확인해야한다. 이는 동적계획법뿐만 아니라 모든 다른 알고리즘을 적용하려 할때도 마찬가지다. 어떤 알고리즘을 적용하려면 그 알고리즘을 적용할 수 있는 문제인가 하는것을 미리 생각해 봐야한다.

다음 회에서는 동적계획법을 이용해 문제를 푸는 방법을 좀더 자세히 알아보도록 하겠다.