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

• 매 순간 가장 좋아보이는 것 선택.
  (현재의 선택이 나중에 미칠 영향 고려 x)
• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 (정렬, 최단경로와 다르게)
• 암기한다고 항상 잘 풀 수 있는 유형이 아님, 많은 유형을 접해보고 훈련을 해야 함
• 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구!

✅ 예제) 거스름 돈

가장 큰 화폐 단위부터
돈을 거슬러 주는 것 (500, 100, 50, 10)

화폐의 종류가 $K$개라고 할 때, 시간 복잡도 $O(K)$

• 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관

🔅 해결 아이디어

가장 큰 화폐부터 돈을 거슬러 주기
(500->100->50->10)

n = 1260
cnt = 0

coin_types = [500,100,50,10]

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

print(cnt)

그리디 알고리즘의 정당성
: 대부분의 문제는 이 알고리즘을 사용했을 때 '최적의 해'를 찾을 수 없는 가능성 다분

그러나 이 문제는
가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로
작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 가능했던 것

ex) 화폐 단위가 500, 400, 100일 경우에 800원을 거슬러 준다 할 때
그리디 알고리즘(500,100,100,100)은 실제 최적의 해(400,400)와 다른 결과값을 가짐

따라서,
그리디 알고리즘은
최소한의 아이디어를 떠올리고
이것이 정당한지 검토해야 함

TIP 코딩 테스트의 문제 유형을 파악하기 어렵다면
그리디 알고리즘을 의심하고,
해결할 수 있는 탐욕적인 해결법이 존재하는지 고민할 것

✅ 큰 수의 법칙

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

• $N$: 배열의 크기

🔅 해결 아이디어

입력값 중에서 가장 큰 수와 두번째로 큰 수 저장
-> 가장 큰 수를 $K$번 더하고 두번째로 큰 수를 $1$번 더하는 과정을 반복

➰ 풀이 1 (복잡)

# 공백으로 구분하여 입력 받기
n, m, k = map(int, input().split())
num_list = list(map(int, input().split()))

idx_max1 = 0
for i in range(len(num_list)):
  if num_list[i] > num_list[idx_max1]:
    idx_max1 = i

idx_max2 = 0
for i in range(len(num_list)):
  if i != idx_max1 and num_list[i] > num_list[idx_max2]:
    idx_max2 = i

cnt = 0
result = 0
while cnt <= int(m):
  for j in range(int(k)):
    cnt += 1
    if (cnt > int(m)):
      break
    result += num_list[idx_max1]

  cnt += 1
  if (cnt > int(m)):
    break
  result += num_list[idx_max2]

print(result)

Review1 sort를 하지 않고 직접 for문을 돌려서 찾으니 매우 비효율적인 코드임

Review2 idx를 저장하지 않고 그냥 값을 저장하는게 빨랐음

Review3 횟수를 세는 cnt 필요 없었고 그냥 m을 이용하면 더 나았음

➰ 풀이 2 (교재 참조)

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

num_list.sort()
first = num_list[n - 1]
second = num_list[n - 2]

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

  if (m == 0):
    break
  result += second
  m -= 1

print(result)

Problem
이 경우에는 M이 10,000 이하이므로
이 방식으로도 문제를 해결할 수 있지만,
M의 크기가 100억 이상으로 커진다면 시간 초과일 것
($O(k * m)$이기 때문에)

➰ 풀이 3 (교재 참조)