[Algorithm] Greedy algorithm - 탐욕 알고리즘

탐욕 알고리즘은 현재 주어진 상황에서 최적의 값을 골라 결과를 채우는 알고리즘을 말한다. 가장 많은 예시인 배낭 채우기는 간단하게 설명하고, 다른 예시를 보도록 하자. 탐욕 알고리즘은 그 이름에서 유추할 수 있듯이 욕심쟁이라면 당연히 따를 법한 알고리즘이다.

 

배낭 채우기

 

( 갑자기 ) 우리는 도둑이다. 도둑이라면 응당 가장 비싼 물건을 훔쳐야 할 것이다. 맥북을 훔치기 위해 도둑이지만, 일반 고객인 척 위장하여 애플매장을 방문하였다.

 

우리에게는 남들에게는 보이지 않는 마법의 '배낭' ( 혹은 가방 ) 이 있다. 이 배낭은 보이지않는 대신에 너무 작게 만들어져서 중량 초과를 할 경우 밑바닥이 터져버린다! ( 요즘 종이 가방도 이것보단 튼튼하겠다! )

 

내 배낭이 버틸 수 있는 총 중량과 애플매장에서 훔칠 수 있는 상품은 아래와 같다.

 

이름	중량	가격
마법의 배낭	3kg	-
맥북프로 2020 special edition	1.7kg	500만원
맥북프로 2019 basic	1.6kg	200만원
맥북에어	0.6kg	100만원
아이패드 프로	0.7kg	120만원
애플펜슬	0.1kg	40만원
아이폰 Max Pro	0.6kg	250만원
애플워치	0.2kg	50만원
아이패드 3	0.5kg	80만원

어떤 물건을 훔쳐야 가장 비싸게 훔칠 수 있을까?

 

직관적으로 생각해보자. 가장 비싼 물건을 챙겨야 하니까 맥북프로 2020 스페셜 에디션은 반드시 챙겨야 할 것 같다. 추가로, 아이폰은 무게 대비 가격이 비싸다. 이렇게 두 가지를 먼저 선택하면 750만 원어치를 훔쳤지만 여전히 0.7kg의 공간이 남는다! 어떤 제품을 더 훔치면 가장 만족스러운 금액을 훔칠 수 있을까?

 

현재까지의 훔칠예정인 목록은 다음과 같다.

이름	중량	가격
맥북프로 2020 special edition	1.7kg	500만원
아이폰 Max Pro	0.6kg	250만원

여기에 추가로 무엇을 훔칠 수 있을까? 남은 중량이 0.7kg 이므로, 0.7kg 이하의 최종 상품은 다음과 같다.

후보	품명	중량	가격
1	아이패드 프로	0.7kg	120만원
2	맥북에어 + 애플펜슬	0.7kg	140만원
3	아이패드3 + 애플워치	0.7kg	130만원

우리는 가장 비싼 물건을 훔치길 원하므로 위의 3가지 조합 중에서 2번인 맥북에어와 애플펜슬을 배낭에 몰래 넣어야 한다.

이처럼 가장 비싼물건, 혹은 비슷하게 가장 무겁거나 가벼운 물건과 같이 현재 상황에서의 최적의 해를 선택하는 것이 탐욕 알고리즘의 핵심이다.

 

다른 예를 들어보자.

 

시간표 짜기

그 옛날 수강신청을 하기 전, 어떤 과목을 신청할 지 정해야 하던 때를 떠올려 보자. 징검다리는 싫으니까 수업이 있는 날에는 강의 없이 시간이 뜨는 경우는 없어야하고, 월요일이나 금요일 중 하루는 쉬어줘야 과제나 스터디 혹은 여행을 할 수 있을 테니까 금공강 또는 월공강을 만들어야 한다. 밤새 놀다가 오전에만 수업을 듣고 하루종일 자야하니까 오전 시간표만 짜보자. 아래와 같은 수강계획표가 있다면 어떤 시간표를 만들 수 있을까?

수업	시작	종료
미술	9:00 am	10:00 am
영어	9:30 am	10:30 am
컴퓨터	10:00 am	11:00 am
수학	10:30 am	11:30 am
음악	11:00 am	12:00 pm

일단, 시간이 겹치기 때문에 모든 과목을 수강할 수는 없다. 오전에 되도록 많이 들어야 오후 시간을 비울 수 있다.

 

이 문제는 너무도 간단하게 해결이 된다. 종료시간이 가장 빠른 수업을 기준으로 선택하면 되기 때문이다.

1. 10시에 미술이 끝난다.
2. 미술과 시간이 겹치지 않는 과목 중 가장 빨리 끝나는 과목인 컴퓨터를 고른다.
3. 컴퓨터와 시간이 겹치지않는 과목 중 가장 빨리 끝나는 과목인 음악을 고른다.
4. 끝

탐욕 알고리즘은 현재의 상황에서 최적의 해를 구하기때문에, 9시를 기준으로 가장 빨리 마치는 과목을 고르고, 해당 과목이 끝난 시점에 시작하지 않은 수업 중 가장 빨리 마치는 과목을 고르는 방식을 계속해서 취하므로써 우리는 아주 간단하게 시간표를 작성할 수 있다.