Greedy Algorithm

Donburi·2023년 2월 5일
0

알고리즘

목록 보기
1/3

Greedy Algorithms

  • "Sequence of locally optimal choices"
  • Greedy algorithms don't always yield globally optimal solutions, but are usually the simplest and most efficient when they do.
    • Optimal Substructure (최적 부분 구조): 매 순간의 최적해가 문제에 대한 최적해인 경우
    • Greedy Choice Property (탐욕 선택 속성): 앞의 선택이 이후 선택에 영향을 주지 않는 경우
  • They often involve a sorting step that dominates the total cost (running time)

Problems

Coin-Change Problem (동전 바꾸기/거스름돈 문제)

Problem: find the minimum number of coins for amount k

Greedy works only when denominationi is divisible by denominationi-1, i>=2
Otherwise, you should use DP.

import sys

n, k = map(int, sys.stdin.readline().split())
denominations = []
for _ in range(n):
    denominations.append(int(sys.stdin.readline()))
count = 0
for coin in denominations[::-1]:
    count += k//coin
    k = k%coin
print(count)

Interval Scheduling

Problem: find the maximum-size subset of mutually compatible intervals

Consider intervals in increasing order of finish time

  • Intuition: leaves maximum interval (hence flexibility) for scheduling the remaining intervals
import sys

n = int(sys.stdin.readline())
intervals = []
for _ in range(n):
    s, e = map(int, sys.stdin.readline().split())
    intervals.append((s, e))
intervals.sort(key=lambda x: (x[1], x[0]))
count = 0
prev = 0
for interval in intervals:
    if interval[0] >= prev:
        count += 1
        prev = interval[1]
print(count)

Reference

  • 파이썬 알고리즘 인터뷰 by 박상길
  • COMP3711 Design and Analysis of Algorithms, HKUST

0개의 댓글