그리디

그리디

그리디 알고리즘

- 문제를 단순 무식하게, 탐욕적으로 푸는 알고리즘이다.

- 탐욕적으로 해결한다는 것은 곧 현재 상황에서 지금 당장 좋은 것만 고른다는 것을 의미한다.

- 문제 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야 함

- 보통 '가장 큰 or 작은' 과 같은 기준이 제시되므로, 정렬 알고리즘과 함께 출제되는 경우가 많다.

그리디 알고리즘의 정당성

- 그리디 알고리즘으로 문제의 해법을 찾았을 때는, 반드시 그 해법이 정당한지 검토해야 한다.

- 그리디 알고리즘을 이용했을 때 최적 해를 구할 수 없는 가능성도 적지 않으므로 유의해야 한다.

다음 그림을 보자. 루트 노드부터 시작하여 거쳐가는 노드 값의 합을 최대로 만들고 싶을 때?

단순히 매 상황에서 가장 큰 값을 고른다면, 해답을 찾을 수 없다는 것을 알 수 있다.

예제

Greedy 알고리즘을 통해, 아래의 문제에 대한 해답을 구해보자.

Q1) 사용하는 화폐가 다음과 같을 때, 금액 N이 입력되면 돈의 최소 개수로 거슬러 주기 위하여 각 종류의 돈이 몇 개씩 필요한지 출력하라. (SWEA 1970)

# 화폐 목록

50,000 원

10,000 원

5,000 원

1,000 원

500 원

100 원

50 원

10 원

문제해결 아이디어

- 최적의 해를 빠르게 구하기 위해선, 가장 큰 액수(화폐) 부터 돈을 거슬러주면 된다.

- 예를 들어 N원을 거슬러줘야 하는 경우, 가장 먼저 50,000원으로 거슬러 줄 수 있을 만큼 거슬러준다.

- 이후, 10,000원, 5,000원 순으로 거슬러 줄 수 있을만큼 거슬러준다.

정당성 분석

- 그리디 알고리즘 문제에서는 문제풀이를 위한 아이디어를 떠올리고, 이 아이디어가 정당한지 검토해봐야 한다.

- 그렇다면 위의 아이디어(=가장 큰 액수부터 돈을 거슬러준다.)는 정당한가?

- 가지고 있는 화폐중에서 큰 단위의 화폐가 항상 작은 화폐의 배수이다. 따라서, 작은 단위의 화폐들을 종합하여 다른 해가 나올 수 없기 때문에, 큰 단위부터 거슬러주는 것이 최적의 해를 보장한다.

- 만약 화폐단위가 500원, 300원, 100원이고 거슬러줘야 하는 돈이 800원이라면? 위의 아이디어는 정당성 결여!

답안 코드

N = int(input()) # 입력받은 돈 # 각 지폐별 사용 횟수를 저장할 배열을 만들기 - idx 0: 50000원 ~ idx 7: 10원 cnts = [0]*8 money = [50000, 10000, 5000, 1000, 500, 100, 50, 10] # 반복문을 통해 가장 큰 금액부터 계산(Greedy) for i in range(8): cnts[i] = N//money[i] # 몫을 cnts 에 저장 N %= money[i] # 거스름돈은 계속해서 계산 print(*cnts) # 결과값이 담긴 배열 출력

시간 복잡도

- 화폐의 종류를 N개라고 하면, 위 코드의 시간 복잡도는 O(N)이다.

- 즉, 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

from http://ggreen01.tistory.com/79 by ccl(A) rewrite - 2021-10-01 00:00:36