알고리즘 강좌 3회
- 다이나믹 #2 -
|
4. 동적계획법의 실제 #3 |
자, 이번에도 역시 문제를 풀어봄으로서 동적계획법을 더 연습해 보자.
이번에 연습해 볼 문제도 역시 너무도 유명한 동적계획법 예제인 Knap sack문제이다. 설마 모르는 분이 있을까봐 문제설명을 드리자면.
소유권 이전 전문가(이하 도둑)가 직업인 동섭이는 어느 날 밤 귀금속 가게를 털었다. 숙련된 솜씨로 문을 따고 가게 안에 들어가 보니 오색찬란 금덩어리 은덩어리 보석덩어리 똥덩어리(엥~ 이건 아닌가) 등등 각종 덩어리들로 눈이 부실 지경이었다. 동섭의 마음 같아서는 몽땅 털어가고 싶지만 자신이 가져온 가방이 그렇게 큰 편이 되지 못했다. 그래서 가장 값을 높게 쳐주는 보석덩어리들만 가져가려고 한다. 동섭이 가장 비싸게 처분할 수 있도록 배낭을 채워주면 된다. 단, 보석덩어리들 마다 각각의 부피와 가격은 다르다. 이 보석가게는 워낙 크기때문에 보석은 제한 없이 얼마든지 가져갈 수 있다고 한다.
대충 이해가 되었을 것이다.
그럼 문제를 풀기 위해 생각해 보자.
일단 여기서는 배낭 전체을 채우는 것을 큰 문제, 배낭 일부를 채우는 것을 부분문제로 생각해 보면 문제 전체가 쉽게 풀린다.(사실 이것이 핵심이다)
그러면 이 문제는 최적화의 원칙이 성립하게 된다. 배낭전체를 채우는 것을 큰 문제, 배낭 일부를 채우는 것을 부분문제로 생각했으므로.
그러면 여기서는 배열을 어떻게 잡아야 할까. 위의 파란색 문장을 바탕으로 생각해보자. 감이 좀 오는가? 여기서 P라는 배열을 한번 정의해 보자.
P[i] = 배낭을 처음부터 i 부피만큼만을 채울 때의 얻을 수 있는 최대 값어치
그러니까 P[10]에는 10부피를 채우는 가장 값어치가 높게 되도록 보석을 넣었는때의 값어치가 들어갈 것이다.
여기까지 했으면 그 다음 점화식을 세워보자. 역시 저 위에 파란색 글귀를 생각하면 점화식을 만들 수 있을것이다. j번째 보석의 가격을 value[j], 부피를 size[j]라고 하고, 집어넣을 보석이 j번 보석이라고 한다면,
P[0] = 0
P[i] = maximum ( P[i - size[j]] + value[j] )
여기서 maximum(...)은 괄호 속에 올수 있는 값중 최대값을 나타낸다. 즉 모든 보석을 넣어봤을때의 가장 값어치가 많이 나가는 경우가 P[i]에 저장된다는 말이다.
점화식을 이용하려면 이번에도 역시 배열을 처음부터 차례대로 채워나가야 할 것 같다.
점화식까지 완성이 되었으면 이젠 프로그램을 짤 수 있다.
program knapsack;
const
n=5; {보석의 개수}
v=30; {배낭의 크기}
size : array[1..n] of integer =(5,10,20,4,8); {보석 한덩이의 크기}
value : array[1..n] of integer =(50,60,140,30,90); {보석 한덩이의 가치}
var
P : array[0..100] of integer;
i,j : integer;
begin
P[0]:=0;
for i:=1 to v do begin
for j:=1 to n do begin
if i-size[j]>=0 then begin {j번 보석이 i부피의 배낭에 들어갈 수 있으면}
if P[i] < P[i-size[j]] + value[j] then
P[i]:=P[i-size[j]] + value[j]; {점화식 이용}
end;
end;
end;
writeln(P[v]);
end.
자... 대충은 이해가 가리라고 믿는다. 이번에도 점화식을 그대로 이용했다. 배낭의 크기가 커지면 이 방법은 소용이 없지만 여기서는 동적계획법을 공부하게 위해 배낭의 최대크기를 100으로 잡았다.
|
5. 동적계획법의 실제 #4 |
한 문제 더 풀어보기로 하자. 이번에 풀 문제는 병신같이 딱히 이름이 없다.(--;) 여기서는 Up sequence문제라고 칭하겠다. 이 문제는 제목에서도 알 수 있듯 수열을 다룬다.
8 13 2 9 4 15 19
이와같이 별다른 규칙 없이 나가는 길이가 n인 수열이 있다고 한다. 문제는 이 수열에서 뒤로 갈 수록 점점 수가 증가되는(오름차순인) 또 다른 수열의 최대길이를 구하는 것이다. 이 수열에서의 오름차순 수열중 최대길이를 갖는것은
8 13 2 9 4 15 19
에서 빨간 글씨로 표시된 8,13,15,19 부분이다.(길이는 4) 또는 2,4,15,19의 경우도 길이가 4이므로 최대 길이를 갖는것이 된다. 하지만 13,15,19같은 것은 길이가 모자라므로 답이 될 수 없다.
수열 전체에서 답을 뽑아내는 것을 큰 문제, 수열의 일부에서 답을 뽑아내는 것을 작은 문제로 생각해보자.(이것이 이번 문제의 핵심이다) 그러면 이번에도 최적화의 원칙이 성립해 버리고 만다.
그러면 배열을 어떻게 정의해야 할까. 여기서 구하고자 하는게 수열의 최대 길이니까 아무래도 수열의 최대길이 L을 다음과 같이 정의하는게 좋겠다.
L[i] = i항으로 끝나는 오름차순 수열의 최대길이
그러니까 L[4]라고 하면 4항으로 끝나는 오름차순 수열의 최대길이이다. 그 숫자는 2가 되겠군.(2,9가 오름차순이므로) 이번에도 차례대로 배열을 채워야 하겠다. 수열의 1항부터 끝항까지 차례대로 오름차순이 되어야 하니까.
이제 점화식을 세울 차례다.
L[1] = 1
L[i] = maximum( L[j]+1 )
이번엔 점화식이 비교적 간단하다. 즉 수열 길이를 하나씩 증가시켜 가면서 지금까지의 최적해에다 더할 수 있으면 더하는 것이다. 프로그램을 짜 보자.
program Up_sequence;
const
n=7;
seq : array[1..n] of integer=(8,13,2,9,4,15,19);
var
L : array[1..100] of integer;
i,j : integer;
max : integer;
begin
L[1]:=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;
{최대값 찾기 : 그 이유는 밑에서 설명}
max:=0;
for i:=1 to n do
if
max
writeln(max);
end.
마지막에 배열L의 요소 중에서 최대값을 출력한 것을 눈여겨 보기를 바란다. 오름차순 수열이 몇 항에서 끝날지 모르므로 최대값을 구한 것이다. 이 소스도 위의 Knapsack문제 소스와 구조가 비슷하다.
|
6. 연습문제 |
이제 동적계획법의 기초는 익혔다. 심화학습을 위해 다음 문제를 풀어보자.
이 문제의 풀이는 다음회에 상세히 나올 것이다.
방금 풀었던 Up sequence문제를 기억하시는지? 이번 문제는 아까 푼 그 문제의 2차원 버젼이다. 참고로 이 문제는 정보올림피아드계의 이름난 분 중 한 사람인 한상진 님이 만드셨던 문제이다.(저작권을 보호하자!-_-;;) 여기서의 수열은 가로 n, 세로 n크기의 정사각형으로 주어진다.
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
여기서도 오름차순 수열을 찾을 수 있다. 단, 이번에 찾을 오름차순 수열의 숫자들은 오른쪽과 아래쪽으로만 가면서 찾아야 한다.(대각선, 그러니까 오른쪽 아래방향으로 갈 수 있다) 이 데이터에서의 답은
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
빨간색으로 표시된 부분으로 그 길이는 7이다. 1,5,9,19같은 경우도 조건은 만족하나 길이가 딸린다. 이런식으로 주어지는 정사각형 수열에서 가장 길이가 긴 오름차순 수열의 길이를 구하여라. 입력, 출력은 파일로 하든 상수선언을 하든 화면을 이용하든 각자 알아서 하기를 바란다.