본문 바로가기

Computer Science/Algorithm

알고리즘 강좌 5회

728x90

- 그리디 #1 -

 

 

1. 그리디(Greedy)란?

 

이번에 우리가 공부해 볼 알고리즘은 그리디(Greedy)이다.

간단히 그리디에 대해 알아보면, 어원 그대로 상당히 탐욕적임을 느낄 수 있을 것이다. 그리디 알고리즘의 핵심은, 몇번의 선택을 하면서 답을 찾아내는데, 그 선택은 전에 결정했거나 앞으로 결정할 선택을 고려하지 않고, 그 당시의 상황에서만 가장 최적인 해를 취하는 것을 의미한다. 이런 과정을 거치기 때문에 그리디 알고리즘은 또 다른 중요한 특징을 가진다. 각 선택들은 부분적으로는 최적일지 모르나 전체적으로 보면 최적이 아닐 수도 있다는 점이다. 그래서 그리디 알고리즘을 쓸 때는 ‘전체적으로도 최적이 되는가?’ 라고 한 번 다시 생각해 봐야한다.

...이렇게 말해놓으면 무슨 소린지 잘 모르는 사람도 많을 것 같다. 다음 장에서 실제 문제에 적용시키면서 공부해 보면 이해가 잘 될 것이다.

 

2. 그리디의 실제#1

 

그리디의 간단한 예를 살펴보도록 하자.

동섭이는 모 슈퍼마켓의 점원으로 아르바이트를 하게 되었다. 계산대에 서서 손님들이 물건을 사면 돈을 받고 거스름돈을 주는 게 동섭이의 일이다. 그런데 너무나 당연한 소리지만, 거스름돈은 돈의 개수를 최소한 적게 해서 주는 것이 좋다. 즉, 거스름돈으로 2250원을 주어야 한다면, 천원짜리 두 장, 백원짜리 두 개, 오십원짜리 한 개 이렇게 총 다섯개로 최대한 줄여서 줘야지, 십원짜리 동전 225개를 확 던져주면 안된다는 소리다.

이 문제는 그리디 알고리즘으로 해결 할 수 있다.

우선 가장 단위가 큰 화폐를 선택한다. 그리고 이렇게 선택한 화폐가 손님한테 줘야할 거스름돈보다 크면 두번째로 단위가 큰 화폐를 선택한다.(거스름돈이 2250원인데 만원짜리 지폐를 거스름돈으로 줄 수는 없는 노릇 아닌가!) 이런식으로 더 줘야할 거스름돈보다 크지 않은 화폐를 선택한다. 이러한 과정을 손님한테 줘야할 거스름돈이 더 없을때 까지 계속한다.

이러한 일련의 과정을 이해하는 것은 별로 어렵지 않을 것이다.(나중에 보면 알겠지만 그리디 알고리즘을 적용하는 문제들은 대부분 “쉽다”.) 이 소스도 역시 쉽다.

 

program ____charge____;

const

money : array[1..5] of integer = (1000,500,100,50,10);

var

result : array[1..5] of integer;

charge : integer;

i : integer;

begin

charge:=2250;{주어야 할 거스름 돈}

 

repeat

for i:=1 to 5 do begin

if charge>=money[i] then break;

end;

 

inc(result[i]);

dec(charge,money[i]);

until charge=0;

 

for i:=1 to 5 do begin

writeln(money[i]:4,'원 짜리 ',result[i],'개');

end;

end.

 

여기는 워낙 쉬워서 별로 설명할 건덕지도 없다.

 

3. 주의할 점

 

앞에서 한 번 말했던 바와 같이, 그리디 알고리즘은 부분적으로는 최적의 해를 가져다 줄 지 모르나 전체적으로도 항상 최적의 해를 가져다 주지는 못할 수도 있다. 위의 거스름돈 주기 문제를 생각해 보자.

위 문제의 상황을 조금 바꿔서, 한국은행에서 새로운 1100원 짜리 화폐를 만들었다고 가정해보자. 그리고 주어야 할 거스름돈을 2600원이라고 하자. 이 때 위의 방법으로 거스름돈을 준다면? 1100원 짜리 2장 + 100원 짜리 4개 = 총 화폐 6개. 하지만 이건 아시다시피 최적해가 아니다. 가장 화폐의 수가 적은 경우는 1000원 짜리 2장 + 500원 짜리 1개 + 100원 짜리 1개 = 총 화폐 4개이다. 그리디 알고리즘의 맹점을 단적으로 보여주는 예다. 그리디 알고리즘을 쓸 때는 항상 전체적으로도 최적의 해가 나오는지를 꼭 생각해 봐야 한다.

 

