Chapter 03. 그리디
1. 당장 좋은 것만 선택하는 그리디
- 그리디(탐욕): 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
- 현재의 선택이 나중에 미칠 영향 고려 X
💡그리디 알고리즘 문제 특징
o 문제 출제의 폭이 매우 넓어 암기만으로 모든 문제 대처는 불가!
⭐어떤 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야함!
⭐힌트) 가장 큰 순서대로, 가장 작은 순서대로… -> 자주 정렬 문제와 짝을 이뤄 출제된다.
⭐대표 문제) 거스름돈
예제 3-1. 거스름돈
[문제]
당신은 음식점의 계산을 도와주는 점원이다. 카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라.
🔖문제 해설
- 가장 큰 화폐 단위부터 거슬러 주기 -> 그리디
1
2
3
4
5
6
7
8
9
10
n = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 몫
n %= coin # 나머지
print(count)
- 시간 복잡도: O(K) -> 동전의 종류에만 영향을 받고 거슬러 줘야하는 금액의 크기와는 무관!
❓왜 그리디로 해결이 가능할까?
o 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문.
그리디 알고리즘의 정당성
- 대부분의 문제는 그리디로 최적의 문제 찾을 수 X
- 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을때!!
⭐대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
⭐코딩 문제 만나면 먼저 그리디 의심!
2. 실전 문제(큰 수의 법칙)
✔️문제
다양한 수로 이루어진 배열, 주어진 수를 M번 더하여 가장 큰 수 만들기.
(단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음)
✔️입력 조건
첫째 줄에 N(2 <= N <= 1000), M(1 <= M <= 10000), K(1 <= K <= 10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10000이하의 수로 주어진다 입력으로 주어지는 K<=M
✔️출력조건
첫째 줄에 큰 수의 법칙에 따라 더해진 답 출력
✔️입력 예시
5 8 3
2 4 5 4 6
✔️출력 예시
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 내 풀이
# 첫번째 줄
N, M, K = map(int, input().split())
if ((2 <= N <= 1000) and (1 <= M <= 10000) and (1 <= K <= 10000) and (K <= M)):
numbers = list(map(int, input().split()))
# 첫번째로 큰 수 찾기
first = max(numbers)
# 두번째로 큰 수 찾기
numbers.pop(numbers.index(first))
second = max(numbers)
# 더하기
count = 0
result = 0
first_add_count = 0
while (count < M):
if (first_add_count < K):
result += first
count += 1
first_add_count += 1
else:
first_add_count = 0
result += second
count += 1
print(result)
❗ 0부터 하면… 만약 5번 하고싶으면 k < 5 O / K <= 5 X -
💡문제 해결 위한 아이디어
o 큰 수와 두번째로 큰 수만 지정
o 큰 수 K번 더하고, 그 다음 큰 수 한번 더하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 책 풀이(1)
n, m, k = map(int, input().split())
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 # while문 끝!
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)
하지만, M의 크기가 100억 이상으로 커지면 시간 초과!!
💡아이디어
o M(총 반복 횟수)을 K + 1(반복되는 수열의 길이)로 나눈 몫이 수열이 반복되는 횟수
o 나머지만큼 큰 수를 더해주면 됨!!
=> int(M / (K+1)) * K + M % (K+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 책 풀이(2)
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
count += m % (k+1)
result = 0
result += (count) * first
result += (m-count) * second
print(result)
💬보완할점
- 정렬 함수 이용할 생각 안한것
3. 실전문제(숫자 카드 게임)
✔️문제
여러개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장 뽑기. 게임 룰은 다음과 같다.
1) 숫자가 쓰인 카드들이 N*M형태로 놓여 있으며 N은 행, M은 열
2) 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택
3) 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑기
4) 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략 세움
✔️입력조건
첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다(1 <= N,M <= 100) 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10000이하의 자연수이다.
✔️출력조건
첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.
✔️입력 예시
3 3
3 1 2
4 1 4
2 2 2
✔️출력 예시
2
- 참고: 2차원 행렬 만들기 참고
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 내 풀이
# 리스트 만들기
N, M = map(int, input().split())
if (1 <= N and M <= 100):
array = [[0] * M for _ in range(N)]
# 행렬 숫자 채우기
for i in range(N):
numbers = list(map(int, input().split()))
array[i] = numbers
# 정답 찾기
result = min(array[0])
for i in range(1, N):
if (min(array[i]) > result):
result = min(array[i])
print(result)
💡아이디어
o 리스트에서 가장 작은 원소 찾기
o 비교해서 큰 수 찾기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 책 풀이(min() 함수 이용용)
# min()함수 이용한 답안 예시
n,m = map(int,input().split())
result = 0
# 1차원 리스트 받아서 각 줄에서 최소값 비교 후 그 중 가장 큰 값 출력
for i in range(n):
data = list(map(int, input().split()))
# 현재 줄에서 가장 작은 수 찾기
min_value = min(data)
# '가장 작은 수'들 중에서 가장 큰 수 찾기
result = max(result, min_value)
print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
# 책 풀이(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)
💬보완할점
- 굳이 2차원 행렬을 실제로 만들 필욘 없네ㅎㅎ
4. 실전 문제(1이 될 때까지)
✔️문제
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1) N에서 1을 뺀다.
2) N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
✔️입력 조건
첫째 줄에 N(2<= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
✔️출력 조건
첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
✔️입력 예시
25 5
✔️출력 예시
2
1
2
3
4
5
6
7
8
9
10
11
12
N, K = map(int, input().split())
if ((2 <= N <= 100000) and (2 <= K <= 100000) and (N >= K)):
count = 0
while N != 1:
if (N % K != 0):
N -= 1
count += 1
else:
N = N // K
count += 1
print(count)
💡아이디어
o 최대한 많이 나누기!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 책 풀이
# 단순하게 푸는 답안 예시_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)
데이터가 너무 많다면?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 답안 예시_2
n,k = map(int, input().split())
result = 0
while True:
#(N == K로 나누어떨어지는 수)가 될 때까지 1씩 빼기
target = (n // k) * k
result += (n - target) # 1을 뺀 횟수
n = target
# N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n -1)
print(result)
💬보완할점
- 데이터가 너무 많아질때 어떻게 하면 좋을지 고민하기!