나동빈 님의 이것이 코딩테스트다 with 파이썬 를 보며 코딩테스트에 필요한 다양한 알고리즘 기법들을 복습하고 정리한 내용입니다.
그리디(Greedy) 알고리즘 이란?
그리디 알고리즘은 말 그래도 ‘탐욕(Greedy)’적으로 단순 무식하게 문제를 푸는 방식이다. 더 쉽게 설명하자면 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 뜻한다.
그리디 알고리즘은 매 순간에서 그 순간의 상황에서’만’ 가장 좋은 방식을 선택하며, 미래에 미치는 영향은 전혀 생각하지 않는다.
코딩테스트에서 그리디 알고리즘은 다른 알고리즘과 다르게 미리 외우고 암기하지 않고도, 풀 수 있을 가능성이 높은 문제 유형이다. 하지만 그 중 ‘다익스트라(Dijktra)’ 알고리즘은 그리디 알고리즘이지만 학습과 암기가 필요한 부분이다.
그리고 그리디 알고리즘은 보통 문제에서 ‘가장 큰 순서대로’, ‘가장 긴 순서대로' 등과 같은 기준을 제시해주기 때문에, 정렬 알고리즘과 짝을 이뤄 출제된다. (정렬 알고리즘도 다시 한번 공부해보자)
어쨋든 코딩 테스트에서 그리디 알고리즘은 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 창의력을 요구하는 문제들로 출제된다!
예제 1. 거스름돈
책에서의 예시는 거스름돈이라는 문제인데, 예전에 비슷한 풀었던 동전 0_11047, 거스름돈_5585 문제와 거의 비슷했다.
그래서 거스름돈_5585 문제로 예를 든다.
내가 푼 코드
import sys
coins = [500, 100, 50, 10, 5, 1]
N = 1000 - int(sys.stdin.readline())
idx = 0
cnt = 0
while N > 0 :
if N // coins[idx] > 0 :
cnt += 1
N -= coins[idx]
else :
idx += 1
print(cnt)책의 내용을 읽고 푼 코드
import sys
N = 1000 - int(sys.stdin.readline())
coins = [500, 100, 50, 10, 5, 1]
cnt = 0
for coin in coins :
cnt += N // coin
N %= coin
print(cnt)문제를 보고 거의 5분안에 코드를 다 치고 맞아가지고, 너무 쉽다 생각했다. 하지만 그 뒷장을 보고 내 잘못을 알게 되었다. 완전 주먹구구식으로 풀어서 시간복잡도가 엄청 비효율적이었다.
나는 입력받은 돈에 가장 큰 동전 순(500 → 100 → … → 1)으로 하나하나 씩 나눠주고 빼주면서 계산했다. 이렇게 되면 1원 단위가 엄청 많아지게 되어, 거스름돈이 정말 많아지는 경우에 계산 과정이 길어질 수 있다.
책에서는 문제의 과정을 하나씩 분석하고, 이를 간단한 식으로 정의하여 훨씬 시간 복잡도가 줄었다.
알고리즘의 정당성?
만약 문제에서 동전의 단위는 500원, 400원, 100원 이었고 800원을 거슬러 주어야 한다고 가정해보자. 문제에서는 500, 100, 100, 100으로 총 4번을 거슬러줘야 한다고 출력하겠지만, 사실 400, 400 총 2번으로 충분히 거슬러 줄 수 있다.
이 문제가 그리디로 풀이가 가능 한 이유는, 가지고 있는 동전의 타입 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
그래서 그리디 알고리즘은 문제를 풀기 위한 아이디어를 떠올리고 이것이 언제나 최적의 해를 도출하는지 꼭 잘 검토하고 파악해야 한다!
예제 2. 큰 수 만들기
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True) # 정렬
tmp = 0
answer = 0
idx = 0
cnt = 1
for _ in range(M) :
answer += A[idx] # 가장 큰 값 더해줌
if tmp == A[0] : # 이전에 더한 값이 현재 더해준 값과 같으면, cnt 1 추가
cnt += 1
else : # 다르면 다시 초기화
cnt = 1
idx = 0
if cnt == K :
idx += 1
tmp = A[idx]
print(answer)예제 3. 숫자 카드 게임
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
tmp = []
for i in range(N) :
cardsRow = list(map(int, input().split()))
tmp.append(min(cardsRow))
print(max(tmp))예제 4. 1이 될 때 까지
import sys
N, K = map(int, sys.stdin.readline().split())
cnt = 0
while N > 1 :
if N % K == 0 :
N //= K
else :
N -= 1
cnt += 1
print(cnt)