그리디 알고리즘- 이것이 코딩테스트다

그리디 알고리즘

 

 

그리디의 의미는 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 이다.

 

 

필자는 이러한 의미에 대해 애매하게만 들렸고 전혀 감이 오지 않았다. 때문에 문제를 풀면서 이 알고리즘의 감을 조금씩 잡았다. 

 

 

그래서 얻은 결론은 이렇다.

 

 

"최소한의 아이디어(대충 생각한 것)를 떠올리고 이것이 정당한지 검토한다면 답을 도출한다."

 

 

예를들어 B라는 문제에 대해 A라는 아이디어가 떠올랐다고 가정하자. 우리는 이 A라는 아이디어가 이 문제에 쓰일 수 있는지, 혹시 A를 쓰다가 반례가 생기는 건 아닌지를 검토해야한다. 이러한 검토가 합리적이라면 이 문제는 결국 풀린다.

 

이 유형은 창의력을 기르는 유형이다. 이 때문에 시간안에 빠르게 알고리즘을 생각하는 능력을 기르는 것이 중요하다.

 

 

책에 있는 문제를 한번 풀어보자.

 

 

문제 해설: 핵심은 "가장 큰 것부터 나눠주는 것"이다. N이 500원보다 크다면 계속 500원으로 나누고 N이 더 작다면 그 뒤의 수로 나누고 이를 반복해서 문제를 해결하면 된다.

 

 

그렇다면 여기서 정당성은 어디 존재하는 걸까? 

정당성은 "큰 수는 작은수의 배수이다"이다. 만약 큰 수가 작은수의 배수가 아니라면 이는 합리적인 방법이 아니다.

예를들어 800원을 500원과 400원 100원으로 나눈다고 해보자. 최소한의 동전개수는 400원 2개지만, 위와같은 알고리즘을 이용한다면 500원 1개 100원 3개가 된다. 결국 이는 최적의 알고리즘이 될 수가 없는 것이다.

 

거스름돈 소스 코드

list = [500,100,50,10]

n = int(input())

count = 0

for i in list:
  count += n // i
  n = n % i
  
print(count)