글로벌(global) 최적을 찾기 위해 각 단계에서 로컬(local) 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘
💭 What is "Greedy"?
- 문제를 "piece by piece"로 해결해나간다.
- always choose the next piece that offers the most obvious and immediate benefit.
단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
탐욕법이란 '현재 상황에서 지금 당장 좋은 것만 고르는 방법', 쉬운 말로, 바로 눈 앞의 이익만 좇는 알고리즘이다.
대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우가 있다.
탐욕법은 ❗최적화 문제❗를 대상으로 한다.
합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다는 점에서 유용한 알고리즘이다.
💭 When do we use "Greedy"?
그렇다면 어떤 문제에서 탐욕법을 사용해야 하는가?
At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.
"탐욕 선택 속성(Greedy Choice Property)"을 갖고 있는 "최적 부분 구조(Optimal Substructure)"인 문제들
👉 탐욕 선택 속성(Greedy Choice Property)란?
🔴 앞의 선택이 이후 선택에 영향을 주지 않는 것.
🔴 즉, Greedy는 선택을 다시 고려하지 않는다.
👉 최적 부분 구조(Optimal Substructure)란?
🔴 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우
💭 Examples for using "Greedy"
그리디 알고리즘이 잘 동작하는 예는 뭐가 있을까?
- 최단 경로 문제를 풀이하는 다익스트라 알고리즘(Dijkstra’s Shortest Path), 최적해 보장
- 압축 알고리즘인 허프만 코딩(Huffman Coding) 알고리즘: 허프만 트리를 빌드할 때 그리디 알고리즘을 사용, 최적해 보장
- 의사결정 트리(Decision Tree) 중 ID3 알고리즘: 항상 그때 그때 최선의 답을 찾아 트리를 빌드해나감
💭 Greedy vs Dynamic Programming
그리디 알고리즘과 다이내믹 프로그래밍은 최적 부분 구조 문제를 푼다는 면에서 자주 비교된다. 그렇다면 Greedy와 Dynamic Programming은 어떻게 다른가?
- Greedy Algorithm: 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태
- Dynamic Programming: 하위 문제에 대한 최적의 솔루션 찾은 후, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션(Globally Optimum Solution)에 대한 선택을 함
즉, 서로 반대 방향으로 접근한다.
동일한 문제여도, 조건에 따라 그리디 알고리즘으로 풀 수 있거나/없을 수 있고, 이에 따라 다이내믹 프로그래밍 방법으로 풀어야할 수도 있다.
💭 Greedy or Dynamic Programming?
🚩 Fractional Knapsack Problem(배낭 문제)
이 문제는 (1) 짐을 쪼갤 수 있는 경우와 (2) 짐을 쪼갤 수 없는 경우 다르게 접근하여 풀어야 한다. 전자의 경우 그리디 알고리즘으로 풀 수 있지만, 후자는 다이내믹 프로그래밍 방법으로 풀어야 한다.
(1) 짐을 쪼갤 수 있는 경우
배낭에 담을 수 있는 무게의 최댓값
n이 주어진다.
각 짐의 가치($) 와 무게(kg) 값이 담긴 배열이 주어진다.
이 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법은?
🔵 단가가 가장 높은 짐부터 차례대로 채워나가면 된다.
(2) 짐을 쪼갤 수 있는 경우
References
- 파이썬 알고리즘 인터뷰(95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트), 박상길 지음
- 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 지음
- https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/
- https://www.geeksforgeeks.org/fractional-knapsack-problem/
