[Algorithm] 그리디(Greedy) 알고리즘

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

그리디(Greedy) 알고리즘

: 탐욕적 알고리즘의 뜻은, '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.
따라서, 매순간 가장 좋아보이는 것을 선택하게 되며, 현재의 선택이 미래에 어떤 영향을 미칠지 고려하지 않는 것이다.

따라서 그리디 알고리즘은 '정당성 분석'이 중요하다.

단순히 현재 best를 선택해도 그게 최적의 해가 되는지 검토가 필요하다는 소리이다!

 

코딩 테스트에서 그리디 알고리즘의 문제유형은

'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이다.

반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은

이미 그 알고리즘의 사용방법을 정확하게 알아야 하는 경우가 많다.

또한, 그리디는 기준에 따라 좋은 것을 선택하는 알고리즘이므로

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.

대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로

그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

---

실제 모든 경로를 다 계산해보고 그 중 최적의 해가 나오는 경우를 찾으면 best가 되겠지만 (첫번째 사진 = 21)

이 경우 시간이 매우 많이 소요된다.

따라서, 탐욕법은 현재 순간에 가장 최선의 선택을 하는 방법을 사용한다.(두번째 사진 = 19)

이와 같이 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

하지만, 코딩테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

---

# 예제 3-1. 거스름돈

 

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

why? 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

예를 들어 N = 1,260일 때를 고려해보자.

• 500원의 개수는 1,260 // 500 = 2(개)
• 100원의 개수는 1,260 % 500 = 260 // 100 = 2(개)
• 50원의 개수는 260 % 100 = 60 // 50 = 1(개)
• 10원의 개수는 60 % 50 = 10 // 10 = 1(개)

 

코드 분석

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500,100,50,10]

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


print(count)

 

시간 복잡도 분석

화폐의 종류가 K개라면 시간 복잡도는 O(K)이다.

이는 동전의 총 종류에만 영향을 받고, 거슬러줘야 하는 금액과 무관하다.

 

# Tip

바로 문제 유형을 파악하기 어렵다면 -> 그리디 알고리즘 의심하고, 탐욕적인 해결법 존재하는지 고민하기

만약 동전의 단위가 서로 배수가 아닌 경우는 그리디 알고리즘으로 풀 수 없다
(다이나믹 프로그래밍에서 해결해야 함_8장)

 

---

# 2. 큰 수의 법칙

큰수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징

 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M = 8이고 K = 3이라고 가정하자

이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로, 큰 수의 법칙에 따라

(6 + 6 + 6) + 5 + (6 + 6 + 6) + 5 = 46이 된다.

 

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

예를 들어 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때, M = 7이고 K = 2라고 가정하자

이 경우에는 두번째의 4와 네번째의 4를 번갈아 두번씩 계산하는 것이 가능하다.

(4 + 4) + (4 + 4) + (4 + 4) + 4 = 28

 

 

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

arr.sort(reverse=True)
first = arr[0]
second = arr[1]

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

print(result)

 

위의 예제는 M이 10,000이하이므로 이 방식으로도 문제를 해결할 수 있지만,
M의 크기가 100억 이상만큼 커진다면 시간 초과 판정을 받을 것이다.

수학적인 아이디어를 이용해 더 효율적으로 처리해보자!

 

예를 들어, N = 5이고, 다음과 같은 배열이 있다고 하자. (2, 4, 5, 4, 6)

first = 6이고 second = 5이므로, M = 8이고 K = 3일 때

(6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46일 것이다.

즉, 특정한 (K+1길이의) 수열 형태로 일정하게 반복해서 더해지는 특징을 갖는다. 

• first가 등장하는 횟수는 (M // (K+1)) * N = (8 // 4) * 3 = 6
• second가 등장하는 횟수는 M // (K+1) = 8 // 4 = 2

 

그런데 만약에 K+1이 M에 나누어 떨어지지 않는 경우는 어떻게 표현할 수 있을까?

예를 들어, M = 11이라고 가정한다면

(6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) + (6 + 6 + 6) = 54이다.

💡 first가 등장하는 횟수는 $$(M//(K+1))*N+M%(K+1)$$

(11 // 4) * 3 + 11 % 4 = 9

💡 second가 등장하는 횟수는 $$M - first 횟수$$

11 - 9 = 2

 

코드를 다시 짜면 다음과 같다.

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

arr.sort(reverse=True)
first = arr[0]
second = arr[1]

cnt = (m // (k+1)) * k
cnt += m % (k+1)

result += first * cnt
result += second * (m-cnt)

print(result)

 

💡
cnt = (m // (k+1)) * k
cnt += m % (k+1)

 

 

---

# 3. 숫자 카드 게임

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

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

 

 

💡 '각 행마다 가장 작은 수를 찾은 후에 그 수에서 가장 큰 수'를 찾는 것

리스트에서 가장 작은 원소를 찾아주는 min() 함수를 이용하자!

 

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

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

print(result)

 

---

# 4. 1이 될 때까지

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

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

이때, 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하라.

예를 들어, N = 17이고 K = 4일 때

• step1) 17 - 1 = 16
• step2) 16 / 4 = 4
• step3) 4 / 4 = 1

다음과 같은 순서로 진행되고 실행한 횟수는 3회이다.

 

💡 '최대한 많이 나누기'

따라서 초반에 나누어 떨어질 수 있을만큼 1을 빼고 이후에 연속해서 나누기를 하는 편이 좋음

 

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

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

  # k로 나누기
  n = n / k
  cnt += 1

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

print(cnt)

 

위의 문제에서는, N의 범위가 10만 이하이므로, 일일이 1씩 빼고 문제를 해결할 수 있다.

하지만, N이 100억 이상의 큰 수가 되는 경우를 가정했을 때도 빠르게 동작하려면,

N이 K의 배수가 되도록 효율적으로 한번에 빼는 방식으로 소스코드를 수정할 수 있다.

 

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

while True:
  # target 변수: 나누어 지는 수
  target = (n // k) * k
  cnt += (n - target)
  n = target

  # N이 K보다 작을 때 더 이상 나눌 수 없으므로 반복문 탈출
  if n < k:
    break

  cnt += 1
  n //= k

# 마지막으로 남은 수에 대해서 1씩 빼기
cnt += (n-1)
print(cnt)

💡  target = (n // k) * k

 

두 코드 비교를 보면, 확실히 코드를 수정할 필요성이 있다.

 

 

---

 

'큰수의 법칙'과 '1이 될때까지' 문제 유형에서 알 수 있듯이

N이 클 때를 대비하여 타임 리밋을 초과하지 않기 위해

반복문을 통과하는 횟수를 줄이기 위한 방법을 잘 알아두는 것이 중요할 것 같다.