Python [AtoZ] Chapter 03. 그리디

[ Table of Contents ]

당장 좋은 것만 선택하는 그리디

1. 정렬 알고리즘과 같이 출제

2. 거스름돈 문제

3. 그리디 알고리즘의 정당성

 

실전 문제

1. 큰 수의 법칙

2. 숫자 카드 게임

3. 1이 될 때까지

 

 

기출 문제

1. 모험가 길드

2. 곱하기 혹은 더하기

3. 문자열 뒤집기

4. 만들 수 없는 금액

5. 볼링공 고르기

6. 무지의 먹방 라이브

[ Abstract ]

0. 그리디 알고리즘은 최적의 해를 구하기 위함

1. 문제를 보고 점화식 세우는 연습하기 ex)큰 수의 법칙 : count = int(m/(k+1))*k + m%(k+1)
2. 문제에서 1을 먼저 빼라고 해도, 나누기 연산부터하는 코드를 짜는 것이 효율적이다. ex) 1이 될 때까지

 

당장 좋은 것만 선택하는 그리디

그리디Greedy 알고리즘은 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘으로, 단순하지만 강력한 문제 해결 방법이다.

코딩 테스트에서 만다게 될 그리디 알고리즘의 문제 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 반면, 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다.

예를 들어 최단 경로를 빠르게 찾아야 하는 문제는 플로이드 워셜Floyd-warshall 혹은 다익스트라Dijkstra 알고리즘과 같은 특정 알고리즘을 미리 알고 있거나 팀 노트를 통해 준비해야 풀 수 있다. 참고로 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘으로 분류되므로, 그리디 알고리즘이면서도 암기가 팔요한 알고리즘이기도 하다. 다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다는 점을 이해하자. (10장의 크루스칼 알고리즘 또한 그리디 알고리즘에 속한다.)

 

1. 정렬 알고리즘과 같이 출제

보통 코딩테스트에서 출제되는 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위해 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 

 

2. 거스름돈 문제

거스름돈 문제는 그리디 알고리즘을 대표하는 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다. 그것은 바로 가장 큰 화폐단위부터 돈을 거슬러 주는 것이다.

코드를 보면 화폐의 종류만큼 반복을 수행해야 하므로, 화폐의 종류가 K개라고 할 때 아래 코드의 시간 복잡도는 O(K)이다. 참고로 시간 복잡도에서 거슬러 주어야 할 돈 N은 찾아볼 수 없는 것을 알 수있다. 즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거스름돈 금액의 크기와는 무관하다는 것을 알 수 있다.

물론 실제 코딩 테스트에서 출제되는 그리디 유형의 문제는 거스름돈 문제보다 난이도가 높은 편이다. 하지만 문제에 접근하는 방법은 유사하다는 것을 명심하자.

n = 1260 #거스름돈
count = 0
coin_types = [500, 100, 50, 10] #큰 단위 화폐부터 차례대로 확인
for coin in coin_types:
    count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수
    n %= coin #화폐로 나눈 나머지를 n으로 초기화 : 260 -> 60 -> 10 -> 0
print(count) #6 : 500x2, 100x2, 50x1, 10x1

 

3. 그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니며, 대부분의 문제는 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 다분하다. 하지만, 거스름돈 문제와 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

 

그리디 문제 풀이 순서

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 오랜 시간을 고민해도 해결 방법을 찾을 수 없다면, DP나 그래프 알고리즘으로 재차 고민해보는 것도 한 방법이다.

실제로 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다. 화폐의 단위가 무작위로 주어진 문제는 DP로 해결할 수 있다.

 

 

실전 문제

1. 큰 수의 법칙

[난이도: 하 / 풀이시간: 30분 / 시간제한: 1초 / 메모리제한: 128MB / 기출 2019 국가 교육기관 코딩 테스트]

큰 수의 법칙은 일반적으로 통계 분야에서 다루어지는 내용이지만, 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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+4+4인 28이 도출된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

[입력 조건]

1. 첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분.

2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.

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

[출력 조건]

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

[입력 예시]

5 8 3

2 4 5 4 6

[출력 예시]

46

 

[문제 해설]

이 문제는 전형적인 그리디 알고리즘 문제로, 문제 해결을 위한 아이디어를 떠올리는 것은 어렵지 않은 편이다. 다만, 구현 실수로 인해 오답 처리를 받는 경우가 많은 문제이므로 꼭 직접 코드를 작성해보는 것을 권장한다.

이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. 가장 큰 수를 연속해서 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다. 이를 소스코드로 표현하면 다음과 같다.

#1. 큰 수의 법칙
''' input       output
    5 8 3
    2 4 5 4 6   46     '''
'''M값이 커지면 시간 초과 발생'''
n,m,k = map(int, input().split()) #배열, 더하기 횟수, 최대 덧셈 횟수
num = sorted(list(map(int, input().split())), reverse=True)
result = 0
while True:
    for i in range(k): #가장 큰 수 k번 더하기
        if m == 0: #더하기 횟수m가 0이라면 반복문 탈출
            break
        result += num[0]
        m -= 1 #더할 때마다 1씩 배기
    if m == 0: #m이 0이라면 반복문 탈출
        break
    result += num[1] #두번째 큰 수 1번 더하기
    m -= 1 #더할 때마다 1씩 빼기
