[이코테]그리디 알고리즘

어느날 solved.ac를 확인하다가 안 사실, 문제의 분류가 있었다는 것!

백준 문제풀이 태그 분포

당시 낮은 티어 별로 문제를 풀었기에 문제의 유형을 생각해 볼 겨를이 없었다.

되짚어보면 브론즈 그리드 알고리즘은 문제를 한 번에 파악하기 힘들었다는 특징이 있었다는 것이 기억난다. 확률처럼, 문제를 푸는 방법이 여러가지지만 그 중에서 가장 최적의 방식을 골라야 시간을 단축할 수 있었기 때문이다. 방금 '알고리즘의 기본 아니냐'는 생각이 들었다면, 지금부터 이 알고리즘이 어떤 것인지 알아가보자.

그리디 알고리즘이란?

탐욕법이라고도 소개되는 이것은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'으로, 각 단계에서 가장 최선의 선택을 하는 기법이다.  사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은, 즉 문제 출제의 폭이 넓다는 특징을 지니고 있다.

이 알고리즘 문제의 핵심은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이다. 따라서 어떠한 문제를 마주쳤을 때 유형을 파악하기 어려울 경우, 그리디 알고리즘을 의심하고 다이나믹, 그래프 순으로 고민하는 것도 방법이 될 수 있다. 주로 정렬 알고리즘과 짝을 이뤄 출제된다.

예제

Chapter 03 그리디 中 예제 3-1. 거스름돈
난이도 ★☆☆, 풀이시간 15분, 시간 제한 1초, 메모리 제한 128MB

당신을 음식점의 카운터를 맡은 점원이라고 가정할 때, 카운터에 거스름돈으로 사용할 동전의 종류(500원, 100원, 10원)가 있고, 그 수는 무한하다고 하자. 손님에게 거슬러 드려야 할 돈 N원에 상응하는 동전의 최소 개수를 구해보자. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

---

체감 난이도 ★☆☆, 소요 시간: 5분
어려웠던 부분: 알고리즘 오류 찾아내기

 해당 문제에서 원하는 것은 동전의 최소 개수이므로 가장 큰 화폐부터 동전의 개수를 세어야 최솟값을 구할 수 있다고 생각했다. 하지만 남은 돈의 수를 나누어주는 과정이 없어서 실패했던 경험이 있다.

#3-1.거스름돈

n = 1260 #거슬러 주어야 할 돈의 변수 생성
cnt = 0 #동전 개수를 저장할 변수 초기화

#큰 단위의 화폐부터 차례대로 확인
coin_list = [500, 100, 50, 10]

for coin in coin_list: #전체를 순회하며(큰 순서대로)
	cnt += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 카운팅
    
print(cnt) #개수 출력

 

문제 해설

이 문제에서 접근 방식은 크게 두 가지가 있다.

1.  10원짜리 동전으로 상응하는 돈 N이 될 때까지 세어 거슬러 준다. 
2. 가장 값이 큰 동전의 순서대로 값을 채워 목표 값이 될 경우 거슬러 준다. 

이 둘의 차이는 엄청나고, 2번이 지금부터 사용할 그리드 알고리즘이다. 이 문제를 풀기 위해서는 '가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례때로 확인하여 거슬러 주는 작업을 수행'하는 것이다.(아이디어) 1번이 아닌 2번을 택하는 이유는 1번이 최적의 해를 구할 수 없는 방식이기 때문이다.

위 문제의 특징은 '동전의 최소 개수'를 구한다는 것과, 거스름돈이 10의 배수라는 것이다. 위 조건이 없다면 그리디 알고리즘으로 해결할 수 없어 보통 다이나믹 프로그래밍으로 해결한다. 이 경우 화폐의 종류(K)만큼의 시간이 들기 때문에 시간 복잡도는 O(K)가 된다.

#3-1.거스름돈

n = 1260 #거슬러 주어야 할 돈의 변수 생성
cnt = 0 #동전 개수를 저장할 변수 초기화

#큰 단위의 화폐부터 차례대로 확인
coin_list = [500, 100, 50, 10]

for coin in coin_list: #전체를 순회하며(큰 순서대로)
	cnt += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 카운팅
    n %= coin #나누어 확인
    
print(cnt) #개수 출력

---

정리

1. 그리디 알고리즘은 각 단계에서 '최적의 해'를 택하는 것이다.

2. 최적의 해를 구할 수 있는 아이디어를 떠올리는 것이 중요하다.

3. 문제 유형을 파악하기 어려울 경우, 그리디 알고리즘을 의심해보고 다이나믹 프로그래밍이나 그래프 알고리즘을 활용해보자.

저서: '이것이 취업을 위한 코딩 테스트다 with 파이썬' - 나동빈 지음
위의 저서를 바탕으로 재구성한 포스트 입니다.