그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법
문제에서 반복적으로 선택을 해도 최적의 해를 구할수 있는지 검토 필요

예시

루트 노드에서 시작해서 단말노드까지의 합의 최대값을 찾고 싶다. 그럴때 최적의 해를 구해라.

실제 눈으로 봐도 5 - 7 - 9 = 21 라는게 쉽게 보인다.
예를들어 루트 노드부터 다음 노드를 넘어갈때 가장 큰값들만 고르자 하고 선택을 하게 된다면
5 - 10 - 4 = 19 최적의 해보다 적은 값이 나오는거를 확인할수가 있다.

여기서 보는 것처럼 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많이 있다.

예시문제 1. 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하여라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

해결방법

최적의 해를 빠르게 구하기 위해서 가장 큰 화폐 단위부터 돈을 거슬러 주고 N원을 거슬러 줄때 가장 먼저 500원 그다음에 100원, 50원, 10원 순서대로 거슬러 주면 된다.

코드 분석

# 거슬러줘야 할돈 입력
n = int(input())

count = 0

#큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += (n // coin) #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    # [//] 연산을 사용 하게 되면 소수점 이하는 버리고 몫만 출력한다
    n %= coin # n은 해당 화폐로 나눈 금액의 나머지

print(count)

예를 들어 1260원이라는 금액을 입력해서 동전의 개수를 세어본다고 가정하면 화폐단위가 가장큰 500원부터 현재 가격에서 나누어 지는 갯수를 10원까지 순차적으로 계산하면서 count에 갯수를 모두 더해주면 전체 동전의 갯수를 알수가 있다.

하지만 여기에서 최적의 해를 보장할수가 없다고 볼수가 있는것이 예를들어서 800원을 거슬러 주어야 하는데 화폐의 단위가 500원 400원 100원 이라고 가정하게 된다면 가장큰 화폐부터 계산해서 500원 1개 100원 3개 총 4개가 나오게 되는데 실제적으로 가장 최적의 해는 400원 2개로 최적의 해를 보장이 안된다고 할수가 있다.

예시문제 2. 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수
는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수 구하기

조건

입력 조건 : 첫째 줄에 N(1 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백을 기준으로 하여 각각 자연수로 주어진다.
출력 조건 : 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
입력 예시 : 25 5
출력 예시 : 2

해결방법

주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다. N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다.

코드 분석

# 입력받은 수를 공백을 기준으로 분리하고 int형으로 바꿔 n, k에 넣기
n, k = map(int, input().split())

result = 0 #연산을 수행하는 횟수

while True:
    #n이 k로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k
    result += (n - target)
    # 1씩 빼주는 과정의 횟수를 result에 더해준다
    n = target
    #n이 k보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if  n < k:
        break
    #k로 나누기
    result += 1
    n //= k

#마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

예를 들어 n = 28 k = 5 의 입력값을 주게 되면 28 // 5 를 통해서 5를 도출할수 있고 5 * 5를 통해서 25라는 k로 나누어 떨어질수있는 값을 구할수가 있게 됩니다. 그렇게 되면 25라는 값을 얻기 위해서 28에서 1을 3번 빼줘야 하기 때문에 (n - target) => (28 - 25) 라는 연산을 하게 되면 3번의 횟수를 구할수가 있게 되고 n이 25일때는 두번째 연산이 성립 되기 때문에 n //= k 를 통해서 25 // 5 5가 도출됨을 볼수가 있다. 이런식으로 작업을 반복하게 되면 횟수가 구해지는 것을 확인할수가 있다.

여기에서 N이 어떤 수라도, K로 계속 나눌수 있다면 빠르게 양을 줄일수 있고, K가 2이상이라면 K로 나누는것이 1로 빼는 것보다 항상 빠르다는것을 확인할수 있기 때문에 최적의 해가 성립이 된다고 확인할수가 있습니다.