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

참고한 책 ; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.

[그리디 알고리즘]

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
• 다시 말해서, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 그리디 알고리즘은 정렬, 최단 경로, 폴로이드 워셜, 다익스트라 알고리즘 처럼 특정 알고리즘을 미리 외우고 있어야문제를 풀 수 있는 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라는 특징이 있다고 한다. (참고로 다익스트라 알고리즘은 엄밀히 말해 그리디로 분류된다고 하니 특이 케이스라 알아두자.)
• 그리디 알고리즘 유형의 문제는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 한다.
• " 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있을 것인가? "

 

[그리디 알고리즘 예시]

• 첫 번째 예시)
  Q : 손님에게 거슬러줘야할 돈이 N원일 때, 거슬러 줘야할 동전의 최소 개수는?
  ANS : ' 가장 큰 화폐 단위부터 ' 돈을 거슬러 주는 것

coin_types = [500,100,50,10]

for coin in coin_types:
	cnt += n // coin
    n %= coin
    
print(cnt)

돈의 종류가 k라고 한다면, 시간 복잡도는 O(k) 가 된다.

 

다음과 같이 탐욕적으로 문제에 접근하여 직관적이고 효과적인 답안을 내는 것이 그리디 알고리즘이다.

 

나는 사실 여기 까지 읽고 아 그렇구나 하고 넘겼는데, 그리디 알고리즘은 절대 여기서 끝내면 안된다고 한다.

그리디 알고리즘은 반드시 그 답안이 타당한지 여부에 대해 검토해야한다.

 

위의 거스름돈 예제의 해답이 맞았던 이유는, 가지고 있는 동전 중 가장 큰 단위가 작은 단위의 배수였기 때문에, 작은 단위를 종합해 다른 해를 낼 수 없기 때문이다. ( 공선성을 띄고 있기 때문에, 가장 큰 단위가 작은 단위의 모든 정보를 포괄하고 있다. )

• 두 번째 예시)
  트리가 있고 각 노드에서 왼쪽과 오른쪽을 선택해 보상을 결정한다고 하자.
  ( 단 방향을 한번 결정하면 그 뒤에 단계에서도 그 방향을 선택하게 된다고 하자. )
  첫번째 단계에서 보상이 10 , 30 이고
  두번째 단계에서 보상이 100, 10 이라고 하자.
  
  만약 그리디 알고리즘 대로 간다면 10 < 30 이므로 오른쪽을 선택할 것이고, 두 번째 단계에서는 10 밖에 얻지 못할 것이다.
  
  당장의 현실 우선 전략이 바로 그리디 알고리즘 이라고 보면 될 것 같다.
  따라서 경제학 관점에서 봤을 때, 장기 균형을 취하고 TVC를 어기지 않기 위해서는 동태적 최적화가 필요한 것이다.
  
  알고리즘 세계에서도 위 트리와 같은 상황일 때는, 동태적 프로그래밍으로 문제를 접근하는게 더 맞는 방식이라고 한다.

---

[실습] 큰 수의 법칙

N, M, K 가 주어진다. 그 뒤 N개의 배열이 주어지는데, 사용자는 N개 배열의 숫자를 이용하되, 같은 숫자를 K번 넘게 더할 수 없고, 총 M번 더할 수 있다. 이렇게해서 만들어지는 가장 큰 수를 구해보자.

 

예를 들어,

# input
5 8 3
2 4 5 4 6

# output
6+6+6+5+6+6+6+5         
<--! 2 4 5 6 6 이 주어졌었다면, 4번째, 5번째 6이 번갈아 8번 나왔을 것이다. -->

# N개 배열, 하나의 숫자는 연달아 K개만 쓸 수 있음, 총 M개의 숫자를 더함
N, M, K = map(int,input().split())
mylist = list(map(int,input().split()))
max_item = 0
max_idx = 0
for i in range(N):                  # max 값과, max의 인덱스 값을 구한다.
    if max_item < mylist[i]:
        max_item = mylist[i]
        max_idx = i

del mylist[max_idx]                # max 값을 소거한 후 최댓값을 구해 두번째로 최댓값을 구했다.
second_item = max(mylist)

ans, cnt = 0, 0
while M > 0:
    if M > K and cnt%(K+1) == 0: # 이전에 두번째 최댓값이 더해졌고, M이 아직 K보다 크면
        ans += K*max_item        # 최댓값을 K개 더한다.
        cnt += K                 # K개 만큼 count가 더해진다.
        M -= K                   # K개 만큼 M에서 K가 빠진다.

    elif M < K and cnt%(K+1) == 0:  # 이전에 두번째 최댓값이 더해졌고, M이 K보다 작으면
        ans += M*max_item           # 남은 M개를 만큼 최댓값을 다 더한다.
        M -= M                      # M이 다 소진되고, While문은 끝이 난다.

    else:
        ans += second_item      # 이전에 max_item 일 때
        cnt += 1                # 두번째로 최댓값을 더한 후, count를 1 센다.
        M -= 1                  # M에서 1 뺀다.
print(ans)

cnt는 이전에 더한 값이 가장 큰 값인지 두번째로 큰 값인지 보려고 선언한 것이다.

 

 

 

 

 

교재 참고한 코드

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

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

first_cnt = M//(K+1) + M%(K+1)
second_cnt = M - first_cnt

ans = first_cnt*first + second_cnt*second
print(ans)

이처럼 숫자 계산해서 계산한 식을 바탕으로 코드를 짜면

코드가 훨씬 간편해지며, 걸리는 시간도 적다.