참고 교재

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

예제 1 - 동전 나누기

1
2
3
4
5
6
7
8
9
10
11
12
# 동전 나누기

n = int(input())
count = 0

coins = [500, 100, 50, 10]

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

print(count)

그리디 알고리즘의 정당성

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출 할 수 있다.

실전 문제 1 - 큰 수의 법칙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 큰 수의 법칙
n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()

a, b = data[n - 1], data[n - 2]

result = 0

for i in range(1, m + 1):
  if i % k == 0:
    result += b
  else:
    result += a

print(result)

시간 초과 문제를 해결하기 위한 방법

반복되는 수열에 대해서 파악

큰 수가 더해지는 회수를 미리 계산

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 큰 수의 법칙 최적화
n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()

a, b = data[n - 1], data[n - 2]

count = int(m / (k + 1)) * k
count += m % (k + 1)

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

print(result)

실전문제 2 - 숫자 카드 게임

1
2
3
4
5
6
7
8
9
10
n, m = map(int, input().split())

max_value = 0

for i in range(n):
  data = list(map(int, input().split()))
  data.sort()
  max_value = max(max_value, data[0])

print(max_value)

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수

실전문제 3 - 1이 될때 까지

1
2
3
4
5
6
7
8
9
10
11
12
n, k = map(int, input().split())

count = 0

while n != 1:
  if n % k == 0:
    n //= k
  else:
    n -= 1
  count += 1

print(count)

최대한 많이 나누는 것이 유리하다
효율적으로 빼기위한 방법을 고려해야한다. $target = (n // k) * k$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 효율적인 방법으로
n, k = map(int, input().split())

count = 0

while n != 1:
  if n % k == 0:
    n //= k
    count += 1
  elif n >= k:
    target = (n // k) * k
    count += (n - target)
    n = target
  else:
    break

count += (n - 1) # 남은 수를 더해준다.

print(count)