그리디 알고리즘이란? (a.k.a 탐욕법)
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
- 다른 유형들에 비해 비교적 외우고 있지 않아도 풀 수 있는 문제이지만, 그래도 출제의 폭이 넓은 편에 속함
- 기준에 따라 좋은 것을 선택하는 알고리즘으로 ‘가장 큰’ 혹은 ‘가장 작은’ 이라는 키워드를 함께 제시하면서 정렬 알고리즘과 짝을 이뤄 출제됨
- 대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’를 찾을 수 없을 가능성이 다분함
→ 따라서 문제 풀이를 위한 아이디어를 떠올리면, 이것이 정당한지 검토할 수 있어야 함
→ 정당하지 않다면, 추후에 배울 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민 필요
그림으로 이해하기
만약 s노드부터 시작하여, 전체 트리에서 가장 큰 수를 찾아야 하는 문제를 풀어야 한다고 생각해보자
완전 탐색이란, 가능한 방안을 모두 고려했을 때 가장 최적의 방법 및 결과를 찾는 것이다.
따라서, 위 그림에서는 트리의 전체 노드를 탐색하고 가장 큰 수인 9가 있는 노드를 찾을 것이다.
이는 가장 최적의 해를 찾는다는 장점이 있지만, 모든 가능한 수를 탐색해야 하기 때문에 어렵고 오래걸린다는 단점이 있다.
반면 위의 사진과 같은 그리디 알고리즘에서는 지금 당장 큰 수를 고려한다.
즉 첫 번째 계층이자 갈림길인 (2,7) 중에서는 7이 더 크다고 판단하고 이동한다.
그리고 두 번째 계층이자 갈림길인 (4,8) 중에서 8이 더 크다고 판단하고 이동한다.
이를 통해서 찾은 해인 8은 전체 트리에서 사실상 가장 큰 값은 아니지만, 그렇게 나쁜 결과는 아니라고 생각할 수 있다.
즉, 지금 당장 좋아보이는 것을 추구해도 그렇게 큰 손해가 아닐 것이라는 기대를 토대로 수행되는 알고리즘이다.
이러한 그리디 알고리즘은 완전 탐색과 같은 방법에 비해 늘 최적의 해를 찾아줄 수 있는 것은 아니지만,
비교적 빠르고 간단하게 문제를 해결해줄 수 있다는 장점을 가지고 있다.
[예제 1번] 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
N = int(input())
# 큰 단위의 화폐부터 확인 - 최소 개수를 희망하기 때문
coin = [500, 100, 50, 10]
result = 0
for i in coin:
result += N // i # num of coin
N = N % i # balance of input N
return result- 화폐의 단위에서 큰 수는 작은 수들의 배수이다. 따라서 큰 수로 먼저 거슬러 주고, 남은 금액을 작은 수로 거슬러주면 된다!
→ 만약 화폐의 단위가 서로 배수가 아니라면?
→ 그 때는 그리디 알고리즘이 아닌, 다이나믹 프로그래밍이나 그래프 알고리즘으로 푼다! - 따라서 500, 100, 50, 10원을 리스트로 저장해놓고 이를 // 연산자와 % 연산자를 이용하여 푼다
→ // 연산자는 몫을 구할 수 있다! 즉 현재 금액에서 현재 단위로 나누어질 수 있는 동전의 개수를 구해준다
→ % 연산자는 현재 단위로 최대한 많이 동전을 교환하고, 남은 금액을 저장하기 위함이다. 남은 금액을 저장하는 이유는 다음 단위의 동전들에서 다시 거스르기 위함이다
[예제 2번] 큰 수의 법칙
큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 본 문제에서 제시한 큰 수의 법칙에 따른 결과를 출력하시오
[입력 예시]
5 8 3
2 4 5 4 6
[출력]
46
N, M, K = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse = True)
result = (data[0] * K + data[1]) * (M//(K+1)) + data[0] * (M%(K+1))
print(result)- 본 문제에서는 리스트 내에서 가장 큰 수와 두 번째로 큰 수 만을 이용하여 푼다
- 우선 가장 큰 수를 K번 반복하고, 두 번째로 큰 수를 한 번 더해준다
→ 이를 M // (K+1) 번 반복한다 - 그리고 M % (K+1) 번 만큼 가장 큰 수를 다시 더한다
- 이 문제는 for문을 이용해서도 풀 수 있지만, M이 너무 커질 것을 고려했을 때 수학적으로 푸는 것이 더욱 시간복잡도 측면에서 이득을 볼 수 있다.
[예제 3번] 숫자 카드 게임
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고, 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N×M 형태로 높여있다. 이 때, N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그 다음에 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
N, M = map(int, input().split())
minimums = []
for i in range(N):
data = list(map(int, input().split()))
minimums.append(min(data))
print(max(minimums))- 본 문제의 핵심은 각 행마다 가장 작은 수를 뽑는 것이고, 그리고 그 중에서 가장 큰 수를 뽑는 것이다
- 이를 구현하면 위의 코드와 같다.
[예제 4번] 1이 될 때 까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1) N에서 1을 뺀다
2) N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오
N, K = map(int, input().split())
count = 0
while N != 1:
if N % K == 0:
N = N // K
else:
N -= 1
count += 1
print(count)- 문제의 조건을 잘 읽고, 그대로만 구현하면 풀 수 있다
- N에서 -1씩 빼는 것보다, N을 K로 나누는 것이 무조건 연산의 수를 더 줄일 수 있기 때문에, 이를 먼저 체크한다
- 만약에 N을 K로 나눌 수 있다면 나누고, 나누지 못한다면 -1을 수행한다
- 그리고 각 연산을 수행하고 카운팅을 한다.
본 포스트는 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책 내용을 토대로 작성되었습니다
