개념
지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
관찰을 통해 탐색의 범위를 줄이는 알고리즘
이상적인 풀이 흐름
- 관찰을 통해 탐색범위를 줄이는 방법을 고안한다.
- 탐색범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.
- 구현해서 문제를 통과한다.
현실적인 풀이 흐름
- 관찰을 통해 탐색범위를 줄이는 방법을 고안한다.
- 탐색범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
- 믿음을 가지고 구현해서 문제를 통과한다.
추천전략
거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다.
→ 짜서 제출해보고 틀리면 빠르게 손절
100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
→ 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20~40분 남은 시점에서 코딩 시작
꿀팁
- 그리디는 코딩테스트에서 그렇게 자주 등장하는 문제라고 보기 어렵다.
- 오히려 그리디라고 착각해서 시간을 낭비하는 경우가 많다.
boj-11047
- 명제
- 동전을 최소로 소모하면서 물건값을 지불하려면 500원 동전을 최대한 많이 써야한다.
- 증명
- 10, 50, 100원 동전으로는 물건값을 최대 10X4+50X1+100X4=490원만 감당가능,500원을 다 사용하지 않을 경우 10,50,100원동전으로 500원 이상 감당해야함
import sys
input = sys.stdin.readline
N, price = map(int, input().split())
coins = [int(input()) for _ in range(N)]
cnt = 0
for i in reversed(range(N)):
cnt += price //coins[i]
price = price % coins[i]
print(cnt)배수관계가 성립하지 않을 때에도 지금 만든 그리디 알고리즘이 잘 동작할 것인가를 생각해보아야 한다.
1, 9, 10 원을 사용하여 18원을 만든다면 그리디 알고리즘은 10원을 먼저 쓰고 남은 8원을 8개 사용하게 된다.
따라서 비슷한 문제를 봤다는 이유만으로 문제를 한정짓는건 위험하다.
boj-1931
먼저 끝난회의를 선택하면 회의의 최대갯수를 구할 수 있다는 명제로 그리디 알고리즘을 구현한다.
어떻게 증명할 수 있을까? 명제를 거짓이라고 가정하고 나중에 끝난 회의가 더 많은 회의를 가질 수 있다는 명제로 생각해보면 나중에 끝난 회의를 삭제해도 스케줄의 변화는 없다.
따라서 먼저 끝난 회의는 적어도 나중에 끝난 회의보다 같거나 많은 회의를 추가로 가지기 때문에 귀류법을 통해서 명제가 맞다는 사실을 증명할 수 있다.
import sys
input = sys.stdin.readline
N = int(input())
meeting_schedules = [list(map(int,input().split())) for _ in range(N)]
meeting_schedules.sort(key = lambda x : (x[1], x[0]))
answer = 0
end_time = 0
for i in range(N):
start, end = meeting_schedules[i]
if end_time <= start:
answer+=1
end_time = end
print(answer)boj-2217
import sys
input = sys.stdin.readline
N = int(input().rstrip())
lopes = sorted([int(input().rstrip()) for _ in range(N)], reverse=True)
max_weight = lopes[0]
for i in range(1, N):
max_weight = max(max_weight, lopes[i] * (i+1))
print(max_weight)가장 큰 로프들을 활용해서 구할 수 있고 현재 최대값과 지금 로프의 무게를 병렬로 구한값을 비교하여 업데이트 해주면 된다.
boj-1026
서로 교차되게 정렬을 한 후 곱하면 최솟값이 된다.
그리디 문제를 접하고 잘 모르겠을 때는 일단 정렬을 하고 이리저리 끼워 맞추는 식으로 풀이를 시도해볼 수도 있다.
N = int(input())
first = sorted(list(map(int, input().split())) , reverse=True)
second = sorted(list(map(int, input().split())))
answer= 0
for i in range(N):
answer += first[i] * second[i]
print(answer)그리디 같지만 그리디로 풀리지 않는 문제들
boj-12865
boj-1477
정리
그리디문제는 그리디인걸 알고 푸는 것과 그렇지 않은 경우의 차이가 크다. 그래서 혼자 이리저리 고민해보다 혹시 그리디로 풀리지 않을까하고 사고를 넓혀가면 좋다.
피드백
요즘 읽고 있는 알고리즘 책도 그렇고 바킹독 유튜브를 보면서 정리해보면서도 느끼는 거지만 결국 수학적 증명방법, 논리적인 사고등이 중요하게 느껴진다. 취직하고 여유가 된다면 수학강의를 듣는 것도 좋은 선택이 될 수 있을 것 같다.
