욕심쟁이 알고리즘 ! 그리디 알고리즘 !

그리디 알고리즘이 뭘까?
말그대로 탐욕 알고리즘이다!
최적의 해를 구하기 위해 최적의 근사값을 찾아가는 방법 이라고 할 수 있다
무슨 말이냐면
서울에서 부산을 가려한다.
최단 경로를 구하는 방법은?
(대구를 경유해서 가야만 한다.)
서울에서 대구 가는 경로
A. 고속도로 : 200km
B. 국도 : 170km
C. 자동차 전용도로 : 190km

대구에서 부산을 가는 경로
A. 고속도로 : 150km
B. 국도 : 160km
C. 자동차 전용도로 : 160km

이런식으로 선택조건이 있다고 하면
서울에서 대구 까지 국도로 이동 후 대구에서 부산까지는 고속도로로 가는 경우가 최적의 해가 된다.

이렇게 구하고자 하는 해의 단계마다 최저값! 최댓값! 과 같이
최적의 해를 구해나가는 방법 이라고 설명할 수 있겠다.

가장 유명한 예제중 하나인 거스름돈 문제가 있다

문제

거스름돈 n원을 거슬러 주는 방법 중 동전 갯수를 가장 적게 주는 방법은?
(동전은 500원 100원 50원 10원이 있다)

방법

구하는 방법은 일단 주어진 input 안에서 500원으로 제공할 수 있는 최댓값을 구한다.
( n // 500)

그럼 이제 n - n//500*500 (500원으로 지불하고 나머지) 에서

이런 방법으로 100원,50원,10원의 순차대로 제공할 수 있는 최댓값을 구하면

최저 동전 갯수를 구할 수 있다.

그러면 백준 알고리즘 2839 번 설탕배달 문제를 살펴보자

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

풀이

n = int(input())
result = 0
while n>=0:
    if n % 5 == 0:
        result += n//5
        print(result)
        break
    n -= 3
    result += 1
else:
    print(-1)

먼저 n 을 input으로 입력받고
설탕봉지 갯수를 result로 놓아줬다.

이 문제는 사실 수능문제 2점도 아니고 단순 방정식으로 작성한다면 중학교 수학 과정의 수준이다
근데 물론 나도 처음 몇 번 제출을 틀렸닼ㅋㅋ

자 방정식으로 써보면?
3x +5y = n 인데 x+y 가 최솟값이 되어야 한다
즉 y가 최댓값이 되어야 x+y 가 최솟값이 될 수 있다.
자 그러면 y 의 최댓값을 구해보자

n = int(input())
if n ==4 or n ==7:
    print(-1)
elif n ==3:
    print(1)
elif n % 5 == 0:
    print(n//5)
elif n % 5 == 1:
    print((n//5 - 4) + 7)
elif n % 5 == 2:
    print((n//5 - 2) + 4)
elif n % 5 == 3 and n !=3:
    print(n//5 + 1)
elif n % 5 == 4 and n !=4:
    print((n//5 - 1) + 3)

사실 처음에 생각한건 n을 5로 나눠서 나오는 나머지는 0,1,2,3,4 니까 이 경우에 따라 return 값을 구해주면 반복문 안쓰고 최적의 해를 가장 빠르게 구하는 방법이지 않을까 라고 생각했다. 근데 안되더라..? 사실 아직도 위의 경우에서 발생하는 예외의 경우가 또 무엇이 있는지 모르겠다.

여하튼 이런 원리와 마찬가지로
n % 5 로 나눴을때 n//5 를 return 에 더해주고 출력 후 break
그 전까지는 n 에서 -3 / 설탕봉지 1추가 이런식으로 반복문을 사용해줬다.

이런 greedy 알고리즘의 접근법은 항상 정답을 찾아내는 것은 아니기 때문에 다이나믹 알고리즘과 같이 많이 쓰인다고 한다. 다음에는 다이나믹 알고리즘에 대해 공부해보자!