(실전)
그리디(greedy): 어떠한 문제가 있을 때 탐욕적으로 문제를 해결하는 알고리즘
탐욕적? - 현재 상황에서 지금 당장 좋은 것만 고르는 것.
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
그리디 알고리즘은 암기한다고 해서 잘 되는 알고리즘 유형이 아님
⇒ 사전 지식이 없어도 풀 수 있는 문제들도 있지만, 많은 유형을 접해보고 문제를 풀어보며 훈련해야 함. (= 맞아가면서 배워야 함)
그리디에서 요구되는 특징: 창의력
⇒ 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
⇒ 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 함
그리디 유형 문제들의 특징
’가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 알게 모르게 제시해줌.
⇒ 정렬 알고리즘과 짝을 지어 출제됨.
예제 - 거스름 돈
책 87p
그리디 알고리즘의 정당성
탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때, 매우 효과적이고 직관적임.
그리디 알고리즘으로 문제의 해법을 찾았을 땐 그 해법이 정당한지 꼭 검토해야 함
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유
⇒ 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
⇒ 큰 단위가 작은 단위의 배수 형태 → 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다 ⇒ 정당함!
바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제을 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보기
⇒ 만약에 해결 방법이 없다면? 다이나믹 프로그래밍 or 그래프 알고리즘 등으로 문제를 해결할 수 있는지 검토하기
처음에 문제를 만났을 때
10원짜리로만 모두 거슬러 주도록 코드를 작성하면 어떻게 되지? → 10원짜리로만 모두 거슬러 주면 최적의 해를 구할 수 없겠구나! (문제점 인식) → 또 다른 가능성이 있는 풀이 방법 생각 → 가장 큰 500원짜리부터 거슬러서 가장 작은 10원짜리까지 차례대로 거슬러 준다면 어떻게 될까? ⇒ 거스름돈 문제에서는 단위가 항상 작은 단위의 배수 형태이므로, 이렇게 하면 항상 최적의 해를 보장할 수 있겠구나!
⇒ 정답!
⇒ 화폐의 단위가 무작위로 주어진 문제는 다이나믹 프로그래밍으로 해결할 수 있음
난이도가 쉬워서 30분만에 풀어야 하는 문제들
30분만에 풀기 실패