Greedy algorithm
그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
그리고, 그것을 선택했을 때 최적의 해를 구할 수 있어야 한다 (정당성 분석 필요)
ex) 다익스트라 알고리즘(최단 경로 문제), 허프만 코딩 알고리즘(허프만 트리를 빌드할 때 그리디 알고리즘을 사용)
Greedy algorithm VS Dynamic programming
그리디 알고리즘
각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태
다이나믹 프로그래밍
하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택
대표 문제
배낭 문제
- (그리디) 짐을 쪼갤 수 있는 분할 가능 배낭 문제: 단가가 가장 높은 짐부터 차례대로 채워나가면 된다.
- (다이나믹) 짐을 쪼갤 수 없는 0-1 배낭 문제
동전 바꾸기 문제
- 동전의 액면이 10원, 50원, 100원처럼 증가하면서 이전 액면의 배수 이상이 되면 그리디 알고리즘으로 풀 수 있다.
- 배수가 아닌 경우 다이나믹 프로그래밍으로 풀어야 한다.
가장 큰 합
- 노드를 계속 더해가다가 마지막에 가장 큰 합이 되는 경로를 찾는 문제
- 다이나믹 프로그래밍으로밖에 못품.
리트코드 - Best Time to Buy and Sell Stock II
- 주식이 내리기 전에 팔고, 오르기 전에 산다.
- 다음 인덱스의 값이 현재 인덱스의 값보다 크면 무조건 사고, 판다.
def maxProfit(prices: List[int]) -> int:
result = 0
for i in range(len(prices) - 1):
if prices[i] < prices[i + 1]:
result += prices[i + 1] - prices[i]
return resulthttps://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
리트코드 - Queue Reconstruction by Height
- 우선순위 큐: 매번 그때의 최소 또는 최적의 값을 추출
- 우선순위 큐는 그리디에 어울리는 대표적인 자료구조
- 그리디 문제의 대부분은 우선순위 큐를 활용해서 풀이
풀이
- max heap으로 구현하였기 때문에 result에 들어가 있는 사람들은 현재 사람보다 다 큼
- 현재 사람의 2번째 원소 값을 인덱스로 보고 result에 그 위치에 넣으면 된다.
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
heap = []
# 키 역순, 인덱스 삽입
for person in people:
heapq.heappush(heap, (-person[0], person[1]))
print(heap)
result = []
while heap:
person = heapq.heappop(heap)
result.insert(person[1], [-person[0], person[1]])
return result