그리디 알고리즘 Greedy 파이썬 코딩테스트 (7)

서론

지난번 재귀 포스팅에 이어 이번에는 그리디 알고리즘에 대해 알아보고자 한다. 이번 포스팅은 이 강의를 참고했다. 가능하다면 이번 포스팅에서 문제도 다룰 예정이고 만약 안된다면 다음 포스팅에서 마저 문제를 다뤄보겠다. 적을 내용이 얼마 없다면 바로 문제 풀것임.

---

그리디 알고리즘이란? 

 현재 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘이다. 일반적으로는 관찰을 통해 탐색 범위를 어떻게 줄일지(=시간 복잡도를 낮출 지) 생각하는데, 이 때 탐색범위를 줄여도 올바른 결과를 낳는다는 사실이 증명이 되어야 한다. 증명이 안된다면 베팅하는거라 단순 노가다 코딩 보다 못한 결과를 초래할 수 있다. 하지만 코딩 테스트에서 빠르게 고안하고, 올바르게 증명할 확률은 극히 드물다. 오히려 잘못된 믿음으로 틀리는 경우가 더 많다고 한다. 

---

코딩테스트에서 그리디 알고리즘 사용?

코테 고인물인 알고리즘 강의 채널에서는 그리디 알고리즘에 대한 위험성을 알려줬다. 때문에 코딩테스트에서의 추천 전략은 1. 예전에 풀어봐서 거의 100% 확신하는 수준에 이르를때 -> 구현해보고 틀리면 손절 2. 100% 확신은 없지만 그럴~듯한 풀이가 내 뇌에 있다. -> 일단 스킵하고 다른 문제를 먼저 푼 다음 다시 돌아와서 해당 문제를 푼다.는 방법이다. 아마 후자는 위에서 언급했듯 틀릴 확률이 압도적으로 높아서 멘탈 관리 + 시간 잡기 관리용으로 언급한듯 하다. 고인물 센세가 말씀하시길, 그리디가 그렇~게 나오는 편도 아니라고 하며 오히려 그리디로 풀 수 없는 문제인데 착각의 늪에서 빠져나오지못해 똥 싸놓고 치우지 못하 경우가 많다고 한다.(의역함) 그러니 그리디스러운 문제여도 바로 풀이는 비추라고 귀결내심.

 

---

그리디 백준 문제 BOJ11047 내 풀이

BOJ11047 문제를 풀어보고자 한다. 일단 내가 딱 보자마자 생각한 것은, 큰 단위 N부터 해당 값(K)을 나누는 것이다. 그래서 몫이 1이상이 나오면 , result += 몫을 하고, K는 나머지로 갱신한다. 이 과정을 코드로 구현한 건 다음과 같다. 문제 복붙하느라 coins 배열이 다소 더러운건 양해요망.

n,k = 10, 4790
coins = [1
,5
,10
,50
,100
,500
,1000
,5000
,10000
,50000]
ahrt,answer = 0,0
coins = sorted(coins,reverse=True)
for i in range(n):
    ahrt = k//coins[i]
    if ahrt >= 1 :
        k= k - ahrt*coins[i]
        answer += ahrt
    else: continue
    
print(answer)

---

그리디 백준 문제 BOJ11047 정석 풀이

DP로도 풀 수 있다고 한다. D[i]는 가치의 합을 i로 만들때 필요한 동전 개수 최솟값 -> D[i] = min(D[i-a1], D[i-a2], D[i-a3],..., D[i-an-1], D[i-an]) ->하면 시간초과가 발생한다고 한다. 때문에 그리디 풀이가 맞을 것이고 직관적으로 생각하면 내 풀이와 같이 가장 큰 단위로 (평소에 우리가 하듯) 거스름돈을 주는 것이다. 하지만 직관적으로 푸는 것과 수학적으로 올바른 것에는 큰 차이가 있다고 한다. 증명 과정을 살펴보면 그리디 풀이가 많은지, 반례를 잡는 능력을 기르기에 좋기 때문이다. 아무튼 수학적으로 옳은지 알기 위해서는 보조정리가 필요하다.

보조 정리 = 동전 최소 소모로 물건값 지불하려면 10/100원은 4개이하, 50은 1개이하로 사용해야 된다. : 귀류법으로 사용하면 10/100의 5개 이상은 50원, 500원으로 대체가 가능하기에 그 이하까지가 최소값임. 그렇기에 동전을 최소로 소모하면서 물건값을 지불하려면 500원 동전을 최대한 많이 써야된다.-> 큰 단위부터 써야 된다.

---

끝으로

보조정리에 따르면 이는 배수 관계가 적용될 때 가능한 건데, 만약에 배수관계가 아니라면 해당 알고리즘을 사용할 수 없다. 간단한 반례를 들면, 1,9,10 이 있고 18을 만드려면 위 알고리즘으로는 10먼저쓰고 8을 만드려고 1을 8개 소모할 것이다. 하지만 사실 9 2개로 해결할 수 있기에 위 알고리즘은 사용할 수 없다. 그렇기에 비슷해보여도 풀이의 방향을 한정짓지 말라는 그의 교훈. 이번엔 간단하게 예제를 풀어보았는데, 다음 포스팅에는 그리디로 유명한 회의실 배정 문제를 풀어보도록 하겠다.