[알고리즘]그리디 알고리즘(Greedy algorithm)

hj·2021년 1월 26일

greedy algorithm

알고리즘

목록 보기

2/35

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 result

https://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