Chapter 03 Greedy

그리디; 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 ~ 탐욕법

Example 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

해설

• 최소 동전 개수 \(\to\) ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것

이 예제가 그리디 알고리즘이 가능한 이유

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

• 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

Answer

n = 1260
count = 0

# 큰 단위 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)

6

step

count = 0;count

0

n = 1260;n

1260

count = count + n//500;count

2

n %= 500;n

260

count = count + n//100;count

4

n %= 100 ; n

60

count = count + n//50;count

5

n %= 50 ; n

10

count = count + n//10;count

6

n %= 10;n

0

큰 수의 법칙

’큰 수의 법칙’은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

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

입력 조건

• 첫쨰 줄에 \(N(2\le N \le 1,000), M(1 \le M \le 10,000), K(1 \le K \le 10,000)\)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

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

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

출력 조건

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

해설

• ’가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산’을 반복

• 반복되는 수열에 대해서 파악하기

가장 큰 수가 더해지는 횟수 \[int(M / (K + 1)) * K + M \% (K + 1)\]

Answer 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] # 두 번째로 큰 수

result = 0

while True:
    for i in range(k): # 가장 큰 수를  K번 더하기
        if m == 0: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때마다 1씩 빼기
    if m == 0: # m이 0이라면 반복문 탈출
        break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 떄마다 1씩 빼기
    
print(result)

 5 8 3 
 2 4 5 4 6

46

step

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

 5 8 3

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

 2 4 5 4 6

data.sort();data

[2, 4, 4, 5, 6]

range(k)

range(0, 3)

first = data[n-1];first

6

second = data[n-2];second

5

result = 0; result

0

result = result + first*3; result

18

m = m - 3 ;m

5

result = result + second; result

23

m = m - 1 ;m

4

result = result + first*3; result

41

m = m - 3 ;m

1

result = result + second; result

46

m = m - 1 ;m

0

int(8 / (6 + 1)) * 3 + 8 % (6 + 1)

4

Answer 2

# 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] # 두 번째로 큰 수

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

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

print(result)

 5 8 3
 2 4 5 4 6

46

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

 5 8 3

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

 2 4 5 4 6

data.sort();data

[2, 4, 4, 5, 6]

first = data[n-1];first

6

second = data[n-2];second

5

count = int(m / (k + 1)) * k ; count

6

m % (k+1)

1

result = 0;result

0

result += count * first;result

36

result += (m - count) * second; result

46

숫자 카드 게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 \(N \times M\) 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그다음 선택된 행에 초함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 정략을 세워야 한다.

입력 조건

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

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

출력 조건

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

문제 해설

• ’각 행마다 가장 작을 수를 찾은 뒤에 그 수 중에서 가장 큰 수’를 찾는 것

Answer 1

• min() 함수를 이용하는 답안 예시

# N, M을 공백으로 구분하여 입력받기
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)

 3 3
 3 1 2
 4 1 4
 2 2 2

2

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

 3 3

result = 0; result

0

range(3)

range(0, 3)

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

 3 1 2

min_value = min(data);min_value

1

result = max(result, min_value);result

1

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

 4 1 4

min_value = min(data);min_value

1

result = max(result, min_value);result

1

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

 2 2 2

min_value = min(data);min_value

2

result = max(result, min_value);result

2

Answer 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)

 2 4
 7 3 1 8
 3 3 3 4

3

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

 2 4

result = 0

range(2)

range(0, 2)

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

 7 3 1 8

min_value = 10001;min_value

10001

min_value = min(min_value,7,3,1,8);min_value

1

result = max(result, min_value);result

1

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

 3 3 3 4

min_value = 10001;min_value

10001

min_value = min(min_value,3,3,3,4);min_value

3

result = max(result, min_value);result

3

1이 될 때까지

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

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

입력 조건

• 첫째 줄에 \(N(2 \le N \le 100,000)\)과 \(K(2 \le K \le 100,000)\)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력 조건

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

문제 해설

• ‘최대한 많이 나누기’

Answer 1

• 단순하기 푸는 답안 예시

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

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K 로 나누기
    n //= k
    result += 1
    
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

 25 5

2

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

 25 5

result = 0; result

0

n%k

0

n //= k;n

5

result += 1 ;result

1

n%k

0

n // k ; n

5

result += 1 ; result

2

Answer 2

• 답안 예시

# N, K를 공백으로 구분하여 입력받기
n, k = map(int, input().split())
result = 0

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

 25 5

2

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

 25 5

result = 0

target = (n // k) * k; target

25

n = target ; n

25

result += 1;result

1

n //= k ;n

5

target = (n // k) * k; target

5

n = target ; n

5

result += 1;result

2

n //= k ;n

1