[이것이코딩테스트다with파이썬] 그리디

 

 

당장 좋은 것만 선택하는 그리디(탐욕법)

 

* 현재 상황에서 지금 당장 좋은 것만 고르는 방법 * 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

 

 

 

예제 1) 거스름돈

 

 

문제)

 

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

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

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

 

문제 해설)

 

'가장 큰 화폐 단위부터' 돈을 거슬러 준다.

=> 근거 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을

종합해 다른 해가 나올 수 없다. (그리디 알고리즘의 정당성 검토)

 

만약, 주어진 거스름돈 동전의 단위가 서로 배수 형캐가 아니라, 무작위로 주어졌다면?

=> 그리디 알고리즘의 정당성이 보장되지 않는다. -> 다이나믹 프로그래밍으로 해결 가능

 

 

문제 풀이)

# 거스름돈 금액
n = 1260
# 동전의 개수
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    # // 연산자 : 나누기 연산 후 소수점 이하의 수를 버리고, 정수 부분의 수만 구함
    count += n // coin
    # 원래 금액에서 현재 코인의 단위로 나눈 후 남은 금액을 n에 다시 저장함
    n %= coin

print(count)

 

 

 

문제 1) 큰 수의 법칙

 

 

문제)

 

큰 수의 법칙 : 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 연속 가능 횟수 K

 

[입력 조건]

* 첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며,

각 자연수는 공백으로 구분한다.

* 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.

단, 각각의 자연수는 1이상 10000이하의 수로 주어진다.

* 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

 

문제 해설)

 

문제 해결을 위해 입력값 중에 가장 큰 수와 두번째로 큰 수만 저장하면 된다.

-> 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 가장 큰 수를 도출해낼 수 있다!

 

 

문제 풀이)

 

* 단순하게 푸는 답안

 

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))
# 결과
result = 0
# 더하는 숫자를 세기 위한 변수
count = 0
# 제일 큰 수 True 두번째 큰 수 False
IsMax = True

data.sort()  # 입력받은 수들 정렬하기
big = data[-1]  # 첫번째로 큰 수
secondbig = data[-2]  # 두번째로 큰 수

# k만큼씩 더하면서 총 m번을 더해야 함
# 더하는 수는 첫번째로 큰 수 big, 두번째로 큰 수 secondbig만 있으면 됨
# 첫 번째 큰 수와 두 번재 큰 수를 번갈아가면서 k번씩 더하되, m번의 횟수가 채워지면 그만하도록

while m > 0:
    if m > k:
        if IsMax:
            result += big * k
            m -= k
            IsMax = False
        elif not IsMax:
            result += secondbig
            m -= 1
            IsMax = True
    else:
        if IsMax:
            result += big * m
            m = 0
        elif not IsMax:
            result += secondbig
            result += big * (m-1)
            m = 0

print(result)

 

위 코드의 방식으로도 해결 할 수 있지만

M의 크기가 100억 이상으로 커진다면 시간 초과 판정을 받을 것이다.

 

=> 수학적 아이디어 를 이용해보자!

 

* 반복되는 수열에 대해서 파악

 

 

만약 K가 3이고 가장 큰 수가 6, 두번째로 큰 수가 5라면

[ 6 6 6 5 ]가 반복된다.

따라서 반복되는 수열의 길이는 K+1이다.

이에, M을 K+1로 나눈 몫이 수열이 반복되는 횟수가 된다.

즉 int( M / ( K + 1 ))만큼 [ 6 6 6 5 ]가 반복되는 것이다.

여기에 K를 곱해주면 가장 큰 수인 6이 등장하는 횟수가 된다.

=> int( M / ( K + 1 )) * K

 

수가 완전히 나누어 떨어지지 않는다면

가장 큰 수인 6이 남은 횟수만큼 더해질 것이다.

즉 나머지인 M % ( K + 1 )회가 된다.

 

이를 한 줄로 표시하면

 int(M / (K + 1)) * K + m % (K + 1) 

 

 

* 반복되는 수열을 이용한 답안

 

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort()  # 입력받은 수들 정렬하기
first = data[-1]  # 첫번째로 큰 수
second = data[-2]  # 두번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1)) * k
count += m % (k + 1)

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

print(result) # 최종 답안 출력

 

 

정리)

 

수열에 대한 문제는 특히 그리디 문제를 사고력 있게 풀도록 일깨워준 좋은 문제였던 것 같다.

단순히 푸는 것에 초점을 맞추기보다 어떻게 하면 잘 짜여진 코드를 구현하는지에 중점을 두어야 할 것 같다.