탐욕 알고리즘 ( Greedy Algorithm )

'그리디' 로 구글링하니 나오는 귀여운 그리디 ..

Greedy Algorithm

그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 한다 

이름에서 알 수 있듯이 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다

정렬이나 최단경로 등의 알고리즘 유형은 알고리즘의 사용 방법을 정확히 알아야 하지만

그리디는 단순하면서 강력한 해결법이기 때문에 딱히 그렇지 않다 !

 

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

문제에서 '가장 큰 순서대로' '가장 작은 순서대로' 같은 힌트를 잘 캐치하면 된다 !

그리디 알고리즘 문제는 주로 정렬 알고리즘과 함께 출제된다

---

대표적인 거스름돈 !

거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 무수히 존재한다고 가정한다

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다

 

그리디 알고리즘의 대표적인 문제인 거스름돈 문제이다

최소의 동전 개수를 거슬러 주기 위해서는 .. 하고 생각해보자

 

최소의 개수로 거슬러 주기 위해서는 간단히 '가장 큰  화페 단위부터' 돈을 거슬러주면 된다

N원을 거슬러줄때 500원부터 10원짜리로 순서대로 !

# 1260원을 거슬러줘야한다고 가정
n = 1260
cnt = 0

# 큰 단위의 화페부터 차례대로
coin = [500, 100, 50, 10]

for c in coin:
	cnt += n //c # 해당 화페로 거슬러 줄 수 있는 동전의 개수 세기
    n %= c

print(cnt)

---

그리디 알고리즘의 정당성

그리디 알고리즘은 문제 풀이를 위한 최소한의 아이디어를 떠올려보고

위 문제처럼 탐욕적으로 접근했을 때 찾은 답이 최적인 경우 사용하면 된다

 

다양한 아이디어를 고민해보고 그리디로 최적의 해를 보장할 수 잇다면 사용하면 된다

 

코딩 테스트에서 문제 유형을 파악하기 어렵다면 먼저 그리디 알고리즘을 의심해보고

그리디 알고리즘으로 해결할 수 없다면 다이나믹 프로그래밍 또는 그래프 알고리즘을 고민해보면 좋다 !

---

큰 수의 법칙

' 다양한 수로 이루어진 배열이 존재할 때 주어진 수들을 M번 더하여 가장 큰 수를 구하라 ' 는 문제이다

배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 더할 수 있는 횟수 K 가 주어진다

 

입력 조건은 N( 2 ≤ N ≤ 1,000 ), M( 1 ≤ M ≤10,000 ), K( 1≤ K ≤ 10,000 ) 가 주어지며 이는 공백으로 구분한다

둘째 줄에는 N개의 자연수가 주어지며 1 이상 10,000 이하의 수가 공백으로 구분된다

N, M, K = map(int,input().split())
data = list(map(int, input().split()))

data.sort(reverse=True)
biggest = data[0]
next = data[1]

result = 0

while True:
  for _ in range(K): # 가장 큰 수를 최대 연속 횟수만큼 더하기
    if M == 0:
      break
    result += biggest
    M -= 1
    
  if M == 0:
    break
  result += next # 두 번째로 큰 수를 한 번 더해주기
  M -= 1
print(result)

이 문제를 풀려면 가장 먼저 반복되는 수열에 대해 파악해야 한다

가장 큰 수를 K번 더하고 두 번째로  큰 수를 한 번 더하는 연산을 반복하면 된다

---

하지만 현재 M 이 10,000 이하이므로 통과할 수 있지만 !

M 의 크기가 100 억 이상 커진다면 시간 초과 에러가 날 수 있다

동일하게 큰 수와 두번째로 큰 수를 지정하되 복잡도를 위해 반복문을 수정해보자 !

N, M, K = map(int,input().split())
data = list(map(int, input().split()))

data.sort(reverse=True)
biggest = data[0]
next = data[1]

# 가장 큰 수가 더해지는 횟수 계산
cnt = int(M/(K+1)) * K
cnt += M % (K+1)

result = 0
result += cnt * biggest # 가장 큰 수 더하기
result += (M-cnt) * next # 두 번째로 큰 수 더하기

print(result)

따란 ! 답을 맞추는 것도 중요하지만 조건에 맞춰 시간 초과 등 코드의 효율성을 생각하며 푸는 것도 중요하다 

---

참고

나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬, 한빛미디어 (2021)