이것이 코딩 테스트다

그리디 알고리즘

내용

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

대부분의 경우 많은 유형의 문제를 풀어보는 것이 도움이 된다.
예외적으로 플로이드 워셜, 다익스트라 알고리즘과 같이 미리 알고 있어야 하는 경우도 있다.

주의할 점

' 지금 당장 좋은 것만 고르는 것'은 결과적으로 최선이 아닐 경우가 많다. 따라서 그리디 알고리즘을 진행함에 있어 정당한 것인가 하는 판단을 해야한다.

거스름돈

거스름돈을 낼 때, 가장 적은 동전의 수를 구하는 문제

import sys

coin = [500, 100, 50, 10]
cnt = 0
change = int(sys.stdin.readline())

for i in coin:
    cnt += change // i
    change %= i

print(cnt)

값이 큰 동전이 작은 동전의 배수이므로 큰 돈부터 처리하는 것이 통했다. 하지만 그렇지 아니할 경우, 다른 해결 방법을 찾아야 한다.

큰 수의 법칙

import sys

n, m, k = map(int, sys.stdin.readline().split())

li = list(map(int, sys.stdin.readline().split()))

li.sort()
fst = li.pop()
snd = li.pop()

small_sum = fst*k + snd

result = small_sum*(m//(k+1))

result += (m%(k+1))*fst

print(result)

가장 큰 수와 그 다음 수를 찾고 더하면 되는 단순한 문제. 그리디의 전형이라고 볼 수 있다. sort()를 이용해서 가장 큰 수를 찾는다.

숫자 카드 게임

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

nominee = []
for i in range(n):
    row = list(map(int, input().split()))
    row.sort()
    nominee.append(row.pop(0))
nominee.sort()
print(nominee.pop(n-1))

결과

nominee를 리스트를 이용해서 sort한 후 pop(0)을 하지 않아도 됐다. 반복문에 조건문을 넣어 기존의 값보다 작으면 넘어가면 된다.

1이 될때까지

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

cnt = 0
while True:
    while n % m != 0:
        n -= 1
        cnt += 1
    n /= m
    cnt += 1

    if n == 1:
        break

print(cnt)

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

cnt = 0


while True:
    if n // m != 0:
        tmp = n - (n // m) * m
        cnt += tmp
        n -= tmp
    n //= m
    cnt += 1

    if n == 1:
        break

print(cnt)

결과

그리디 알고리즘 문제에서 주의해야 할 것으로 정당한 것인가 하는 문제도 있었지만 실제 문제를 풀어보니 반복되는 상황을 던져주면 그대로 코딩에 옮기는 경우가 있다. 위 코드처럼 하나하나 빼는 것이 아니라 최적화를 시키기 위해 한 번의 연산으로 처리할 수 있도록 주의해야 한다.