그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

특징

• 매 순간 가장 좋아 보이는 것을 선택
• 현재의 선택이 나중에 미칠 영향은 고려하지 않음.
• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

예제 : 거스름돈

Q : 카운터에 거스름돈으로 500, 100, 50, 10원짜리 동전이 무한이 있다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단 거술러 줘야할 돈 N은 항상 10의 배수이다.

해설)
이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제이다. 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것.

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분은 그리디로 '최적의 해'를 구할 수 없기 때문.

➡️ 따라서 그리디 알고리즘으로 문제의 해법을 찾았다면 정당한지 검토 필요.

위의 방법이 정당한 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 때문이다. 예를 들어 단위가 500, 400, 100 이라면 그리디로는 4개의 동전 (500 + 100 + 100+ 100)이지만 최적해는 2개(400 + 400)이기 때문.

이처럼 그리디 알고리즘으로 풀었다면 정당한지 확인 가능

코딩테스트에 응용

코딩테스트 문제를 만났을 때 바로 문제 유형을 파악하기 어렵다면, 그리디 알고리즘을 의심하고, 문제를 해 결할 수 있는 해결법이 존재하는지 고민하자. 만약 그리디로 안된다면 나중에 만날 DP나 그래프로 해결할지 고민해보자.

그리디 알고리즘을 그냥 풀다가 책을 읽고 예제도 풀어보니 무엇인지 확실히 감이 잡힌다.
책 구매는 잘한 선택 같다! 굳