여유로워져서! 저번에 못 읽은 앞부분도 읽어보려고 한다 후후 😎

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

• 그리디 알고리즘이란, 어떠한 문제가 있을 때 단순 무시학하게, 탐욕적으로 문제를 푸는 알고리즘이다.
• 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 암기한다고 해서 잘 푸는 알고리즘은 아니다. 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요하다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 것이므로 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다!
• 정렬 알고리즘과 짝을 이뤄서 제출되는 경우가 많다.

예제 1. 거스름돈

문제

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

해설

그리디 알고리즘의 대표적인 문제. 가장 큰 화폐단위부터 돈을 거슬러 주는 것이다.

n = 1260
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
    count += n // coin
    n %= coin

print(count)

• 화폐의 종류가 K개라고 할 때 위 소스코드의 시간 복잡도는 O(K)다.
• 거슬러줘야 하는 돈과 무관하며, 동전의 종류에 영향을 받는다.

그리디 알고리즘의 정당성

• 모든 알고리즘 문제에 적용할 수 없다! 그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
• 어떤 문제를 만났을 때 문제의 유형을 바로 파악하기 어려울 때는, 그리디 알고리즘을 의심하고 해결법이 존재하는지 고민해보자.

2. 큰 수의 법칙

난이도 하

문제

동빈이의 큰 수 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 더하는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 단, 서로 다른 인덱스의 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

해설

이 문제는 전형적인 그리디 알고리즘 문제다. 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. 연속으로 더할 수 있는 횟수는 최대 K번이므로 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다.

코드

n, m, k = map(int, input().split())
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 # 더할 때마다 1씩 감소
    
    if m == 0: break # m이 0이라면 반복문 탈출
    result += second
    m -= 1  

위 코드로 문제를 해결할 수 있다. 그러나 입력 값이 100억 이상이라면 시간 초과가 뜰 수 있는 코드이다. 간단한 수학적 아이디어로 더 효율적으로 문제를 해결해보자.

그러기 위해서는 가장 먼저 반복되는 수열에 대해 파악해야 한다. 반복되는 수열의 길이는 M을 K+1로 나눈 몫이 된다. 나누어 떨어지지 않을 때는 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다.

int(M / (K + 1)) * K + M % (K + 1)

위의 식을 이용하여 가장 큰 수가 더해지는 횟수를 구하고, 이를 이용해 두 번째로 큰 수가 더해지는 횟수까지 구할 수 있다.

더 효율적인 코드

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort() # 정렬
first = data[n-1]
second = data[n-2]

count = int(m / (k + 1)) * k + m % (k + 1)
count += m % (k + 1)
result = count * first + (m - count) * second

print(result)

3. 숫자 카드 게임

난이도 하

문제

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

카드들이 N * M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

해설

이 문제를 푸는 아이디어는 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다.

코드

• min() 함수를 이용

n, m = map(int, input().split())
result = 0

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

print(result)

4. 1이 될 때까지

난이도 하

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

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

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

해설

주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다. 어떠한 수가 있을 때, 2 이상의 수로 나누는 것이 1을 빼는 것보다 숫자를 훨씬 많이 줄일 수 있기 때문이다.

단순한 정답 코드

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

while n >= k:
    while n % k != 0:
        n-= 1
        result += 1
    n //= k
    result += 1

while n > 1:
    n -= 1
    result += 1

print(result)

좀 더 효율적인 코드

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

while True:
    target = (n // k) * k
    result += (n-target) # 나머지가 있어서 +1 하는 횟수
    n = target
    if n < k : break

    result += 1
    n //= k

result += (n-1)
print(result)

참고자료 : 이것이 코딩 테스트다 (나동빈 저)