그리디(Greedy) 알고리즘

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

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

• 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
• 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함.
• 주로 정렬 알고리즘과 짝을 이뤄 출제됨.
• 그리디 알고리즘 해법의 정당성 검토할 것.

예제) 거스름돈

문제

손님에게 거슬러 줘야 할 돈이 N원일 때, 500원, 100원, 50원, 10원짜리 동전을 이용하여 거슬러줘야 할 동전의 최소 개수를 구하시오.

IDEA

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

풀이

N = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
  count += N//coin
  N = N%coin

print(count)

• 화폐의 종류만큼 반복 수행 => 시간 복잡도 O(K) (K : 화폐의 종류)
  • 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관함.
• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없으므로 정당한 아이디어

---

2. 큰 수의 법칙

문제

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

<동빈이의 큰 수의 법칙>

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

입력 조건

• 첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

IDEA

주어진 자연수 중 가장 큰 두 개의 수를 저장하고, 가장 큰 수를 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]

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)

• for문을 이용하여 가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 코드 작성
• 각 연산을 수행할 때마다 m-1을 계산, m이 0이 되는 경우 반복문 중단

방법 2

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
count += m%(k+1)

result = 0
result += first * count # 가장 큰 수 더하기
result += (m-count) * second # 두 번째로 큰 수 더하기

print(result)

• '가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산'이 몇 번 반복되는지를 생각하자!
  • 위 연산은 M // (K+1) 만큼 반복 후, 남은 횟수만큼 가장 큰 수를 더함. 즉,
  • 가장 큰 수를 더하는 횟수 : (M // (K+1)) * K + M % (K+1)
  • 두 번째로 큰 수를 더하는 횟수 : M // (K+1) = M - (가장 큰 수를 더하는 횟수)

---

3. 숫자 카드 게임

문제

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

<게임의 룰>

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

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 <= N, M <= 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10000 이하의 자연수이다.

출력 조건

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

IDEA

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

풀이

방법 1

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)

• min() 함수를 이용하여 각 행에서의 최솟값 구하기
• max() 함수를 이용하여 각 행에서의 최솟값 중 최댓값 구하기

방법 2

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

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(min_value, result)

print(result)

• for문을 이용하여 각 행에서의 최솟값 구하기
• max() 함수를 이용하여 각 행에서의 최솟값 중 최댓값 구하기

---

4. 1이 될 때까지

문제

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

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

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

입력 조건

첫째 줄에 N (2 <= N <= 100000)과 K (2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력 조건

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

IDEA

최대한 많이 나누기

1. N이 K의 배수가 될 때까지 1씩 빼기
2. N을 K로 나누기

풀이

방법 1

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

while n >= k: # n이 k 이상이면 k로 계속 나누기
  while n % k != 0: # n이 k로 나누어 떨어지지 않는다면 n에서 1씩 빼기
    n -= 1
    result += 1
  n //= k
  result += 1

while n > 1: # 마지막으로 남은 수에 대하여 1씩 빼기
  n -= 1
  result += 1

print(result)

• while문을 이용하여 n이 k 이상이라면 k로 계속 나눈다.
  • 만약 n이 k로 나누어 떨어지지 않는다면 n에서 1씩 뺀다.
• 마지막으로 남은 수에 대하여 1씩 뺀다.

방법 2

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

while True:
  target = (n // k) * k # n이 k로 나누어떨어지는 수가 될 때까지 1씩 빼기
  result += (n - target)
  n = target
  if n < k:
    break
  result += 1
  n //= k

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

• n이 k로 나누어떨어지는 수를 구하고, 그 수가 될 때까지 1씩 뺀다. (while문 이용 X)
• 이후 k로 나눈다.
• n이 k보다 작은 수가 될 때까지 반복하고, 남은 수에서는 1씩 뺀다.