[코딩테스트] 그리디 알고리즘

그리디 알고리즘

현재 상황에서 당장 좋은 것만 고르는 방법

-> 현재의 선택이 나중에 미칠 영향은 고려하지 않음

-> 문제에서 요구하는 최적의 해를 구할 수 있는지 검토하는 과정이 필요함

 

그리디 알고리즘의 유형은 매우 다양하기 때문에 암기가 어려움

여러 유형을 파악하고 훈련하는 것이 중요함

 

그리디 알고리즘은 기준에 따라서 좋은 것을 선택하는 알고리즘 (크기에 따른 순서 등)

 

 

예제) 거스름돈 문제

거슬러 줘야 할 최소한의 동전 개수 구하기

-> 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함

 

정당성 검토 : 거스름돈 문제를 그리디로 해결할 수 있는 이유는 동전의 큰 단위가 작은 단위의 배수이기 때문임

-> 다른 단위의 동전을 종합해 다른 해가 나올 수 없음

 

만약 거스름돈 종류가 500, 400, 100 등이 있으면(배수가 아니면) 그리디로 풀 수 없음

(800원을 거슬러 줄 때, 그리디 방식으로 하면 500, 100, 100, 100이지만, 400, 400이 더 적은 동전 개수임)

-> 문제 풀이를 위한 아이디어를 도출하고 이것이 정당한지 검토해야 함

 

 

예제) 큰 수의 법칙

배열에 포함된 N개의 자연수를 M개 결합하여 만들 수 있는 가장 큰 값을 구하라.

값은 연속되게 입력할 수 있으며, 최대 K번까지 연속되게 작성할 수 있음

 

반복(수열)이 있는지 파악하자 -> 반복문을 제거할 수 있음!

- for문을 사용한 풀이

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

data.sort(reverse=True)
first = data[0]
second = data[1]

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)

 

- for문 사용하지 않고 문제 풀이

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

data.sort(reverse=True)
first = data[0]
second = data[1]

count = int(M / (K + 1)) * K # 수열의 반복 횟수 * 수열 내 최대값 반복 회수
count += M % (K + 1) # 수열 외 나머지

result = 0
result += count * first # 가장 큰 수 더하기
result += (M - count) * second # 두 번째 큰 수 더하기

print(result)

 

 

 

 

※ 해당 포스트는 이것이 "코딩 테스트다 with 파이썬(나동빈 저)"를 통해 학습한 내용을 정리한 것입니다.