욕심쟁이(Greedy) 알고리즘

출처 : http://blog.naver.com/dekucug/100105148371

먹고, 먹고, 또 쳐먹고. 욕심쟁이(그리디) 알고리즘

사실 이번 알고리즘의 90% 이상이 이름에 들어있습니다. 모든 알고리즘이 그런 형식이기는 하지요. Greedy란, 욕심이 많은, 탐욕스러운 이라는 뜻입니다. 그럼 대체 욕심많은 알고리즘이 무엇이냐? 컴퓨터가 어떻게 욕심을 부려서 문제를 풀 수 있다는 것일까요?

사실 이 알고리즘은 상당히 사람틱하달까, 인공지능 틱하다고 말 할수 있습니다. 간단하게, 한가지의 예를 들어 볼테니 여러분들이 한번 이 문제를 풀어보십시오.

	방금 커맨드센터에서 SCV 한기가 나왔다. 당신은 그 SCV을 시켜 미네랄을 채취하게 하고 싶다. 미네랄이 총 3개 A, B, C 가있는데, 각각의 커맨드센터로 부터의 거리는 10m, 15m, 30m 이다. 이때 당신은 어느 미네랄으로 SCV를 보내는 것이 좋을까?

직관적으로 생각해 보면, 당연히 제일 가까운 10m 미네랄로 보내는 것이 옳습니다.

바로 방금, 당신은 Greedy 알고리즘을 이용한 것이지요. 단순히 욕심을 내서, 제일 가까운 미네랄로 보낸 것이니까요. 만약 욕심을 내지 않았더라면, 어디의 미네랄이든 상관 없겠지요. 만약 이번엔 거리는 다 똑같고, 각각의 자원량이 100,2000,5000 이였다면, 5000 미네랄을 선택하였겠지요. 정말 쉽습니다. 그냥 가장 좋은 방법을 택하는 것, 이것이 바로 그리디 알고리즘인 것입니다.

허나, 우리 인생을 이렇게 그리디 알고리즘으로 살면 어떻게 될까요.

분명히 망하겠지요. 그리디 알고리즘은 최적의 해가 나오기가 힘듭니다. 왜냐하면 그리디 알고리즘은 전혀 뒷일을 생각하지 않기 때문입니다. 사실 그리디 알고리즘의 정확한 의미는, '현재'상태에서 가장 좋은 방법을 택하는 것 입니다. 다시 위의 SCV 문제로 돌아가 봅시다.

분명히 위의 상황에서 가장 좋은 방법은 10m 미네랄을 선택하는 것, 그 뿐입니다. 허나 아까 말했듯이, 그리디 알고리즘은 미래를 고려하지 않습니다. 좋아라 하면서 냅다 10m 미네랄로 채취를 보냈더니, 갑자기 버로우한 저글링이 튀어나온다면 ?! 차라리 30m가는 것 만 못한 결과가 되는 것이지요.

가장 좋은것은 아니더라도 ...

사실 올림피아드 같은 최적해를 요구하는 문제풀이에서, 그리디 알고리즘은 거의 쓰이는 일이 없습니다. 그리디는 최적해가 아닌, 좋은해를 찾아주는 알고리즘이기 때문입니다. 허나 어떤 게임의 CPU 인공지능을 만드는데는 도움이 될 지도 모르지요. 왜냐하면, 인간의 사고방식을 참고한 알고리즘이니까요. 만약 이 그리디 알고리즘에, 백트래킹 알고리즘을 살짝 가미시키면 간단한 체스 인공지능 정도는 만들 수 있는겁니다. ( 우선 백트래킹(가능한 경우의 수를 체크하는것)을 이용해 자기가 갈수 있거나, 먹을수 있는 말의 갯수라던가 등의 조건을 첨가시키고 그리디를 살짝 이용하면 되겠지요. )

그렇게 생각해 보면 그리디 알고리즘은 결코 나쁜 알고리즘이라고는 할 수 없습니다. 구현하기도 쉽고, 상당히 좋은 해를 찾아주므로 오히려 좋은 알고리즘 쪽에 속한다고 볼 수도 있겠지요. 사실 올림피아드 같은 문제를 보면 제일 먼저 떠오르는것이 그리디 알고리즘입니다. 거의 대부분의 문제가 최대 또는 최소를 요구하는 문제니까요.

이런 그리디 틱한 알고리즘을 제일 먼저 생각나게 하는 문제의 유형이 몇가지 있습니다. 이미 카이스트 학습자료에도 나와 있지요. 가방 안에 가장 비싼 보석들을 담는 문제, 회의를 가장 많이 하는 문제, 행렬 내에서 연속된 연산의 최대/최소 값이라던가...

사실 그리디를 씀으로써 항상 최적해가 나오는 문제 유형이 있긴 있습니다. 대표적으로 스케쥴링 문제이지요.( 하루동안 총 몇번의 회의를 가질수 있는가 하는 문제. 예를들어 1번회의_1시~2시, 2번회의 3시~4시 라면 당연하 2개가 최대의 회의 갯수입니다 ) 이는 자료에서도 다루었고, 문제에서도 출제되었습니다. 이 문제에서 중점적으로 그리디 하게 보아야 할 것은 회의의 갯수이므로, 우선 끝나는 시간대이 빠른대로 정렬한 후, 첫번째 회의를 선택 한 뒤 그다음으로 제일 먼저 시작하는 회의를 구하면 당연히 최적해가 나옵니다. 조금만 생각해 보시면 그것이 당연하다는 것을 느끼실 수 있습니다. 스케쥴링 알고리즘의 작동 방식은 그냥 통안에 휴지들을 꾸깃꾸깃 집어넣는 방식이니까요.

이번 알고리즘은 별로 다룰게 없어서 짧게 끝났내요. 결국 그리디 알고리즘을 요약하자면,

1. 가장 좋은것을 선택하라.(물론 이때 좋은것을 선택하는 기준이 제일 중요함)

2. 항상 최적해를 보장하지는 않는다.