사전 상 그리디(greedy)는 탐욕스러운, 욕심 많은이라는 뜻을 가진 영단어이다.
그리디 알고리즘은 이러한 뜻과 같이 욕심 많은 알고리즘이다. 이게 무슨 말이냐 하면 그리디 알고리즘을 사용하면 선택의 기로에 놓일 때마다 닥칠 미래 같은건 생각하지 않고, 오직 최선의 방법만 선택하여 최종 해답을 구하게 된다.
하지만, 모든 문제에서 이러한 그리디 알고리즘으로 최적의 결과를 찾을 수 있는 것은 아닌데, 그리디 알고리즘을 적용하기 위해서는 문제가 다음 두 가지 조건을 만족해야한다.
탐욕스런 선택 조건이란 앞선 선택의 결과가 이후의 선택에 영향을 주지 않는다라는 것을 뜻한다.
즉, 항상 탐욕스런 선택(최선의 선택)만 하더라도 최적의 결과를 얻을 수 있다는 뜻이다.
각 부분 문제의 최적해를 가지고 전체 문제의 최적해를 구할 수 있을 때 최적 부분 구조 조건이 성립한다고 한다.
이게 무슨 말이냐하면, 예를 들어 피보나치 수열의 식은 다음과 같이 구성되어 있는데
fibo(n) = fibo(n - 1) + fibo(n - 2);
전체 문제(fibo(n)
)이 최적해가 되려면 부분 문제(fibo(n-1) + fibo(n-2)
)가 최적이 되어야한다. 즉, 피보나치 수열은 최적 부분 구조 조건을 성립한다.
자, 이제 그리디 알고리즘에 대해 어느정도 알았으니 실전에서 사용할 수 있는 간단한 예제를 이용하여 그리디 알고리즘에 익숙해져보자.
문제 상황
겜마고 학생 도윤이는 방학동안 편의점에서 아르바이트를 하려고 한다. 도윤이가 담당하게 된 첫 업무는 계산 업무! 손님으로 온 부성이는 과자 2봉지와 음료수 3개를 골라 총 가격은 7,800원이 나왔고, 부성이는 계산을 위해 10,000원을 내밀었다. 평소 알고리즘을 좋아하던 도윤이는 동전의 갯수를 최소한으로 하여 거스름돈을 주고 싶다.
해결 과정
결론
정리하자면 가장 가치가 높은 동전을 먼저 거슬러주고 남은 잔액에 맞추어 순서대로 거슬러주면 된다.
문제 상황
겜마고 학생 도윤이는 방학 중 호실 친구들과 함께 부산으로 여행을 떠나기로 한다! 도윤이와 친구들은 우선 학교에서 모여 광명역으로 이동한 후 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원 |
해결 과정
결론
학교 -> 부산 까지의 효율적인 경로를 알려면 학교 -> 광명역의 효율적인 경로와 광명역 -> 부산역의 효율적인 경로를 알아낸 뒤 그것을 더하면 된다.
오 정말 유익한 게시물입니다. 어렵게만 생각했던 '그리디 알고리즘'의 개념에 대해 쉽게 잘 정리해주셨네요~~