그리디(Greedy) 알고리즘

그리디 알고리즘?

사전 상 그리디(greedy)는 탐욕스러운, 욕심 많은이라는 뜻을 가진 영단어이다.

그리디 알고리즘은 이러한 뜻과 같이 욕심 많은 알고리즘이다. 이게 무슨 말이냐 하면 그리디 알고리즘을 사용하면 선택의 기로에 놓일 때마다 닥칠 미래 같은건 생각하지 않고, 오직 최선의 방법만 선택하여 최종 해답을 구하게 된다.

하지만, 모든 문제에서 이러한 그리디 알고리즘으로 최적의 결과를 찾을 수 있는 것은 아닌데, 그리디 알고리즘을 적용하기 위해서는 문제가 다음 두 가지 조건을 만족해야한다.

탐욕스런 선택 조건(Greedy Choice Property)

탐욕스런 선택 조건이란 앞선 선택의 결과가 이후의 선택에 영향을 주지 않는다라는 것을 뜻한다.

즉, 항상 탐욕스런 선택(최선의 선택)만 하더라도 최적의 결과를 얻을 수 있다는 뜻이다.

최적 부분 구조 조건(Optimal Substructure)

각 부분 문제의 최적해를 가지고 전체 문제의 최적해를 구할 수 있을 때 최적 부분 구조 조건이 성립한다고 한다.

이게 무슨 말이냐하면, 예를 들어 피보나치 수열의 식은 다음과 같이 구성되어 있는데

fibo(n) = fibo(n - 1) + fibo(n - 2);

전체 문제(fibo(n))이 최적해가 되려면 부분 문제(fibo(n-1) + fibo(n-2))가 최적이 되어야한다. 즉, 피보나치 수열은 최적 부분 구조 조건을 성립한다.

간단 예제로 알아보는 그리디 알고리즘

자, 이제 그리디 알고리즘에 대해 어느정도 알았으니 실전에서 사용할 수 있는 간단한 예제를 이용하여 그리디 알고리즘에 익숙해져보자.

거스름돈 문제

문제 상황

겜마고 학생 도윤이는 방학동안 편의점에서 아르바이트를 하려고 한다. 도윤이가 담당하게 된 첫 업무는 계산 업무! 손님으로 온 부성이는 과자 2봉지와 음료수 3개를 골라 총 가격은 7,800원이 나왔고, 부성이는 계산을 위해 10,000원을 내밀었다. 평소 알고리즘을 좋아하던 도윤이는 동전의 갯수를 최소한으로 하여 거스름돈을 주고 싶다.

해결 과정

1. 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 선택한다.
2. 선택된 동전의 합이 목표 거스름돈을 초과하는지 확인한다.
3. 초과한다면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택하게 된다.
4. 선택된 동전들의 합이 최종 거스름돈과 일치하는지 확인한다.
5. 액수가 부족하다면 1번으로 돌아가 다시 진행한다.

결론

정리하자면 가장 가치가 높은 동전을 먼저 거슬러주고 남은 잔액에 맞추어 순서대로 거슬러주면 된다.

---

기차 문제

문제 상황

겜마고 학생 도윤이는 방학 중 호실 친구들과 함께 부산으로 여행을 떠나기로 한다! 도윤이와 친구들은 우선 학교에서 모여 광명역으로 이동한 후 ktx를 타고 부산역으로 이동하려고 한다. MBTI가 J인 도윤이는 여행 전날 버스와 ktx의 정보를 확인하여 가장 빠르게 부산에 도착할 수 있는 경로를 짜려고 한다.

버스와 ktx의 정보는 다음과 같다.

버스 정보

버스 번호	소요 시간	가격
1번 버스	30분	3,000원
2번 버스	25분	3,000원
3번 버스	45분	3,000원

KTX 정보

KTX 번호	소요 시간	가격
1번 KTX	3시간	100,000원
2번 KTX	4시간	100,000원
3번 KTX	2시간 30분	100,000원

해결 과정

1. 학교에서 광명역으로 이동하는 버스 중 소요시간이 가장 적은 버스를 선택한다.
2. 광명역에서 부산역으로 이동하는 ktx 중 소요시간이 가장 적은 버스를 선택한다.
3. 경로를 출력한다.

결론

학교 -> 부산 까지의 효율적인 경로를 알려면 학교 -> 광명역의 효율적인 경로와 광명역 -> 부산역의 효율적인 경로를 알아낸 뒤 그것을 더하면 된다.