[이것이코딩테스트다] 그리디

그리디(Greedy) 유형

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법 -> 말 그대로 탐욕

- 매 순간 가장 좋아 보이는 것을 선택

- 현재 선택이 나중에 미칠 영향 고려X

 

 

코딩 테스트에서의 특징

- 코테에서 그리디 알고리즘 문제 유형은 주로 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높음

-> 그리디 알고리즘 유형의 문제는 매우 다양. 다양하게 풀어봐야함.

- 최소한의 창의력 요구. 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제 풀 수 있는지 파악할 수 있어야함

- 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 처럼 기준을 제시해주기도함 -> 정렬 알고리즘과 짝을 이뤄 출제되기도

 

- 이 방법대로 하면 항상 최적의 해를 가지는지

- 현재 선택할 수 있는 가장 최선의 방법이 무엇인지

- 문제 해결할 수 있는 탐욕적인 해결법이 존재하는지

 

그리디로 해결 방법을 못찾았다면? -> 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 해결 가능한지 고민

 

 

예제 3-1 거스름돈

- '가장 큰 화폐 단위부터' 거슬러 주는 게 포인트 (항상 최적의 해를 보장함)

-> 이게 정당한지 검토해야함

(갖고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해서 다른 해가 나올 수 없음)

-> 정당하다

ex) 500,400,100원 이면 그리디 알고리즘으로 못풂

n = 1260
coin_type = [500,100,50,10]
count = 0

for i in coin_type:
    count += n//i
    n = n%i
    
print(count)