- 그리디 #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
알고리즘 강좌 5회  (1) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27
  1. pr 2019.06.25 11:16

    가장 화폐의 수가 적은 경우는 1100원 1장 1000원 1장 500원 1개
    총 화폐 3개...

+ Recent posts