그리디
📎 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
그리디(greedy) 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- ‘탐욕법’이라고도 함 ex. 다익스트라 알고리즘
- 매 순간 가장 좋아보이는 것을 선택, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않음
- 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
- ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 제시됨
→ 정렬 알고리즘과 자주 짝을 이루어 출제됨
예제 1. 거스름돈
Q. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하여라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
A. ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것
→ 500원으로 거슬러 줄 수 있는 만큼 거슬러 주고, 100원, 50원, 10원 순서로 거슬러 주기
정당성 - 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없음
n = 1260
cnt = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
cnt += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기(정수 나누기)
n %= coin # 남은 잔액 업데이트
print(cnt)| n // coin | n % coin | |
|---|---|---|
| 반복 1(500) | 1260 // 500 = 2 | 1260 % 500 = 260 |
| 반복 2(100) | 260 // 100 = 2 | 260 % 100 = 60 |
| 반복 3(50) | 60 // 50 = 1 | 60 % 50 = 10 |
| 반복 4(10) | 10 // 10 = 1 | 10 % 10 = 0 |
예제 2. 큰 수의 법칙
Q. 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙, 배열의 특정 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에는 서로 다른 것으로 간주함.
- 입력 조건
- 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
A. 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하여 ‘가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산’을 반복함
sol 1) 단순하게 풀기
n, m, k = map(int, input().split()) # N, M, K를 공백으로 구분하여 입력받기
data = list(map(int, input().split())) # N개의 수를 공백으로 구분하여 입력받기
data.sort() # 가장 큰 값을 구하기 위해 정렬
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수
result = 0
while True:
for i in range(k): # 가장 큰 수를 K번 더하기
if m == 0: # 최대 M번 더할 수 있으니까
break
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)sol 2) 반복되는 수열 이용
n, m, k = map(int, input().split()) # N, M, K를 공백으로 구분하여 입력받기
data = list(map(int, input().split())) # N개의 수를 공백으로 구분하여 입력받기
data.sort() # 가장 큰 값을 구하기 위해 정렬
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수
result = 0
# 가장 큰 수가 더해지는 횟수 계산
cnt = int(m / (k + 1)) * k
cnt += m % (k + 1)
result += cnt * first # 가장 큰 수 더하기
result += (m - cnt) * second # 두 번째로 큰 수 더하기
print(result)-
가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있음
-
ex) M = 8, K = 3, first = 6, second = 5 일 때,
6 6 6 56 6 6 5→ 반복되는 수열의 길이는 (K + 1), 수열이 반복되는 횟수 M // (K + 1)큰 수가 더해지는 횟수 =
int(M / (K + 1)) * K + M % (K + 1)
예제 3. 숫자 카드 게임
Q. 숫자 카드 게임의 규칙은 다음과 같다.
1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.- 입력 조건
- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100)
- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
A. 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾기
→ min() 함수를 이용해서 각 행에서 가장 작은 수를 찾은 다음 그 수들 중에서 가장 큰 수를 찾으면 됨
sol 1) min() 함수 이용
n, m = map(int, input().split()) # n, m을 공백으로 구분하여 입력받기
result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
data = list(map(int, input().split()))
min_value = min(data) # 현재 행에서 '가장 작은 수' 찾기
result = max(result, min_value) # '가장 작은 수'들 중에서 가장 큰 수 찾기
print(result)sol 2) 2중 for문 이용
n, m = map(int, input().split()) # n, m을 공백으로 구분하여 입력받기
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이 될 때까지
Q. 어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복해서 수행한다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다. (N이 K로 나누어 떨어질 때)
N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구해야 한다.- 입력 조건
- 첫째 줄에 N(2 ≤ N ≤ 100,000)과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
A. 주어진 N에 대하여 ‘최대한 많이 나누기’를 수행
→ K가 2 이상의 자연수이므로, 가능하면 나누는 것이 항상 더 숫자를 빠르게 줄이는 방법이 됨
sol 1) 단순하게 풀기
n, k = map(int, input().split()) # N, K를 공백으로 구분하여 입력받기
result = 0
# N이 K 이상이라면 K로 계속 나누기
while n >= k:
# N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
while n % k != 0:
n -= 1
result += 1
n //= k # K로 나누기
result += 1
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
n -= 1
result += 1
print(result)sol 2) 좀 더 효율적으로 풀기
n, k = map(int, input().split()) # N, K를 공백으로 구분하여 입력받기
result = 0
while True:
# N이 K로 나누어떨어지는 수가 될 때까지 1씩 빼기
target = (n // k) * k
result += (n - target)
n = target
if n < k: # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
break
result += 1
n //= k # K로 나누기
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)