알고리즘 강좌 4회

목차

이글은 알고리즘에 대한 강좌입니다.

본문내용

디버그해서 하나하나 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] if L[i] L[i]:=L[j]+1; {점화식 이용}
trace[i]:=j; {L[i]의 값의 고향(?)을 저
장}
end;
end
end;
end;
{최대값 구하기 : 정답 찾기}
max:=-maxint;
for i:=1 to n do
if max 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' 즉 빙산의 일각에 지나지 않는다. 보다 중요하것은 실제로 문제를 많이 풀어보는 것이다. 특히 동적계획법 문제는 다른 문제들과 비해서 과연 이게 동적계획법을 이용해서 풀리는 문제인지 구분하기 힘들다. 이런 것을 척 보고 구분할 수 있으려면.. 문제를 많이 풀어보는 수밖에 없다.
부족한점이 많은 강좌였지만 이 강좌를 보고 동적계획법에 대해 약간이라도 이해를 했기를 바란다. 다음회부터는 그리디 알고리즘에 대해 알아도록 하겠다.
-------------------------------------------------------------------------------------
드디어 다이나믹 강좌가 끝을 맺었군요.
Q/A 게시판에 썰렁하네요. 이 강좌에는 질문꺼리조차 없어서 그런가요?^^

키워드

알고리즘,   강좌,   다이나믹,   연습문제,   동적계획법,   1차원