[파이썬 알고리즘 인터뷰] 그리디 알고리즘

• 그리디 알고리즘: 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘
  • 대부분 뛰어난 결과를 도출하지 못하지만, 드물게 최적해 보장
  • 최적해를 찾을 수 있으면 그것을 목표로 삼고, 그것이 어렵다면 주어진 시간 내에 최적에 가까운 해를 찾음
  • 탐욕 선택 속성 + 최적 부분 구조 에 해당하는 문제에 좋다
    • 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것
    • 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우
  • 예) 다익스트라, 허프만 코딩, ID3
  • DP vs Greedy
    • DP: 하위 문제에 대한 최적 솔루션을 찾고, 이 결과들을 결합한 정보로 전역 최적 솔루션 선택
    • Greedy: 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태
• 배낭 문제: 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 각각 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 하는 짐들의 조합
  • 짐을 쪼갤 수 있을 때 그리디, 쪼갤 수 없을 때 DP
• 동전 바꾸기 문제: 돈을 동전으로 거슬러 줄때, 동전의 갯수를 최소한으로 하여 거슬러주는 문제
  • 동전끼리 모두 배수 관계: 그리디, 그렇지 않다면 DP
• 가장 큰 합: 이진 트리에서 헤드부터 리프까지 노드를 하나씩 선택하여 가장 큰 합이 되도록 하는 경로 찾기
  • 이진 트리를 정렬하는 등의 추가 작업 없이는 그리디로 풀이 불가

122. Best Time to Buy and Sell Stock II

- 그리디: 오늘보다 내일 가격이 오르면 오늘 사고 내일 팔기 매일 반복

- (내일 가격 - 오늘 가격) 값이 0보다 큰 날만 누적 합산

 

406. Queue Reconstruction by Height

- 최대 힙 -> 키는 내림차순, 같은 키끼리 인덱스는 오름차순으로 힙 구성하여 하나씩 추출하며 인덱스 값으로 위치

* heapq.heappush(heap, (-person[0], person[1]))

- 내 풀이: 힙 대신 리스트로 키 내림차순, 인덱스 오름차순으로 정렬 후 같은 알고리즘으로 정답 구성

* sort(key = lambda x : (x[0], -x[1]), reverse = True)

 

621. Task Scheduler

- 갯수가 많은 순으로 n개 + idle 순으로 다 없어질 때까지 반복 삽입하되, 마지막 n개는 가능한만큼 중간의 idle에 삽입

* Counter().subtract(Counter())

n

idle

n

idle

n

idle

...

n

n + 1

n + 1

n

idle

...

나머지

 

134. Gas Station

- 브루트 포스

- 답이 존재하는 경우, 다음 주유소로 넘어갈 수 없는 지점이 있다면 처음부터 이 지점까지는 출발점이 될 수 없음

 

455. Assign Cookies

- 그리디 -> 정렬된 두 리스트를 투포인터로 순회하며 만족되는 횟수 세기

- 이진 검색 -> 두 리스트 정렬 후, 사이즈 리스트 순회하며 탐욕 리스트 이진 검색