📌 그리디 알고리즘이란?
Greedy란 '탐욕스러운'이라는 뜻으로, 탐욕법이나 욕심쟁이 알고리즘이라고도 한다.
그리디 알고리즘은 매 순간 가장 좋은 것을 선택하는 알고리즘이다.
기준에 따라 좋은 것을 선택하는 알고리즘이기에 당장 가장 좋은 것만을 선택해 나아가도 문제가 없는지 기준을 파악할 수 있어야 한다.
그리디 알고리즘은 항상 최적의 해를 찾을 수 있는 것은 아니다.
따라서, 최적의 해를 선택하고 조건을 만족하는지, 해결이 가능한지를 확인해주어야 한다.
예시 문제 2문제 추가
📌 거스름돈 찾기
그리디 알고리즘에서 가장 기본적으로 풀기 좋은 문제이다.
거스름돈으로는 500원, 100원, 50원, 10원짜리 동전들이 있다. 거슬러 줘야 할 동전의 최소 개수를 구하라.
(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.)
1. 최소의 개수를 위해서는 단위가 가장 큰 동전을 선택 해준다.
2. 거슬러주고 남은 돈을 다음 단위의 동전으로 거슬러주며 결괏값 도출
이렇게 가장 큰 동전을 선택하여 최적의 해를 찾아나간다.
이 문제가 그리디 알고리즘으로 해결할 수 있는 이유는, 큰 단위의 동전은 작은 단위의 동전의 배수이기 때문이다.
예를 들어 N이 800원이고 주어진 거스름돈의 단위가 500원, 400원, 100원인 경우, 그리디 알고리즘을 이용한다면, 500 + 100 + 100 + 100 + 100으로 4개가 되겠지만, 실제의 최소 개수는 400 + 400으로 2개이다.
( 단위가 배수가 아닌, 무작위로 설정되어 있는 경우는 다이내믹 프로그래밍으로 해결할 수 있다.)
✅[ CODE ]
n = int(input()) # 거슬러 줘야 할 돈
coin = [500, 100, 50, 10] # 거스름돈으로 사용되는 동전
result = 0 # 최소 개수
for i in coin: # 거스름돈 단위가 큰 것부터
result += n // i # 몫
n %= i # 나머지
print(result)시간 복잡도는 거스름돈 단위 종류에 따라, O(n)이다.
📌 회의실 배정
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
회의가 가장 많이 진행될 수 있도록 하려면, 가장 빠르게 끝나 다음 회의를 빠르게 시작할 수 있는 회의를 선택해야 한다.
1. 주어진 회의를 가장 빠르게 끝나는 회의 순으로 정렬한다.
2. 가장 빠르게 끝나는 회의가 동일한 경우엔, 그중 가장 빠르게 시작하는 회의를 선택한다.
3. 정렬된 회의들을 순차적으로 확인하며, 겹치지는 않는지 확인해준다.
✅[ CODE ]
n = int(input())
arr = []
for _ in range(n):
arr.append(list(map(int, input().split())))
cnt = 0
time = 0
arr.sort(key = lambda x : (x[1], x[0]))
for x in arr:
if (time <= x[0]):
time = x[1]
cnt += 1
print(cnt)
이처럼 정렬 알고리즘을 통해 기준을 선택하여 그에 따라 좋은 것을 선택하는 문제가 많다.
문제 풀이를 위한 기준을 떠올리고 적절한지 검토할 수 있어야 한다.