4. 그리디의 실제 #2

 

최소비용 신장 트리(Minimum Spanning Tree)에 대해서 아는가? 여기서는 최소비용 신장트리(이하 MST)를 구하는 그리디 알고리즘을 설명하겠다.

MST를 간단히 정의하면 “그래프 상의 모든 정점을 연결하는 가장 짧은 이음선들의 집합”이라고 말할 수 있다. 다음 그림을 보자.

 

이것도 그림이냐! 라고 하시는 분이 혹시 있을지 모르겠다. 미안타.-_-; 나한테 그림에 관해서는 시비를 걸지 말아달라-_-;;

그림 2를 보면, 그래프 G의 모든 정점(A,B,C,D,E)를 모두 연결할 수 있으면서 그 길이의 합이 최소(1+3+4+2=10)인 선들이 굵은 선으로 나타나 있다. 그림 2의 굵은 선과 같은 선들의 집합을 MST라고 하는 것이다. (MST에 대해 더 자세한 것은 앞으로 올라올 초급 알고리즘 강좌를 참고하시길.)

그래프 G가 주어질 때 MST를 찾는 알고리즘은 크게 두가지가 있는데, Prim의 알고리즘과 Kruskal의 알고리즘이 그것이다. 두 알고리즘 모두 그리디를 응용한 것인데, 여기서는 이해하기 쉬운 Prim의 알고리즘을 공부해보자.

 

위 그림을 예로 들어 설명하겠다. 우선 그래프상의 점을 아무거나 하나 잡는다. 편의상 A로 잡아본다. 그리고 이렇게 잡아서 MST를 만들게 될 정점들을 {}로 묶어서 표시해 보자. 우선 A를 잡았으므로 {A} 이다.

그 다음, {}에 속하는 정점들 중에서 가장 가까운 정점을 또 선택한다. A와 가장 가까운 곳은 거리가 1인 B이다. 그러면 선택한 정점이 하나 늘어나서 {A,B}가 된다.

이제 {}에 속하는 정점에서 가장 가까운 정점을 선택하는 과정을 반복하면 된다. {A,B}에서 가장 가까운 곳은 거리가 1인 C이다. {A,B,C}까지 선택되었다.

{A,B,C}에서 가장 가까운 정점은 거리가 2인 E이다. {A,B,C,E}가 되었다. 마지막으로 {A,B,C,E}와 가장 가까운 정점은 거리가 4인 D이다. {A,B,C,E,D}가 되어 모든 정점이 연결되었으므로 MST는 완성이다.

아래 소스는 위 과정을 그대로 코딩한 것이다. 여기서 출력은 MST의 길이이다.

 

program __Mininum_Spanning_Tree__;

const

n=5;{정점의 개수}

 

{그래프의 상태에 대한 데이터.

D[i,j]<>0 이면 정점i와 정점j간의 거리는 D[i,j]이고,

D[i,j]=0 이면 정점i와 정점j을 연결하는 이음선이 없다는 뜻}

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

(0,1,3,0,0),

(1,0,3,6,0),

(3,3,0,4,2),

(0,6,4,0,5),

(0,0,2,5,0)

);

 

var

tree,selected : array[1..n] of integer;

i,j,k : integer;

min,edge : integer;

sum : integer;

begin

tree[1]:=1;{정점A를 선택}

selected[1]:=1;

 

for i:=2 to n do begin

 

min:=maxint;

for j:=1 to i-1 do begin

for k:=1 to n do begin

if (D[tree[j],k]<min) and (D[tree[j],k]<>0)

and (selected[k]=0) then begin

{가장 가까운 선택되지 않은 정점을 찾는다}

min:=D[tree[j],k];

edge:=k;

end;

end;

end;

 

inc(sum,min);

tree[i]:=edge;{정점 추가}

selected[tree[i]]:=1;

 

end;

 

writeln(sum);

 

end.

 

실제로 Prim의 알고리즘은 시간복잡도가 n2이지만 여기서는 이해를 편하게 할 목적으로 조금 풀어서 코딩했기때문에 n3이 되고 말았다(-_-;;)

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 강좌 7회  (0) 2010.11.28
알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27