그리디 알고리즘

<aside> 💡

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

</aside>

3-1 거스름돈

• 문제

def change() :
    N = int(input("Enter a new value: "))
    coin_type = [500, 100, 50, 10]
    answer = 0
    for coin in coin_type :
        quotient = N // coin
        N = N % coin
        answer += quotient
    print("The number of coins is: ", answer)

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘을 사용

• 화폐의 단위가 서로 배수 형태가 아니라면?

3-2 큰 수의 법칙

• 문제

풀이

# 1. 입력 받기
N, M, K = map(int, input().split())
number_list = list(map(int, input().split()))

# 2. 정렬
number_list.sort()

# 3. 가장 큰 수와 그 다음 큰 수
first = number_list[N-1]
second = number_list[N-2]

# 4. 사용된 횟수 구하기
first_count = (M // (K+1)) * (K) + M % (K+1)
second_count = M // (K+1)
result = first * first_count + second * second_count
print(result)

• m이 매우 큰 숫자라면? (시간복잡도를 한번 계산해봅시다)

3-3 숫자 카드 게임

• 문제

풀이

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

min_value_list = []
# 한 줄씩 입력 받아 확인
for i in range(n) :
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)
    min_value_list.append(min_value)
# 가장 작은 수들 중에서 가장 큰 수 찾기
result = max(min_value_list)
print(result)

.

예시답안

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

3-4 1이 될 때까지

• 문제

풀이

N, K = map(int, input().split())
count = 0
while (N != 1) :
  if (N % K == 0) : 
    N = N // K
    count += 1
  else : 
    N = N-1
    count += 1
print(count)

예시답안

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    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)