코테 독학(feat.이것이 코딩테스트다 with 파이썬) - 그리디 [개념편]

그리디 알고리즘

말 그대로 탐욕적으로 문제를 푸는 알고리즘.

'현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

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

 

예제 1 - 거스름돈

n = 1260 #거슬러줘야 할 돈
coin_set = [500, 100, 50, 10]
count = 0

for coin in coin_set:
	count += (n // coin)
    n %= coin
    
print(count) # 최소 동전 갯수

 하지만 이 코드는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기에 가능하다.

 

예로 거슬러 줄 돈이 800원이고 화폐 단위가 500원, 400원, 100원이면 그리디 알고리즘으로는 500원, 100원, 100원, 100원이지만, 실제 최적의 해는 2개의 동전(400원 400원)이다. 다시말해 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로, '가장 큰 단위의 화폐부터 차례대로 확인하여거슬러 주는 작업만을 수행하면 된다.'는 아이디어는 정당하다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할수 있다.    

 

처음에 문제를 만났을 때는 이것저것 다양한 아이디어 고려하기!!

 

예제 2 - 큰 수의 법칙

 

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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

 

 

풀이 코드 1:

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

data.sort() # 오름차순 정렬
first = data[n-1]
second = data[n-2]

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+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다. 이 때 M이 (K+1)로 나누어떨어지지 않는 경우도 고려해야 한다. 그럴 때는 M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다. 

 

풀이 코드 2 :

# 똑같이 n, 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 + m % (k+1)

result = 0
result = count * first + (m-count) * second

print(result)

 

예제 3 - 숫자 카드 게임

 

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

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

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

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

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

 

입력 조건: 

• 첫째 줄에 숫자카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1<=N,M<=100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상10,000 이하의 자연수이다.

출력 조건:

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

입력 예시1:

3 3
3 1 2
4 1 4
2 2 2 # 출력 예시 1: 2

 

입력 예시2:

2 4
7 3 1 8
3 3 3 4 # 출력 예시 2: 3

 

 

풀이코드 1

min()함수 이용 :

# 행과 열 크기 받기
n, m = map(int, input().split())

result = 0

# 카드들의 숫자 받기
for i in range(n):
	data = list(map(int, input().split()))
    min_value = min(data)
    # 작은 수들 중에서 가장 큰 값 찾기
    result = max(result, min_value) # 반복 때마다 가장 큰 값 업뎃 시도

print(result)

 

풀이코드 2

2중 반복문 구조 이용 :

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0

# 한 줄씩 입력받아 확인
for i in range(n):
	data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
    	min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)
    
print(result) # 출력

 

 

예제 4 - 1이 될 때까지

 

어떠한 수 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<=100,000)과 K(2<=K<=100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력 조건:

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

입력예시 : 

25 5 # 출력 예시: 2

 

풀이 코드:

n, k = map(int, input().split())

result = 0

while n > 1:
    if n % k == 0:
        n //= k
        result += 1
    else:
        n -= 1
        result += 1

print(result)

 

이 문제도 문제 해결을 위한 아이디어를 떠올릴 수 있으면 어렵지 않게 해결할 수 있다. 주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 왜냐하면 어떠한 수가 있을 때, '2 이상의 수로 나누는 것'이 '1을 빼는 것'보다 숫자를 훨씬 많이 줄일 수 있기 때문이다. 문제에서는 K가 2 이상의 자연수이므로, 가능하면 나누는 것이 항상 더 숫자를 빠르게 줄이는 방법이 된다.

 

문제에서는 N의 범위가 10만 이하이므로, 이처럼 일일이 1씩빼도 문제를 해결할 수 있다. 하지만 N이 100억 이상의 큰 수가 되는 경우를 가정했을 때에도 빠르게 동작하려면, n이 k의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스코드를 작성할 수 있다.

 

풀이 코드 2 (문제의 N 범위가 커졌을 때):

n, k = map(int, input().split())
result = 0

while True:
    # (N == K로 나누어떨어지는 수)가 될 때까지 K로 나누기
    target = (n // k) * k # N이 K로 나누어떨어지는 수
    result += (n - target) # N에서 target을 빼기 (1씩 빼는 연산의 수)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # 나누어 떨어지는 수로 만든 후 K로 나누기
    result += 1
    n //= k
    
    # 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)

print(result)