그리디 알고리즘

현재 상황에서 지금 당장 좋은것만 고르는 방법

현재 상황에서 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할수 있다는 것은 아님

최적의 해를 보장할 수 없을 때가 많지만 최적해에 가까운 값을 구할때 사용

ex) 거스름돈 문제

<aside> 💡

거스름돈으로 500원, 100원, 50원, 10원 동전이 무수히 많이 존재할때 손님에게 거슬러 줄 돈 N원을 최소 개수의 동전으로 주는 방법. 단, 거슬러 줘야 할 돈은 항상 10의 배수.

</aside>

최적해를 빠르게 구하기 위해서 가장 큰 화폐 단위부터 거슬러줌

가장 큰 화폐부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 정당성이 필요함

⇒ 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기 때문. 그렇지 않다면 정당한 방법이 아님.

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
    count+= n //coin
    n%=coin
print(count)

시간복잡도: 화폐 개수가 K일때 O(K)

ex) 1이 될때까지

<aside> 💡

어떤 수 N이 1이 될때까지 다음의 두 과정중 하나를 반복적으로 수행한다.

두번째 연산은 N이 K로 나누어질때만 선택할 수 있다.

1. N에서 1을 뺀다
2. N을 K로 나눈다.

N과 K가 주어질 때 N이 1이 될때까지 수행해야하는 최소 횟수를 구해라.

1 ≤ N ≤ 100000, 2 ≤ K ≤ 100000 인 자연수

</aside>

n,k = map(int, input().split())

count = 0
while(n != 1):
    if(n % k == 0):
        n = n//k
        count+=1
    else:
        n-=1
        count+=1
print(count)

최대한 많이 나누기를 수행해아함. 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 더 많이 줄일 수 있기 때문.

ex) 곱하기 혹은 더하기

<aside> 💡

각 자리가 숫자로만 이루어진 문자열 S가 주어졌을때 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 곱하기 혹은 더하기 연산자를 넣어 만들수 있는 가장 큰 수를 구해라.

모든 연산은 왼쪽부터 오른쪽으로 이루어진다.

</aside>

data =input()

result = int(data[0])

for i in range(1, len(data)):
    num = int(data[i])
    if num <= 1 or result <= 1:
        result+=num
    else: 
        result*=num
print(result)

일반적으로 곱하기 연산이 더하기 연산보다 더 값을 크게 만든다

하지만 두 수중에서 하나라도 0혹은 1인 경우 곱하기보다는 더하기를 수행하는것이 효율적이다