Greedy

특징

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형, 반면 정렬, 최단 경로 등은 해당 알고리즘의 사용 방법을 정확히 알아야 해결 가능한 경우가 많음
• 다익스트라도 일종의 그리디, 암기가 필수인 알고리즘
• 보통 코테에서 나오는 그리디는 문제를 풀기 위한 최소한의 창의력(아이디어 떠올릴 수 있는 능력) 요구
• 가장 큰 순서대로 or 가장 작은 순서대로 같은 기준 있을 수도 있음. 정렬과 함께 사용하는 경우 많음
• 코테 할 때, 가장 먼저 그리디를 생각해보고 고민해도 안나오면 DP 나 그래프로 넘어가자.

예제) 거스름돈

500원, 100원, 50원, 10원으로 거스름돈 N(10의 배수)원을 거슬러 줄 때, 줘야할 동전의 최소 개수를 구하라.

솔루션

• 가장 큰 화폐부터 최대한 많이 주기!
• 시간복잡도 O(K), K : 화폐 종류 개수

그리디 알고리즘의 정당성

그리디 알고리즘으로 솔루션을 찾았을 때는 이 방법이 정당한지 검토해야한다.

예제에서는 화폐 중 큰 화폐들은 작은 화폐로 나눠져서 작은 화폐들로 새로운 단위를 만들 수 없으므로 가능하다.

10원짜리로만 만들어 보기 → 최적해 안됨

500원부터 10원까지 주기 → 가능

⇒ 큰 단위가 항상 작은 단위의 배수 형태이므로 최적해 보장할 수 있겠다 → 이 솔루션 당첨!

참조

• 이것이 취업을 위한 코딩테스트다 with Python 도서, 나동빈