[Algorithm][Python] 탐욕(Greedy) 알고리즘

이제부터 제대로된 알고리즘 공부를 시작해 보고자 합니다. 그래서 첫 번째로 공부할 알고리즘은 탐욕(Greedy) 알고리즘에 대해서 공부를 해보도록 하겠습니다.

탐욕(Greedy) 알고리즘이란?

탐욕(Greedy, 앞으로는 그리디라는 용어로 사용하도록 하겠습니다) 알고리즘이란 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 입니다. 탐욕적이라는 의미는 현재 상화에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

코딩 테스트에서 만나게될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있습니다. 그리디 알고리즘 유형의 문제는 매우 다양하기 때문에 다른 암기해야 하는 알고리즘들과는 다르게 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아닙니다. 그리디 알고리즘은 사전 지식이 없어도 풀 수는 있지만 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 합니다.

보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠오릴 수 있는 능력을 요구합니다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악할 수 있어야 합니다. 그래서 이번 그리디 알고리즘의 경우에는 여러 문제를 다뤄보면서 그리디 알고리즘 문제는 어떻게 다루어야 하는지 알아보도록 하겠습니다.

큰 수의 법칙 문제

큰 수의 법칙은 일반적으로 통계 분야에서 다루어지는 내용이지만 철수는 본인만의 방식으로 다르게 사용하고 있다. 철수의 쿤 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

입력 조건

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

출력 조건

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

입력 예시
5 8 3
2 4 5 4 6

출력 예시
46

문제 해설

이 문제는 전형적인 그리디 알고리즘 문제로, 문제 해결을 위한 아이디어를 떠올리는 것은 어렵지 않습니다. 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 그 다음으로 큰 수만 구하면 됩니다. 연속으로 더할 수 있는 횟수는 최대 K번 이므로 가장 큰 수를 K 번 더하고 두 번째를 큰 수를 한 번 더하는 연산을 바놉갛면 됩니다. 아래는 제가 짠 코드와 제가 참고한 책에 있는 코드입니다.

#제가 직접 짠 코드
n, m, k = map(int, input().split())
number_list = list(map(int, input().split()))

number_list.sort()

first_large_number = number_list[n-1]
second_large_number = number_list[n-2]

cnt = 0
result = 0

while True:

    for i in range(k):
        if cnt == m:
            break
        result+=first_large_number
        cnt+=1

    if cnt == m:
        break

    result+=second_large_number
    cnt+=1

print(result)

#책에 있는 코드
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)

추가적으로 문제에서는 M 이 10,000 이하이므로 위의 로직을 이용해도 큰 문제는 없습니다. 하지만 만약에 M 의 크기가 100억 이상처럼 커진다면 위 로직으로는 시간 초과를 받을 수 있습니다. 이럴 때에는 문제에서 수학적인 접근을 통해 단순한 수학적 연산만으로 해답을 구할 수 있으며, 이러한 연습도 꾸준하게 해주어야 합니다.
이 문제에서는 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특수한 수열 형태로 일정하게 반복해서 더해지는 특징이 있습니다. 반복되는 수열의 크기는 K+1 이며 이 반복되는 수열은 M 의 크기 내에서 반복이 됩니다. 그렇다면 우리는 k가 반복되는 개수와 그 나머지 개수를 구한 다음에 가장 큰 수와 두 번째로 큰 수에 각각 구한 개수를 곱해주면 됩니다.

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 += (count) * first
result += (m-count) * second

마치며

오늘은 그리디 알고리즘에 대해서 알아보았습니다. 그리디 알고리즘은 사실 어떤 기법이 있는 것은 아니며 문제 해결을 위한 가장 적법한 방법을 찾고 그것을 구현하는 것이라고 생각합니다. 다만 몇몇 문제들 중에서는 암기해서 푸는 문제들도 있을 듯 합니다. 그래서 그리디 알고리즘은 문제들을 많이 풀어야 한다고 생각하며, 추후에 알고리즘 개념들을 모두 정리한 후 문제 푸는 과정에서 그리디 알고리즘 문제 풀이를 진행하는 것으로 그리디 알고리즘 심화 공부를 진행할 예정입니다. 긴 글 읽어주셔서 감사드리며, 내용 중에 잘못된 것, 오타 혹은 궁금하신 내용이 있으시다면 댓글 달아주시기 바랍니다.