💡난이도(하)
코드 작성 소요 기대시간 (30분이내)
단순, 무식하게!
현재 상황에서 지금 당장 좋은 것만 고르는 방법
그리디 알고리즘이란
⛓ 그리디 알고리즘 은
사전에 유형을 외우지도 않아도 풀 수 있는 가능성이 높은 유형이다. 예를 들어, 최단 경로를 빠르게 찾아야 하는 문제는 플로이드 워셜(Floy-Warshall) 혹은 다익스트라(Dijkstra) 알고리즘과 같은 특정 알고리즘을 미리 알고 있어야 한다.
*참고) 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘으로 분류되므로, 그리디 알고리즘이면서 '암기' 가 필요한 알고리즘이다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는(탐욕적인) 알고리즘으로 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시한다. 따라서 이 기준은 대체로 정렬 알고리즘와 상응된다.
✔ 예제1. 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.이 문제에서의 아이디어는 '가장 큰 화폐 단위부터 거슬러 주기' 이다.
N = 1260이라고 가정하면,
n = 1260
count = 0
# 큰 단위의 화폐부터 순서대로 확인
coins = [500, 100, 50, 10]
for changes in coins:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)그리디 알고리즘의 정당성
그리디 알고리즘은 모든 알고리즘 문제에 적용 할 수 없다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해' 를 찾을 수 없을 가능성이 높다.
하지만 거스름돈 문제와 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 땐 매우 효과적이다!
따라서, 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 방법이 정당한지 검토해봐야 한다.
예를 들어, 800원을 거슬러 줘야하는데 화폐단위가 [500, 400, 100]원 인 경우
그리디 알고리즘에 의하면 4개의 동전 (500+100+100)으로 거슬러 줘야 한다. 하지만 잘 생각해 보면 동전 2개를 사용하는 (400+400) 이 '최적의 해'가 된다.
예제2. 1이 될 때 까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행한다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구해라.
(단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.)<조건>
1번. N에서 1을 뺀다.
2번. N을 K로 나눈다.첫 줄에 N(2<=N<=100,000) , K(2<=K<=100,000)가 공백으로 구분되며 각각 자연수로 주어진다. (N>=K)
import sys
N, K = map(int,input().split())
result = 0
while (1):
# (N==K로 나누어떨어지는 수) 가 될 때까지 1씩 빼기
target = (n//k)*k
result +=(n-target)
n = target
# N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 나옴.
if N < K :
break
result += 1
N //= k
# 마지막으로 남은 수 에 대해 1씩 뺌
result += (n-1)
print(result)