[Algorithm] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기

이번에 살펴볼 알고리즘은 그리디 알고리즘이다. 기본적인 알고리즘으로 이것을 처음으로 다루었어야했는데 BFS/DFS부터 다뤄버렸다… 그리디 알고리즘의 경우 구현보다는 문제해결 능력을 요구하기에 빠르게 이해하고 이후에 문제를 다루어 볼 것이다.

그리디 알고리즘(탐욕법, Greedy Algorithm)이란?

• 현재 상황에서 가장 좋은 것만 고르는 방법을 의미한다.
• 단순하지만 강력한 문제 해결 방법이다.
• 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

코딩 테스트의 유형

• 그리디 알고리즘의 경우 문제 출제의 폭이 매우 넓어 문제를 풀기위한 능력을 요구한다.
• 하지만, 최단 경로를 구하는 다익스트라 알고리즘의 경우 그리디 알고리즘으로 분류가 되어 암기가 필요하다.

대표적인 그리디 알고리즘 예제

• 거스름돈 문제
  • 거스름돈이 500원, 100원, 50원, 10원 짜리 동전이 무한이 존재한다 가정할 때, 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수는?(단, N은 항상 10의 배수)
  • Ex) N=1260의 경우 500원 2개, 100원 2개, 50원 1개, 10원 1개 총 6개를 거슬러 주어야 한다.
    즉, 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
  • N = int(input()) Coin = [500, 100, 50, 10] cnt = 0 #거스름돈 동전의 개수 for i in Coin: # 500원 동전부터 개수 Count cnt += (N//i) # 사용한 동전의 개수(몫) 만큼 더해준다. N %= i # N은 남은금액으로 update print(cnt)

그리디 알고리즘 문제의 정당성

• 만약 위와 같은 동일한 문제에서 동전이 500원, 400원, 100원 이라면 어떻게 될까?
• 위와 같은 풀이 방법이라면 500원 1개, 100원 3개로 총 4개로 도출이 되지만 400원 2개로 더 작은 경우의 수가 발생할 수 있다.
• 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.