[이코테] 3장 그리디

 

Greedy(탐욕법)

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

 

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 기준에 따라 좋은 것을 선택하는 알고리즘
• 가장 큰 순서대로, 가장 작은 순서대로 같은 기준을 제시해줌   → 정렬과 짝을 이뤄 같이 출제
• 최소한의 아이디어를 떠올리고, 이 아이디어가 정당한 지 검토할 수 있어야 한다.

 

---

[예제1] 거스름돈

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

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

 

아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 준다.

1) 남은 돈 : 1260원

 

2) 500원으로 거슬러 줄 수 있는 돈 500x2 = 1000원

남은 돈 : 1260 - 1000 = 260원

 

3) 100원으로 거슬러 줄 수 있는 돈 100x2 = 200원

남은 돈 : 260 - 200 = 60원

 

4) 50원으로 거슬러 줄 수 있는 돈 50x1 = 50원

남은 돈 : 60 - 50 = 10원

 

5) 10원으로 거슬러 줄 수 있는 돈 10x1 = 10원

남은 돈 : 10 - 10 = 0원

 

풀이

n = 1260
count = 0

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

for coin in coin_types:
	count += n // coin   # 해당 화폐로 거슬러 주 줄 수 있는 동전의 개수 세기
    n %= coin			# 거슬러 준 돈을 제외한 나머지 돈
    
print(count)

시간 복잡도 : O(K)    ∴ K는 화폐의 종류 

그리디를 사용하는 이유 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

• 문제를 처음 접했을 때 다양한 아이디어를 고려해야 한다.
• 동전의 단위가 서로 배수 형태가 아니었다면 탐욕법을 사용하지 못했을 것
  (만약 무작위로 주어졌다면 다이나믹 프로그래밍으로 해결)

 

---

 

[실전 문제1] 큰 수의 법칙

다양한 수로 이뤄진 배열이 있을 때, 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙

• 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과할 수 없다.
• 서로 다른 인덱스에 있다면, 같은 수여도 서로 다른 것으로 간주한다.

EX1) [2, 4, 5, 4, 6],  M = 8, K = 3 일 때

정답 : 6 + 6+ 6 + 5 + 6 + 6 + 6 + 5 = 46

 

EX2) [3, 4, 3, 4, 3], M = 7, K = 2 일 때

정답 : 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28

 

 

입력 조건

첫째 줄에 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

 

 

<풀이>

가장 큰 수와 두 번째로 큰 수만 저장하면 된다.

=> 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한번만 더하는 연산

 

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

# N개의 수를 공백으로 구분해 입력받기
data = list(map(int, input().split()))

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

resut = 0

while True:
	for i in range(k): 	# 가장 큰 수를 k번 더하기
    	if m == 0:
        	break
        result += first
        m -= 1
   
	if m == 0:  
   		break
	result += second  # 두 번째로 큰 수를 한 번 더하기
    m -= 1

 

이 풀이는 M이 10,000이하이므로 위 방식으로 문제 풀이가 가능하지만, M이 100억 이상으로 커진다면 시간 초과가 일어날 것이다. 간단한 수학적 아이디어를 이용해 효율적인 문제 해결 가능하다.

 

아이디어 : 반복되는 수열에 대해 파악

[2, 4, 5, 4, 6], M = 8, K = 3 일 때,

가장 큰 수 = 6

두 번째로 큰 수 = 5

이때 합이 최대일 경우는 (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46 이된다.

 

(K + 1)의 길이를 가지는 (6, 6, 6, 5) 수열이 반복되고 있다.

반복되는 수열의 길이는 2이므로, M을 (K+1)로 나눈 몫( = M / (K+1)) 이 된다.

이때, M이 (K + 1)로 나눠떨어지지 않는 경우도 고려해야한다. M을 (K + 1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해진다.

ex) M = 8, K = 4일때, count = 1 * 4 + 8 % 5  = 7

(6, 6, 6, 6, 5) + (6, 6, 6) = 47

 

즉, 가장 큰 수가 더해지는 횟수는 int(M / (K + 1)) * K + M % (K + 1)

 

n, m, k = map(int, input().split())
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)

 

 

---

[실전 문제2] 숫자 카드 게임

여러 개의 숫자 카드 중에서 게임 규칙을 지키며 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임

 

<게임 규칙>

1. 숫자가 쓰인 카드들이 N x M(행x열) 형태로 놓여있다. 

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

 

 

<풀이>

아이디어 : 각 행마다 가장 작은 수를 찾은 뒤, 그 중 가장 큰 수를 찾는 것

min() 함수를 이용할 수 있거나, 2중 반복문 구조를 이용할 수 있어야 한다.

 

 

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)

 

리스트에 넣고 min이나 max를 하는 방식으로 구현했었는데, min(arg1, arg2, ...) 를 사용하는게 간결하게 표현 가능한 것 같다.

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

ans = []

for _ in range(n):
    ans.append(list(map(int, input().split())))

# min(iteration) 함수
min_list = []
for i in range(n):
    min_list.append(min(ans[i]))
    
# min(arg1, arg2, ...) 함수
result = 0
for i in range(n):
    result = max(result, min(ans[i]))

print(max(min_list))

 

2. 2중 반복문 구조를 이용한 답안

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)

 

 

---

 

[실전 문제3] 1이 될 때까지

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

 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

입력 조건 

첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되어, 각각 자연수로 주어진다.

이때, N은 항상 K보다 크거나 같다.

출력 조건

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

 

입력 예시

25 5

출력 예시

2

 

 

<풀이>

아이디어 : N에 대해 '최대한 많이 나누기'를 수행

1을 빼는 것보다 숫자를 훨씬 많이 줄일 수 있기 때문에, 가능하면 K로 나누는 것을 수행해야 한다.

 

1) N이 K의 배수가 될 때까지 1을 빼기

2) N을 K로 나누기

 

 

1. 단순하게 푸는 답안

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

print(n, k)
count = 0
while n >= k:
	
    # N이 K로 나누어 떨어지지 않는다면, N에서 1씩 빼기
    while n % k != 0: 
        n -= 1
        count += 1
	
    # K로 나누기
    n //= k
    count += 1

# 마지막으로 남은 수에 대해 1씩 빼기
while n > 1:
    n -= 1
    count += 1

print(count)

 

 

2. N이 매우 큰 수가 된 경우를 가정했을 때는 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)