알고리즘 강좌 4회

- 다이나믹 #3 -

 

7. 연습문제 풀이

 

자, 지난번 강좌에 나왔던 연습문제는 푸셨는가?

그럼 풀이법에 대해 설명하도록 하겠다.

이 문제도 동적계획법으로 풀린다.(당연하지.. 동적계획법 강좌에 나온 문젠데) 풀이법은 1차원 Up sequence문제와 별로 다를 것이 없다. 우선 이차원 배열 L(2차원 버젼이므로)을 다음과 같이 잡는다.

 

L[i , j] = i행 j열에 있는 숫자로 끝나는 오름차순 수열의 최대길이

 

1차원 버젼과 별로 다르지 않다.

그럼 점화식은?

 

L[i , j] = 1

L[i , j] = maximum( L[k1 , k2] + 1 )

 

역시 1차원 버젼과 다를것은 별로 없다.(음.. 그러고 보니 "다를것이 없다"라는 말을 지난 강좌에서부터 너무 많이 쓰고 있는 듯..-_-) 그 전까지의 최대길이에 조건을 만족할 경우 +1해주면 되는 것이다.

그럼 소스를 보자.

 

program Upsequence_2D;

const

n=5;

data : array[1..n,1..n] of integer =(

(1,2,3,4,5),

(8,5,4,10,9),

(7,2,9,3,20),

(21,22,6,19,11),

(10,5,20,12,11)

);

var

L : array[1..n,1..n] of integer;

i,j,k1,k2 : integer;

max : integer;

 

begin

L[1,1]:=1;

for i:=1 to n do begin

for j:=1 to n do begin

if i+j=2 then inc(j);{L[1,1] 은 처리할 필요가 없으므로}

 

for k1:=1 to i do begin

for k2:=1 to j do begin

if (k1=i) and (k2=j) then break;{자기 자신 L[i,j]은 계산에서 제외}

 

if data[i,j]>data[k1,k2] then begin{조건에 맞으면}

if L[i,j]<L[k1,k2]+1 then begin

L[i,j]:=L[k1,k2]+1;{점화식 이용}

end;

end;

 

end;

end;

end;

end;

max:=0;

for i:=1 to n do begin

for j:=1 to n do begin

if max<L[i,j] then

max:=L[i,j];

end;

end;

writeln(max);

end.

 

휴~ 길다. 작성해놓고 보니 1차원 버젼이랑 별다른 차이가 없다.(또...!--;;)

 

8. 추적

추적.. 영어로는 trace라고들 한다.

동적계획법에서는 추적도 상당히 중요한 부분을 차지한다.

지금까지 우리는 '최적해'만을 출력했다. 하지만 실제 문제에서는 그 최적해가 어떻게 해서 구성 되는지도 구해야 할 때가 매우 많다. 예를 들면 Up sequence문제에서 오름차순 수열의 최대길이말고도 최대길이를 갖는 오름차순 자체를 구하라고 요구하는 경우다. 사실 이렇게 답이 어떻게 구성되어 있는지를 구하는 방법은 여러가지가 있다. 하지만 여기서는 필자가 쓰는 방법만 간단히 소개하기로 한다.

동적계획법에서는 최적해를 구성하는 경로가 쭉 이어져서 나오는 경우가 대부분이다. Up sequence같은 경우도 1->3 , 3->9 , 9->13, ... 뭐 이런 식으로 연달아 이어져서 나온다. 문제의 이런 성질을 이용해 경로를 추적할 수 있다.

우선 추적할 경로를 저장하는 배열을 잡아보자.

 

trace : array[1..n] of integer;

 

보통 추적하는 배열은 동적계획법의 최적해가 들어가는 배열과 똑같은 크기로 잡는다.

Up sequence 1차원 버젼에 보면 다음과 같은 부분이 있다.

 

for i:=2 to n do begin

for j:=1 to i-1 do begin