print(result) #46

 

 

이 문제는 M이 10000이하이므로 위 방식으로도 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다. 간단한 수학적 아이디어를 이용해 더 효율적으로 문제를 해결해보자.

이 문제를 풀려면 가장 먼저 반복되는 수열에 대해서 파악해야 한다. 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특성이 있다. 위의 예시에서는 수열 [6, 6, 6, 5]가 반복된다.

그렇다면 반복되는 수열의 길이는 어떻게 될까? 바로 (K+1)로 위의 예시에서는 4가 된다. 따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 다시 여기에 K를 곱해주면, 가장 큰 수가 등장하는 횟수가 된다.

이때 M이 (K+1)로 나누어떨어지지 않는 경우도 고려해야 한다. 그럴 때는 M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다. 즉, 가장 큰 수가 더해지는 횟수는 다음과 같다.

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

(파이썬에서는 A를 B로 나눈 몫을 구하기 위해 int (A / B)라고 작성하거나, A // B로 작성한다.)

결과적으로 위의 식을 이용하여 가장 큰 수가 더해지는 횟수를 구한 다음, 이를 이용해 두 번째로 큰 수가 더해지는 횟수까지 구할 수 있는 것이다. 이를 토대로 답안을 작성하면 다음과 같다.

''''수열(점화식)을 이용'''
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 + m%(k+1) # ( 8//(3+1) )*3 + 8%(3+1) = 6 + 0 = 6

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

print(result) #46

 

 

2. 숫자 카드 게임

[난이도: 하 / 풀이시간: 30분 / 시간제한: 1초 / 메모리제한: 128MB / 기출 2019 국가 교육기관 코딩 테스트]

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 NxM 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.

2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.

4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

카드들이 NxM 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

[입력 조건]

첫째 줄에 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1<=N,M<=100)

둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10000 이하의 자연수이다.

[출력 조건]

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

[입력 예시]

3 3            2 4

3 1 2         7 3 1 8

4 1 4         3 3 3 4

2 2 2

[출력 예시]

2               3

 

[문제 해설]

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다. 이 문제는 앞서 다루었던 큰 수의 법칙 문제보다 난이도가 낮다. 다만, 이 문제를 해결하기 위해서는 리스트에서 가장 작은 원소를 찾아주는 min( )함수를 사용하거나, 2중 반목문 구조를 이용할 수 있어야 한다.

#2. 숫자 카드 게임
'''min()함수를 이용'''
n, m = map(int, input().split()) #3 3
num = []
for i in range(n):
    num.append(min(list(map(int, input().split())))) #3 1 2, 4 1 4, 2 2 2
print(max(num)) #2


'''2중 반목문 이용'''
n, m = map(int, input().split()) #NxM
result = 0
for i in range(n): #N행
    data = list(map(int, input().split())) #3 1 2, 4 1 4, 2 2 2
    #현재 줄row에서 가장 작은 수 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a) #1, 1, 2
    result = max(result, min_value) #1, 1, 2
print(result) #2

 

 

3. 1이 될 때까지

[난이도: 하 / 풀이시간: 30분 / 시간제한: 1초 / 메모리제한: 128MB / 기출 2019 국가 교육기관 코딩 테스트]

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

[입력 조건]

첫째 줄에 N(2<=N<=100000)과 K(2<=K<=100000)가 공백으로 구분되면 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

[출력 조건]

첫째 줄에 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

[입력 예시]

25 5

[출력 예시]

2

 

[문제 해설]

주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다. 왜나하면 2 이상의 수로 나누는 것이 1을 빼는 것보다 숫자를 훨씬 많이 줄일 수 있기 때문이다. 따라서, N이 K의 배수가 되도록 효율적으로 한 번 빼는 방식으로 소스코드를 작성하자.

#3. 1이 될 때까지
n,k = map(int, input().split()) #17 4
result = 0

while True: #n>1:해도 맞나?
    target = (n // k) * k #k로 나눈 몫에 k를 곱한다.
    result += (n - target) #입력값n에서 target만큼 뺀 값을 결과값result에 더해주기
    n = target #target값을 n으로 초기화

    if n<k: #n이 k보다 작을 때(=더이상 나눌 수 없을 때) 반복문 탈출
        break
        
    #k로 나누기
    result += 1
    #print(result) #2 '3' <- to check
    n //= k #k로 나눈 몫을 n으로 초기화
    #print(n) #4 1 <- to check : 1이 되면서 while문 탈출

result += (n-1) #마지막으로 남은 수에 대하여 1씩 빼기
print(result) #위의 while문에서 '3'이 출력된다.

 

 

기출 문제

1. 모험가 길드

2. 곱하기 혹은 더하기

3. 문자열 뒤집기

4. 만들 수 없는 금액

5. 볼링공 고르기

6. 무지의 먹방 라이브

 

 

이 글은 주인장의 자습 목적을 위해 <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 99.99% 참고하여 만들었다.