[코테스터디] 그리디(Greedy)

그리디 문제는 현재 상황에서 가장 좋은 것만 고르는 방법 즉, 탐욕적으로 문제 푸는 방법을 의미한다. 부분적으로 구한 해를 통해 전체 해를 구하면 된다. 보통 정렬이나 우선순위 큐(`heapq`)를 이용해 푸는 문제들이 많다. 사실 그리디 문제는 유형이 없는 것 같다. 간단한 문제들도 있지만 복잡한 문제들도 많으니 많이 풀어봐야 한다.

그리디 문제에서 나오는 우선순위 큐

우선순위 큐를 구현하기 위해 힙(Heap)이라는 자료구조를 사용한다. 우선순위 큐는 스택이나 큐와 다르게 우선순위가 높은 데이터를 가장 먼저 처리한다.대표적으로 아래 먹방 라이브 문제가 우선 순위 큐를 사용하는 그리디 문제이다.

`import heapq`를 통해 최소 힙 모듈을 불러와 사용할 수 있다. 데이터가 회전 초밥처럼 돌아가면서 풀어야하는 문제에 많이 사용되니 알아두면 좋을 것이다. 이 모듈 말고도 `PriorityQueue` 모듈도 존재하는데 일반적으로 `heapq`가 더 빠르다고 한다. 

heapq.heappush(hq, 4) # hq(힙큐)의 상태를 유지하면서 4(item)을 추가한다.
heapq.heappush(hq, 3)

heapq.heappop(hq) # hq(힙큐)의 상태를 유지하면서 가장 작은 값을 추출한다. 
# 만약 값이 비어있는 경우 IndexError를 발생시킨다.

heapify(lst) # 리스트를 힙으로 반환

#  모든 k에 대해 heap[k] <= heap[2*k+1] 또는 heap[k] <= heap[2*k+2] 만족

• 파이썬 우선순위 큐 공식 문서↗
• 우선순위 큐와 힙 - chanBLOG↗

 

큰 수 만들기

다음은 큰 수 만들기라는 문제이다. 

해당 문제를 풀기 위해선 O(N) 정도의 코드를 작성해야한다. 문제는 k개를 제거했을 때 가장 큰 숫자를 구하는 문제이다. 예를 들어, "4177252841"의 경우 1부터 하나씩 큰지 작은지를 비교하면서 큰 경우 큰 숫자를 넣고 기존의 숫자를 제거해버리면 되는 방식이다.

그리고 만약 제거해야할 갯수가 남았을 때 뒤에 있는 숫자를 자르는 방식으로 문제를 풀면 된다. 결론적으로, 하나하나 순간마다 최적의 경우를 판단하여 문제를 푸는 방식이다.

📝 풀어보기 좋은 문제들

• 큰 수 만들기 - 프로그래머스
• 무지의 먹방 라이브 - 2019 KAKAO BLIND