if seq[i]>seq[j] then begin{i항의 숫자가 오름차순 수열이 될수 있다면}

if L[i] < L[j] + 1 then begin

L[i] := L[j] + 1;

...

end;

end;

end;

end;

 

그럼 ...부분에 추적 경로를 집어넣는 명령을 써 주는 것이다. 다음과 같이 써 주면 OK.

 

for i:=2 to n do begin

for j:=1 to i-1 do begin

if seq[i]>seq[j] then begin{i항의 숫자가 오름차순 수열이 될수 있다면}

if L[i] < L[j] + 1 then begin

L[i] := L[j] + 1;

trace[i]:=j;

end;

end;

end;

end;

 

즉 trace[i]에는 최적해 L[i]가 유래한 위치(여기서는 배열의 첨자)를 집어 넣어 주는 것이다. (앞으로 L[i]가 유래한 위치를 고향-_-; 이라고 칭하겠다)

이제 다음과 같은 루틴을 집어넣으면 추적은 완성된다.

 

result : array[1..n] of integer;{최적해의 경로를 최종적으로 저장할 배열}

t,c : integer;

 

c:=0;t:=maxp;{maxp는 배열 중 최적해의 첨자}

repeat

inc(c);

result[c]:=data[t];{경로 저장}

t:=trace[t];{정답의 고향(--;)을 쫓아감}

until t=0;

 

이렇게만 써 놓으면 무슨 소린지 이해가 잘 안갈 것이다. 이것에 대해서 개념적으로 자세히 설명하기는 힘들다. 아래에는 Up sequence 1차원 버젼을 경로 추적까지 해서 수열의 최대길이와 그 수열자체도 출력하도록 해 놓은 소스가 나와있다. 잘 모르겠다면 이 소스를 파스칼 통합환경에서 디버그해서 하나하나 trace해보도록 하자.(그것도 추적이고 이것도 추적이다--;)

 

program Upsequence;

const

n=7;

data : array[1..n] of integer =(

8,13,2,9,4,15,19

);

var

L,trace,result: array[1..n] of integer;

 

i,j : integer;

max,maxp : integer;

begin

L[1]:=1;

for i:=2 to n do begin

for j:=1 to i-1 do begin

if data[j]<data[i] then begin

if L[i]<L[j]+1 then begin

L[i]:=L[j]+1; {점화식 이용}

trace[i]:=j; {L[i]의 값의 고향(?)을 저

장}

end;

end

end;

end;

{최대값 구하기 : 정답 찾기}

max:=-maxint;

for i:=1 to n do

if max<L[i] then begin

max:=L[i];

maxp:=i;

end;

{추적부분}

i:=maxp;j:=0;

repeat

inc(j);

result[j]:=i; {결과 출력용으로 저장}

i:=trace[i]; {정답의 고향(??)을 계속 찾아감}

until i=0;

{출력부분}

writeln(max);

for i:=max downto 1 do

write(data[result[i]],' ');

 

end.

 

이런 정도의 추적만 능숙히 할 수 있으면 실전에서도 상당히 도움이 될 것이다.

9. 정리

 

이상으로 동적계획법에 대해 어느정도 알아보았다. 하지만 지금껏 내가 설명한 것은 'the tip of the iceberg' 즉 빙산의 일각에 지나지 않는다. 보다 중요하것은 실제로 문제를 많이 풀어보는 것이다. 특히 동적계획법 문제는 다른 문제들과 비해서 과연 이게 동적계획법을 이용해서 풀리는 문제인지 구분하기 힘들다. 이런 것을 척 보고 구분할 수 있으려면.. 문제를 많이 풀어보는 수밖에 없다.

부족한점이 많은 강좌였지만 이 강좌를 보고 동적계획법에 대해 약간이라도 이해를 했기를 바란다. 다음회부터는 그리디 알고리즘에 대해 알아도록 하겠다.