이코테_2021 강의 몰아보기_2. 그리디 & 구현

그리디 알고리즘

1.       그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 합니다.

2.       일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.

3.       그리디 해법은 그 정당성이 중요합니다.

A.       단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

4.       일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.

5.       하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다.

 

<문제> 거스름 돈 :

문제 설명 :

1.        최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐를 거슬러 주면 됩니다.

2.        N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줍니다.

A.       이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됩니다.

3.        N =1,650일 때의 에시를 확인해 봅시다.

 

문제해결 아이디어 :

1.        남은 돈 : 1,260원의 거스름돈을 동전의 큰 단위 부터

2.        500원 2개

3.        100원 2개

4.        50원 1개

5.        10원 1 개

 

정당성분석 :

1.        가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까요?
            가장 큰 화폐 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들으 종합해 다른해가 나올 수 없기 때문입니다.

2.        만약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면 어떻게 될까요?

3.        그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 합니다.

 

n = 1260
count = 0
 
# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]
 
for coin in array:
    count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전 세기
    n %= coin
 
print(count)

<문제> 1이 될 때까지: 문제조건

l  난이도 1 | 풀이시간 15분 | 시간제한 2초 | 메모리 제한 128MB

입력조건 첫째 줄에서 N(1<=N<=100,000)과 K(2<=K<=100,000)가 공백을 기준으로 하여 각각 자연수로 주어집니다.

출력조건 첫째 줄에 N이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력합니다.

입력예시 25 5

출력예시 5

주어진 N에 대하여 최대한 많이 나누기를 수행하면 됩니다.

N의 값을 줄일 때 2 이상의 수로 나는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄이 수 있습니다.

예를 들어 N=25, K=3일 때는 다음과 같습니다.

 

단계	연산 과정	N의 값
0단계		N=25
1단계	N에서 1빼기	N=24
2단계	N을 K로나누기	N=8
3단계	N에서 1 빼기	N=7
4단계	N에서 1 빼기	N=6
5단계	N을 K로나누기	N=2
6단계	N에서 1 빼기	N=1

# N, K을 공백기준으로 구분하여 입력받기
n, k = map(int, input().split())
result = 0
 
while True:
    #N이 k로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    #N 이 K 보다 작을 때 (더 이상 나눌 수 없을때) 반복문 탈출
    if n < k:
        break
    #K로 나누기
    result += 1
    n //= k
 
#마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)