코딩테스트 - Chapter 03

그리디

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

1. 당장 좋은 것만 선택하는 그리디

거스름돈

💡 가장 큰 화폐 단위부터 돈을 거슬러 준다.

n = int(input())
count = 0

coin_type = [500, 100, 50, 10]

# 큰 단위 화폐부터 차례대로 for 문
for coin in coin_type:
    count += n // coin # count = 거스름돈 / coin의 몫
    n = n % coin

print(count)

2. 큰 수의 법칙

큰 수의 법칙

💡 그리디 알고리즘

n, m, k = map(int, input().split()) # n개의 자연수 중, m번 더하여 가장 큰 수. 중복은 k번까지 가능
data = list(map(int, input().split()))

data.sort()
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수

result = 0

while True:
    for i in range(k) :
        if m == 0:
            break
        result += first
        m -= 1
    if m == 0:
        break
    result += second
    m -= 1

print(result)

💡 반복되는 수열 파악

n, m, k = map(int, input().split()) # n개의 자연수 중, m번 더하여 가장 큰 수. 중복은 k번까지 가능
data = list(map(int, input().split()))

data.sort()
first = data[-1]
second = data[-2]

# count = (횟수 / (연속 first + 1번 second)) * 연속 + (횟수 / (연속 + 1번)의 나머지)
# count = first가 연속으로 더해질 횟수
count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += count * first
result += (m - count) * second

print(result)

3. 숫자 카드 게임

숫자 카드 게임

💡 min() 함수 이용

n, m = map(int, input().split()) # n행 m열

result = 0

for i in range(n) :
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value) # 각 행의 가장 작은 수 중 가장 큰 수

print(result)

💡 2중 반복문 구조 이용

n, m = map(int, input().split()) # n행 m열

result = 0 

for i in range(n) :
    data = list(map(int, input().split()))
    min_value = 10001
    for a in data :
        min_value = min(min_value, a)
    result = max(result, min_value)

print(result)

4. 1이 될 때까지

1이 될 때까지

💡 최대한 많이 나누기 연산 수행

n, k = map(int, input().split()) # n이 1이 될 때 까지 k로 나누기 or -1

count = 0

while n >= k : # n이 k 이상일 경우
    while n % k != 0 : # n이 k 이상이지만 k로 나눈 나머지가 0이 아니면
        n -= 1
        count += 1
    n = n // k
    count += 1

while n > 1 : # n이 k보다 작지만 1보다 큰 경우
    n -= 1
    count += 1

print(count)

💡 N이 K의 배수가 되도록 한 번에 나누기 연산 수행

n, k = map(int, input().split()) # n이 1이 될 때 까지 k로 나누기 or -1

count = 0

while True :
    target = (n // k) * k # target = n에 근접한 k의 배수
    count += (n - target) # n과 target의 차이많큼 -1 연산을 수행함으로 count는 -1 연산 수행 값만큼 추가된다.
    n = target

    if n < k : # n이 k보다 작으면 반복문 탈출
        break
    count += 1
    n //= k

# 마지막 남은 수에서 -1 연산 수행한 횟수 추가
count += (n - 1)
print(result)