✏️ 서론
어제는 순열과 조합을 배웠다.
이제는 실제 코딩테스트에서 많이 출제되는 유형 중 하나인
그리디(Greedy) 알고리즘을 배워보자.
✏️ 본론
- 최종 해답을 찾기 위해 각 단계마다 하나의 답을 고름
- 각 단계에서 답을 고를 때 가장 좋아 보이는 답을 선택
- 선택할 당시 최적의 답을 고르지만, 최종 해답이 반드시 최적임을 보증하지 않음
그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
greedy란 단어 그대로, 무식하고 탐욕적이게 문제를 푸는데 여기서 탐욕적이란 말은 현재 상황에서 가장 지금 당장 좋아 보이는 것만 고르는 방법을 뜻하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
또, 앞으로 다루게 될 알고리즘과 다르게 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 다익스트라 알고리즘 같은 특이 케이스는 제외하자.
(근데 나는 다익스트라가 뭔지 모른다 🥲 🥲 )
보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력 즉, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한다.
또, 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다. 이러한 문제는 정렬을 사용하면 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
거스름 돈 문제를 예를 들면, 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.
가장 큰 화폐 단위부터 돈을 거슬러주는 것이다.
N원을 거슬러줘야한다고 가정하면 가장 큰 단위인 500원, 100원... 차례로 거슬러주면 최소의 동전개수로 모두 거슬러 줄 수 있다.
N=1,260이라고 하면 500원 2개, 100원 2개, 50원 1개, 10원 1개로 최소한의 동전으로 거스를 수 있다.
이를 식으로 표현하면 다음과 같다.
n = 1260
coin_array = [500, 100, 50, 10]
count = 0
# count: n을 coin으로 나눈 몫
# `n`을 `coin`으로 나눈 나머지를 0이될때까지 지속함
for coin in coin_array:
count = count + n // coin
n = n % coin
print(count)
👉🏽 6코드를 보면 화폐의 단위만큼 반복수행해야하므로 시간복잡도는 O(K)이다.
또, 거슬러줘야 할 돈 N은 찾아 볼 수 없는것을 알 수 있는데, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.
그리디 알고리즘의 또 다른 특징은 해법이 정당한지 검토해야하는데, 거스름돈문제를 그리디 알고리즘으로 풀 수 있는 이유는 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
예를 들어, 동전의 화폐 단위가 500원, 400원, 100원일 경우를 생각해보자.
그리디 알고리즘으로는 4개의 동전(500원 1, 100원 3)을 거슬러줘야하지만, 최적의 해는 2개의 동전(400원 * 2)을 거슬러 주는 것이다.
아이디어까지는 동일하다는 점에서 정당하다.
이처럼 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
만약 어떤 코딩테스트를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해보고, 문제를 해결 할 수 있는 탐욕적인 해결법이 존재하는지 참고해보자. 그래도 찾기 어렵다면, 그때는 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할수있는지 재차 고민해보자.
(아직 나는 다이나믹, 그래프 알고리즘이 뭔지 모른다 🥲 🥲 )
마지막으로 거스름돈 문제에서 동전(화폐)의 단위가 서로 배수의 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다.
이때는 다이나믹 프로그래밍으로 해결 할 수 있으며 이는 2장에서 배우기로 하자.
📍 [ 문제 ] 백준 - 거스름 돈(5585)
문제 중 카운터에서 1000엔 지폐를 한장 냈을 때라고 선언되어있기 때문에, 입력값은 항상 1000을 빼줘야한다.
다음 잔돈은 이미 주어져있기 때문에 data 값으로 넣으면 된다.
다음과 같이 풀 수 있다.
t = int(input())
n = 1000 - t
data = [500, 100, 50, 10, 5, 1]
count = 0
for coin in data:
count = count + n // coin
n = n % coin
print(count)
👉🏽 예제 입력: 380, 예제 출력: 4
📍 [ 문제 ] 백준 - ATM(11399)
해당 문제도 거스름 돈과 동일하게 그리디(greedy) 알고리즘을 사용하면 된다.
앞에 위치한 사람이 걸리는 시간만큼 누적되는 계산이다.
즉, 뒤로 갈수록 누적한 값이 최소가 되어야하고 리스트를 sort(), 오름차순으로 배열 한 다음 풀면되는 문제다.
여기까지 도출하는데 성공했으나, 뒤에 리스트에 값을 누적하면서 더하는 방법(?)을 몰랐다.
결국 for문을 2번돌면 풀수있는 문제였는데,
그게 어려웠다. 아직 많이 부족한것 같다.
for문을 2번 사용하는 문제를 풀어봐야겠다.
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0
for i in range(n):
for j in range(i+1):
result = result + array[j]
print(result)
👉🏽 예제입력
5
3 1 4 3 2
👉🏽 예제출력
32
✏️ 결론
오늘은 그리디 알고리즘에 대해 배워봤다.
아직 거스름 돈문제만 풀었지만 그리디알고리즘을 적용하는 다른문제를 풀어봐야겠다고 생각했다.
내일까지 그리디 알고리즘을 보고 구현 파트로 넘어가자.
