그리디 with 파이썬
1. 개요
그리디 알고리즘이란 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미한다. 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 다른 알고리즘의 유형과 비교했을때 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제의 유형이다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
2. 거스름돈
문제
카운터에는 거스름 돈으로 사용할 500, 100, 50, 10원 짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야할 돈이 N원일 때 거슬러줘야할 동전의 최소 갯수를 구해라. 단, 거슬러 줘야 할 돈은 항상 10의 배수이다.
답안
n = int(input("금액 : "))
count=0
list=[500,100,50,10]
for coin in list:
count += n//coin
n %=coin
print(count)
이 문제는 가장 큰 화폐 단위부터 돈을 거슬러 주는 것만 생각하면 쉽게 해결할 수 있다. 코드를 보면 화폐의 종류만큼 반복을 수행해야 하기 때문에 화폐의 종류가 K개 있다면 복잡도는 O(K)가 된다.
3. 그리디 알고리즘의 정당성
그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분 문제는 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 다분하다. 위에서 제시한 예시처럼 거스름 돈 문제에서 가장 큰 화폐 단위부터 돈을 거슬러 주는 것과 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이다.
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있었던 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수 이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 예를 들어 800원을 거슬러 줘야 하는데 단위가 500, 400, 100일 경우 그리디 알고리즘으로 해결할 경우 500+100+100+100을 거슬러 줘야 한다고 나오는데 최적의 해는 400+400을 거슬러 주는 것이다. 따라서, 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로, 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만 수행하면 된다. 대부분 그리디 알고리즘 문제에서는 이와 같이 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
거스름돈 문제에서 화폐의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다. 이 경우에는 다이나믹 프로그래밍으로 해결해야 한다.
어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 다음에는 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 고민해보는 것도 방법이다.
4. 큰 수의 법칙
문제
n개의 자연수가 주어지고, 주어진 수들을 m번 더해서 가장 큰 수를 만드는 알고리즘을 구현하라. 단, 특정한 인덱스(번호)에 해당하는 수가 연속으로 K번을 초과해서 더해질 수 없고 값이 같아도 인덱스가 다르면 다른것 취급한다.
Hint) 반복되는 과정은 최대한 줄이도록 한다.
입력 예시
5 8 3 # n m k 순
2 4 5 4 6
출력
46
첫 번째 시도
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
lastdata = a[n-1]
beforedata = a[n-2]
count=0
sum =0
for i in range(m-m//(k+1)):
sum +=lastdata
count+=1
if count==k:
count=0
sum+=beforedata
print(sum)
m이 10,000 이하이므로 이 방식으로도 해결이 가능하지만 M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받는 코딩이다.
두 번째 시도(더욱 간결하게)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
lastdata = a[n - 1]
beforedata = a[n - 2]
count = 0
sum = 0
반복횟수 = m // (k + 1) # 6+6+6+5 의 반복 횟수
나머지 = m % (k + 1)
sum += 반복횟수 * (lastdata * k + beforedata)
sum += 나머지 * lastdata
print(sum)
가장 먼저 파악해야 하는 것은 반복되는 수열이다. 입력 예시대로 할 경우 6+6+6+5+6+6+6+5 가 수행된다. 이를 살펴보면 6+6+6+5가 반복된다는 것을 알 수 있다. 따라서 이 연산을 한 번에 묶어서 처리하면 알고리즘의 효율을 높일 수 있다.
5. 숫자 카드 게임
문제
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 룰은 다음과 같다.
- 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. N은 행의 개수이고 M은 열의 개수이다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야한다.
- 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮을 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자를 뽑을 수 있도록 전략을 세워야한다.
입력 예시
3 3
3 1 2
4 1 4
2 2 2
출력
2
첫 번째 시도
n,m = map(int,input().split())
a = [[0] for i in range(n)]
for i in range(n):
a[i]= list(map(int,input().split()))
ans = min(a[0])
for i in range(1,n):
if ans<min(a[i]):
ans = min(a[i])
print(ans)
배열을 미리 생성하고 그 배열 안에 입력받은 배열을 다 넣고 판단했다. 이러면 시간도 메모리도 낭비다.
개선한 풀이
n,m = map(int,input().split())
result =0
for _ in range(n):
a = list(map(int,input().split()))
ans = min(a) # 가장 작은 수 찾기
result = max(ans,result) # 작은 수 중에서 큰 수 찾기
print(result)
처음 했던 풀이에서 배열을 입력받자마자 작은 수를 판단하는 형식으로 알고리즘을 개선했다.
문제를 푸는 아이디어는 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다.
6. 1이 될 때까지
문제
어떤 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택한다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 예시
25 5
출력
2
풀이
count = 0
n, k = map(int, input().split())
while n > 1:
if n % k == 0:
n //= k
count += 1
else:
count += n%k
n-= n%k
print(count)
n의 범위가 100억 이상의 되는 수를 가정했을 때에도 빠르게 동작하기 위해서 뺄셈을 한 번에 처리하도록 알고리즘을 설계했다.
파이썬은 다른 언어보다 작동이 느리기때문에 최적화가 가장 중요하다는 것을 기억하자.
