그리디 알고리즘(Greedy)이란?

이것이 코딩 테스트다 with 파이썬 - Ch. 3 그리디 알고리즘을 공부하고 기록했습니다.

 

그리디 (Greedy) 알고리즘이란?

- 각 상황에 대해 더 좋은 선택지만 선택하는 알고리즘

 

위 특징처럼 매 순간 좋은 선택지를 고르기에 이후에 발생하는 결과를 고려하지 않는 알고리즘이다.

즉, 매 순간 좋은 결과를 선택하는 방법이 정답을 확실하게 보장하는지 확인해야한다!

 

딱히 별도로 외워야하는 코드 및 그런 건 없다.

그러나, 문제를 보고 최소한 그리디로 풀 수 있다는 걸 확인할 수 있다는 걸 파악하는 게 핵심이다.

즉, 정당성을 검토해봐야한다는 뜻이다!

 

주로 문제 지문에서 힌트가 주어진다.

EX) ''가장 큰 순서대로", "가장 작은 순서대로" 이런 기준을 제시해준다.

 

실전 문제 1. 큰 수의 법칙

목표 : 다양한 수로 이루어진 배열에 주어진 수들을 M번 더해 가장 큰 수를 만든다.

특징 : 특정 인덱스에 해당하는 값이 K번 연속할 수 없다.

입력 조건 : N(배열 크기, 2 <= N <= 1,000), M(합 횟수, 1 <= M <= 10,000), K(반복 제한수, 1 <= K,<= 10,000)

 

Sol) 가장 큰 수와 그 다음으로 큰 수를 찾은 뒤, 가장 큰 수를 K번 반복 후 그 다음으로 큰 수를 1회 더하는 것을 반복하면 된다.

 

단순하게 푼 코드

시간 복잡도 : 반복문 사용으로 인한 O(N) (sort 시간복잡도 고려 X)

import sys
input = sys.stdin.readline

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

arr = list(map(int, input().split()))

# 가장 큰 값과 그 다음으로 큰 값을 구하기에 좋은 방법
# 배열을 오름차순으로 정렬한 뒤, 제일 뒤의 2개의 값을 찾는다. (-2, -1)
arr.sort()
maxVal = arr[-1]
nextVal = arr[-2]
cnt = 0 # 연속해서 더한 횟수 기록용 변수
total = 0 # 전체 합 기록용 변수

for _ in range(M):
    if cnt == K:
        total += nextVal
        cnt = 0
        continue
    total += maxVal
    cnt += 1

print(total)

 

공식으로 푼 코드

시간 복잡도 : O(1)

import sys
input = sys.stdin.readline

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

arr = list(map(int, input().split()))

# 가장 큰 값과 그 다음으로 큰 값을 구하기에 좋은 방법
# 배열을 오름차순으로 정렬한 뒤, 제일 뒤의 2개의 값을 찾는다. (-2, -1)
arr.sort()
maxVal = arr[-1]
nextVal = arr[-2]

repeatarr = maxVal * K + nextVal # 반복되는 arr의 합산

# M번을 K+1번으로 나눈 몫만큼 repeatarr를 곱하고 나머지만큼 최대값을 곱해서 더해주면 된다.
total = (M // (K+1)) * repeatarr
total += (M % (K+1)) * maxVal

print(total)