Greedy 알고리즘
Greedy 알고리즘
- Greedy 알고리즘이란?
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
- 문제에서 "가장 큰 순서대로" 또는 "가장 작은 순서대로"와 같은 기준을 제시해준다.
- 예제 1 ) 거스름돈 문제
1) 문제
N원을 거슬러 줘야할 때, 가장 큰 화폐 단위부터 돈을 거슬러 주어야 한다.
2) 풀이
n = 1260
count = 0
coin_types = [500, 100, 50, 10]
for c in coin_types:
# 해당 동전으로 거슬러 줄 수 있는 개수 세기
count += n // c
n %= c
print(count)- 주의점
(1) 문제를 처음 접했을 때 다양한 아이디어를 고려해야 한다.
(2) 동전의 단위가 서로 배수 형태가 아니었다면 탐욕법을 사용하지 못했을 것 (만약 무작위로 주어졌다면 다이나믹 프로그래밍으로 해결할 수 있음)
실전예제 1. 큰 수의 법칙
- 특징
-> 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
-> 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없음
1) 문제
첫째 줄에 N, M, K의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
둘째 줄에 N개의 자연수가 주어진다. 공백으로 구분한다.
입력으로 주어지는 K는 항상 M보다 작거나 같다.
첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력한다.
2) 풀이 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):
if m == 0:
break
result += first
m -= 1
if m == 0 :
break
result += second
m -= 1
print(result)3) 주의점
이 문제를 풀기 위해서는 반복되는 수열을 파악해야 한다. m의 크기가 커졌을 경우 시간 초과를 막기 위해 좀 더 효율적으로 해결법을 생각해야 한다.
4) 풀이 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)실전예제 2. 숫자 카드 게임
1) 특징
-> 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 최종적으로 뽑는 게임
-> 각 행마다 카드 한장씩 뽑아서 그 중에서 가장 큰 수를 찾아라
-> N x M 형태로 카드가 놓여있다.
-> 행을 먼저 선택하고 가장 낮은 카드를 뽑을 것을 고려하기
즉, 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것
2) 풀이
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. 1이 될 때 까지
1) 문제
어떠한 수 N이 1이 될 때 까지 2개의 과정 중 하나를 반복적으로 수행하려고 한다. 단 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
N, K가 주어질 때 N이 1이 될때까지 과정을 수행해야하는 최소 횟수를 구하라.
2) 풀이 1
n, k = map(int, input().split())
result = 0
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)3) 풀이 2
n, k = map(int, input().split())
result = 0
while True:
target = (n // k) * k
result += (n - target)
n = target
if n < k:
break
result += 1
n //= k
# 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)
Learning by Doing