1. 개요
현재 상황에서 당장 좋은 것만 고르는, 특정 기준 하나만을 선택하여 기준대로 최적의 해를 구하는 방법이다.
그리디 알고리즘의 핵심은 어떤 기준을 적용하고 적용할 것인지 판단하는 것이다.
2. 적용
아래와 같은 graph가 있다고 하자.
이때 노드의 값을 최대로 얻고자 할 때는 어떤 알고리즘을 적용해야 하는가?
물론 만나는 노드마다 최대의 값을 선택하면 된다면, 최대값을 기준으로 그리디 알고리즘을 적용할 수 있다.
그러나 5>7>9와 5>10>4와 같이 그리디 알고리즘의 반례가 나타날 수 있는데, 이처럼 그리디 알고리즘이 최적의 해를 보장하지는 않을 수 있다(다만 최적의 해에 가까운 방안을 도출해는 것은 가능).
따라서 최적의 해를 도출해내기위해 어떤 특정 기준, 혹은 sub 기준까지 어떻게 마련할것인가를 생각해내는 것이 중요하다.
key point :
- 적용할 기준이 명확하다.
- 코드를 줄일 수 있는 라이브러리 및 함수가 있는가
- 그리디(main) 기준과 부가(sub) 기준을 어떻게 적용할 수 있는가
2-1. 손님에게 주는 거스름돈
손님에게 주어야 할 거스름돈 N원이 있다고 할 때, N원 거스름돈을 주기위한 최소 화폐의 개수는 무엇인가?
- 각 화폐단위(10, 100, 500, 1000)는 숫자가 커질 수록 모든 단위의 배수가 되어, 가장 큰 단위의 개수 순으로 몫을 구해나간다면 정상적인 최적의 해를 도출할 수 있다.
- 다만 배수가 아닐 경우엔 별도의 sub기준을 마련할 필요가 있다.
#거스름돈을 가장 적은 화폐로 거슬러준다고 할 때
def greedy(value):
result = 0
result = result + value//500
value = value % 500
result = result + value//100
value = value % 100
result = result + value//50
value = value % 50
result = result + value//10
return result
print(greedy(1260))
2-2. 숫자 문자열의 최대값 구하기
숫자문자열이 주어졌을때, 모든 값을 확인해가며 결과적으로 구할 수 있는 최대값을 구하는 알고리즘은?
- 곱하기 기준을 적용하는 그리디 알고리즘이긴 한데, 항상 곱하기가 큰 수를 만들 수 있는가?
- 이때 별도의 기준도 같이 필요
- 두 수 중 하나라도 0 혹은 1일 경우, 더하기 수행
- 두 수 모두 2이상이라면 곱하기
#입력의 최초 형태는 숫자로 구성된 "문자열"
#최초 test case 및 정수는 input()으로 입력받아도 무방
data = input()
#비교는 항상 마주하는 두 수에 대해 진행
result = int(data[0])
for i in range(1, len(data)):
#두 수 중 하나라도 0 혹은 1일 경우 더하기 수행
#이때 두 수는 일전의 결과와 다음 숫자를 의미
num = int(data[1])
if result <=1 and num <=1:
result = result + num
else:
result = result * num
print(result)2-3. N을 1로 만드는 가장 최소 경우의 수 구하기
어떤 수 N이 1이 될 때까지 두 과정 중 하나는 반복수행한다.
→ N에서 1을 뺀다
→ N을 K로 나눈다(N이 K로 나누어떨어질때 가능).
이 과정을 최소로 수행하는 알고리즘은?
#K로 나눈 과정을 최대한 많이 수행하는 기준이 명확히 정해져있다.
#N은 항상 1에 도달할 수 있다
#그리디 알고리즘 적용 가능
import sys
N, K = map(int, sys.stdin.readline().split())
result = 0
while True:
#N이 K로 나누어 떨어지는 수가 될 때까지 감안
target = N // K * K #★이런 부분) N이 K로 나누어 떨어지지 않을 경우, 나누어 떨어지는 가장 가까운 수를 구하는 과정
#(최초 값을 입력받았을때)
result = result + N - target
#그만큼 1을 감산
N = target
#N이 K보다 작아 나누어떨어지지 않을 경우엔 반복문 탈출
if N < K:
break
result = result + 1
N = N // K
#남은건 뺴는 과정
result = result + (N-1)
print(result)2-4. 특정 기준에 맞는 모험가 그룹 구하기
마을에 모험가 N명이 있다고 가정해보자.
모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정하는데, 공포도가 X인 모험가는 반드시 X명 이상으로 구성해야 모험에 참가가능하다.
N명에 대한 모험가 정보가 주어졌을때 모험을 할 수 있는 그룹의 최대 수를 구하는 알고리즘은?
이때의 핵심은, 일단 가장 낮은 수를 찾는다는 점에서 그리디 알고리즘이다(모험가를 공포도에 따라 일렬로 정렬).
다만 별도의 기준으로, "오름차순 정렬" 후에 낮은 숫자부터 순차적으로 확인하여
현재 그룹에 포함된 모험가의 수가 공포도 이상이라면 결과도출
import sys
# key point input() 및 이를 정수화
N = int(input())
# key point 입력받고 이를 바로 list화
data = list(map(int, sys.stdin.readline().split()))
data.sort()
#결과(그룹의 수)
result = 0
#현재 모험가의 수
count = 0
#이미 정렬되어있으므로 공포도를 낮은 것 부터 차례대로 확인
for i in range(len(data)):
count = count + 1
if count >= data[i]:
result = result + 1
#이 이후부터 다시 순회를 계속해야 하므로 count = 0
count = 0
print(result)