🙂TIL from lecture

---

Greedy Algorithm

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

🔑 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구

🔑 정당성 분석이 중요!

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

: 최적의 해가 보장되지 않기 때문

ex) 거스름 돈

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재할 때,
손님에게 거슬러 줄 N원의 최소 동전의 개수를 구하시오. 단, N은 항상 10의 배수

• 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유?
  가지고 있는 동전의 큰 단위가 항상 작은 단위의 배수이므로
  → 작은 단위의 동전들을 종합해 다른 단위가 나올 수 없기 때문
  

cf) 800원을 거슬러야 하는데 화폐 단위가 500, 400, 100 인 경우

n = 1260
count = 0

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

for coin in mon:
	count += n//coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수
	n %= coin # 해당 화폐 단위 보다 작은 단위가 필요한 돈

print(count)

화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도 O(k)

🏆Today Code Test

---

🛠Problem Approach

'''
문제 : 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행
(단, 두번째 연산은 N/K로 나누어 떨어질때만!)

1. N - 1
2. N / K

! 정당성
# 2번을 수행하는 게 최소값을 만드는 데 유리 -> 나누기는 N 값을 크게 낮추므로
# 1번은 2번을 수행하지 못할때만 수행하는 방법 사용
'''

N, K = map(int, input().split())
count = 0

while N != 1: # N이 1이 아닐 동안 실행
    count += 1
    if N % K == 0: # N이 K의 배수이면
        N //= K # 몫을 N으로
    else:
        N -= 1

print(count)

시간복잡도 O($k$) : count의 횟수 만큼

🔑Solution

✅정당성
: N이 아무리 큰 수여도 K(K ≥ 2)로 계속 나눈다면 기하 급수적으로 빠르게 수를 줄일 수 있음!

## 코드 솔루션

N, K = map(int, input().split())
res = 0

while True:
	target = (N//K)*K # N보다 작은 K의 최대 배수 값
	result += (n - target) # K의 배수가 아닐 시, 1번 과정(-1)을 수행 해야하는 값
	n = target # K의 최대 배수 값
	if n < k: # K보다 작아서 나눠지지 않은 값이 있다면 반복문 탈출
		break
	result += 1 # N/K를 계산한 횟수 증가 시키기
	n //= k # K로 나눠 줄인 N값 계산하기

result += (n-1) # K보다 작아서 나눠지지 않은 값이 있다면 1이 될때까지 1단계 수행하는 값 더해주기

print(result)

시간복잡도 O($\log{k}$)

→ 한 반복문 안에서 1, 2단계가 동시 수행되기 때문에 큰 수 일수록 더 유리하다