그리디 알고리즘
"당장 좋은 것만 선택하는 그리디"
그리디를 번역하면 탐욕법이라고도 번역되는데, 탐욕은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"을 의미합니다.
그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
아래 "거스름돈" 문제로 그리디 알고리즘을 설명하겠습니다.
[이것이 취업을 위한 코딩 테스트다 (with. Python)] 교재를 기반으로 작성된 포스트입니다.
거스름돈
저는 GS25 스토어 매니저 알바생입니다.
거스름돈을 주기 위해선, 500원, 100원, 50원, 10원 중 에서 줄 수 있습니다.
N원을 거슬러 주기 위해서, 가장 큰 화폐의 단위 먼저 거슬러 줍니다.
그 다음 100원, 그 다음 50원, 그 다음 10원으로 거슬러 줄 수 있습니다.
만약 1,260원을 거슬러 주어야 한다면, 다음과 같이 거슬러 주면 됩니다.
그리디 알고리즘의 정당성
그리디 알고리즘은 최적의 해를 찾을 수 없을 가능성이 있습니다.
제가 만약 400원이라는 단위를 만들어내면 어떨까요?
그래서 화폐 단위가, 500원, 400월, 100원이 되었다고 가정해봅시다.
우리가 800원을 거슬러 주려고 합니다.
- 기존 : 500원 + 100원 + 100원 + 100원
- 최적 : 400원 + 400원
원래는 가장 큰 단위로 거슬로 주고, 그 다음 단위로 거슬러 주는 것이 정석이였는데,
최적의 해는 2개의 동전(400원)으로 거슬러 주는 것이 최적이였습니다.
그래서, 그리디 알고리즘에서는 문제 풀이를 위한 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 합니다.
그리디 알고리즘의 주요 속성
그리디 알고리즘을 풀 때, 두가지 조건을 성립해야합니다.
1. 탐욕 선택 속성
- 각 단계에서 '최적의 선택'을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
각 단계에서, 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져옵니다.
2. 최적 부문 구조
- 전체 문제의 최적해가 '부분 문제의 최적해로 구성' 될 수 있는 경우.
전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.
사실 그리디 알고리즘은 거창한 것이 아니라고 생각합니다.
그냥 문제에 대한 정답을 이끌어 내는 것이라고 생각하면 될 것 같습니다.
문제 풀기
- 최적해의 구조를 생각하고 선택 하기
- 선택된 해가 문제 조건을 만족하는지 적절성 검사 수행 하기
- 조건을 만족하지 않으면 해를 제거
- 해답 검사
