눈앞에서 제일 좋은 걸 고른다냥! 그리디
안녕, 나 코딩냥이다냥! 11장에서는 다 해봤다냥. 오늘은 정반대라냥 — 한 번도 안 돌아보고 앞으로만 간다냥.
매 순간 제일 좋아 보이는 걸 덥석 집는 거라냥. 그래서 이름이 그리디 (욕심쟁이) 라냥. 코드는 오늘 배우는 것 중 제일 짧다냥. 대신 생각이 제일 어렵다냥.
오늘의 학습 목표
- 그리디가 무엇을 하는 방법인지 안다.
- 대부분의 그리디가 정렬에서 시작한다는 걸 안다.
- 그리디가 틀리는 경우를 반례로 직접 본다.
- 무엇으로 정렬할지 문제마다 다르다는 걸 안다.
- 내 기준이 맞는지 확인하는 방법을 안다.
1단계 · 욕심쟁이가 뭐냥 (8분)
거스름돈 1300원을 줄 때 어떻게 하냥? 500원 두 개, 100원 세 개라냥. 큰 것부터 최대한 집었다냥. 그게 그리디라냥.
비유로 이해하기 — 뷔페에서 접시 담기
접시는 하나인데 음식이 많다냥. 그리디는 제일 맛있어 보이는 것부터 차례로 담는 거라냥. 담고 나서 "아까 그거 뺄 걸" 하고 되돌리지 않는다냥.
11장의 완전탐색은 접시에 담는 모든 조합을 다 해봤다냥. 그리디는 한 번만 훑는다냥. 그래서 훨씬 빠르다냥.
대신 위험하다냥. 되돌아보지 않으니, 처음 고른 게 잘못됐으면 끝까지 잘못된 채로 간다냥.
- 어떤 기준으로 고를지 정한다 — 오늘의 어려운 부분이라냥
- 그 기준대로 앞에서부터 한 번 훑는다 — 오늘의 쉬운 부분이라냥
1번이 정해지면 2번은 열 줄 안쪽이라냥. 그래서 그리디 문제는 코드가 짧은데 어렵다냥.
2단계 · 정렬이 절반이라냥 (10분)
"어떤 기준으로 고를지"가 정해지면, 그건 보통 정렬 기준이라냥.
그래서 그리디 코드는 대개 sort 로 시작한다냥.
ATM 앞에 사람들이 줄을 섰다냥. 각자 걸리는 시간이 다르다냥. 모두가 기다린 시간의 합을 제일 작게 하려면 누구를 앞에 세워야 하냥?
짧은 사람부터라냥. 왜 그런지가 중요하다냥.
맨 앞사람이 쓴 시간은 뒤에 선 모든 사람이 다 같이 기다린다냥. 뒷사람이 쓴 시간은 자기만 기다린다냥.
그러니 여러 번 더해지는 자리에 짧은 사람을 두는 게 이득이라냥.
times.sort()
run = 0
total = 0
for t in times:
run += t # 이 사람까지 걸린 시간이라냥
total += run # 그게 이 사람이 기다린 시간이라냥
print(total)위에서 "앞자리는 여러 번 더해진다" 라고 말했다냥. 이게 이 정렬 기준의 이유라냥.
그리디에서 기준을 고를 때는 항상 이렇게 물어보자냥 — "이걸 앞에 두면 왜 이득이냥?"
대답을 못 하면 그 기준은 아마 틀린 거라냥. 오늘 3단계에서 바로 그런 경우를 본다냥.
3단계 · 그리디는 자주 틀린다냥 (15분)
오늘 가장 중요한 단계라냥. 그리디는 항상 되는 방법이 아니라냥. 11장의 완전탐색은 느릴 뿐 항상 맞았다냥. 그리디는 빠르지만 틀릴 수 있다냥.
거스름돈을 다시 보자냥. 우리 동전은 1, 5, 10, 50, 100, 500원이라냥. 큰 것부터 집으면 항상 최소 개수가 나온다냥.
그런데 동전이 1원, 3원, 4원짜리뿐인 나라라면 어떻게 되냥?
6원을 만들어보자냥.
큰 것부터 집는 그리디는 이렇게 한다냥.
- 4원을 집는다 (남은 돈 2원)
- 4원은 너무 크니 3원도 너무 크니 1원을 집는다 (남은 돈 1원)
- 1원을 집는다 (남은 돈 0원)
동전 3개라냥. 그런데 정답은 3원 + 3원 = 2개라냥.
그리디가 틀린 답을 냈다냥. 코드에 버그가 있는 게 아니라, 방법 자체가 이 문제에서는 안 맞는 거라냥.
왜 우리 동전으로는 되고 1·3·4로는 안 되냥?
우리 동전은 큰 동전이 작은 동전의 배수라냥. 500은 100의 5배, 100은 50의 2배라냥. 그래서 큰 걸 집어도 손해가 안 난다냥.
1, 3, 4는 아니라냥. 4는 3의 배수가 아니라냥. 그래서 4를 집는 순간 3원짜리 두 개로 딱 떨어질 기회를 놓친다냥.
오늘 1번 문제가 배수 조건을 문제에 못 박아둔 이유가 이거라냥. 그 조건이 없으면 그리디로 풀면 안 된다냥.
그래서 문제의 조건을 잘 읽어야 한다냥.
"각 동전은 그보다 작은 동전의 배수" 같은 문장은 장식이 아니라냥. "이 문제는 그리디로 풀어도 된다" 는 허락이라냥.
그 문장이 없는데 그리디로 풀면 틀린다냥. 그런 문제는 13장에서 배울 방법으로 풀어야 한다냥.
4단계 · 무엇으로 정렬하냐가 전부라냥 (15분)
회의실이 하나 있다냥. 회의 신청이 잔뜩 들어왔는데 시간이 겹치는 것들이 있다냥. 최대한 많은 회의를 하려면 어떤 걸 골라야 하냥?
그럴듯한 기준이 여러 개 떠오른다냥.
- 일찍 시작하는 회의부터 — 그럴듯하지만 틀린다냥
- 짧은 회의부터 — 이것도 그럴듯하지만 틀린다냥
- 일찍 끝나는 회의부터 — 이게 정답이라냥
왜 "일찍 끝나는" 이 정답이냥?
회의실을 가장 빨리 비워주는 회의이기 때문이라냥. 빨리 비면 남은 시간이 길어지고, 남은 시간이 길수록 뒤에 더 많이 넣을 수 있다냥.
2단계에서 말한 그거라냥 — "이걸 먼저 고르면 왜 이득이냥?" 에 대답할 수 있다냥.
각 후보가 왜 틀리는지 직접 보자냥.
"일찍 시작하는 회의부터" 가 틀리는 예라냥.
회의가 (1, 4), (2, 3), (3, 5) 세 개 있다냥.
일찍 시작하는 순서로 고르면 (1, 4) 를 먼저 잡는다냥. 그러면 (2, 3) 도
(3, 5) 도 겹쳐서 못 쓴다냥. 1개라냥.
일찍 끝나는 순서면 (2, 3) 을 먼저 잡고, 그다음 (3, 5) 를 잡는다냥.
2개라냥.
"짧은 회의부터" 가 틀리는 예라냥.
회의가 (1, 10), (9, 12), (11, 20) 세 개 있다냥.
제일 짧은 건 (9, 12) 라냥 (3시간). 이걸 먼저 잡으면 앞뒤가 둘 다
막힌다냥. (1, 10) 도 (11, 20) 도 겹친다냥. 1개라냥.
일찍 끝나는 순서면 (1, 10) 과 (11, 20) 을 잡아서 2개라냥.
짧은 회의 하나가 가운데 끼어서 양쪽을 다 망치는 거라냥.
# 끝나는 시각 기준이라냥
meetings.sort(key=lambda m: (m[1], m[0]))
end = -1
cnt = 0
for s, e in meetings:
if s < end:
continue # 겹치니 건너뛴다냥
cnt += 1
end = e # 회의실이 이제 e 에 빈다냥같은 입력이라도 질문이 다르면 기준이 달라진다냥.
오늘 4번과 5번 문제는 입력이 완전히 똑같다냥. 그런데 4번은 "회의실 하나에 최대 몇 개", 5번은 "전부 열려면 회의실이 몇 개"를 묻는다냥.
4번은 끝나는 시각으로 정렬하고, 5번은 시작과 끝을 사건으로 쪼개서 훑는다냥. 4번 풀이를 5번에 그대로 내면 틀린다냥.
문제를 먼저 읽고 기준을 정하는 것, 그게 오늘의 전부라냥.
5단계 · 내 기준이 맞는지 확인하기 (10분)
기준을 정했는데 맞는지 확신이 안 선다냥. 그럴 때 쓰는 방법이 있다냥. 11장에서 배운 완전탐색을 꺼내는 거라냥.
- 아주 작은 입력을 여러 개 만든다냥 (3~5개짜리라냥)
- 완전탐색으로 진짜 답을 구한다냥 — 느려도 상관없다냥, 작으니까
- 그리디로도 구한다냥
- 두 답이 다른 입력이 나오면, 그게 내 기준의 반례라냥
작은 입력에서 백 번 맞으면 대체로 맞는 기준이라냥. 한 번이라도 다르면 확실히 틀린 기준이라냥.
3단계의 1, 3, 4 동전 반례도 이렇게 찾을 수 있다냥.
금액을 1부터 20까지 돌려보면서 그리디 개수와 완전탐색 개수를 비교하면
6 에서 처음으로 갈린다냥. 손으로 고민할 필요가 없다냥.
반례를 못 찾았다고 맞는 건 아니라냥.
이건 틀렸다는 걸 빨리 알아내는 방법이지, 맞다는 걸 증명하는 방법이 아니라냥. 그래도 입문 단계에서는 이걸로 충분하다냥.
진짜 증명은 "왜 이득이냥?" 에 제대로 대답하는 거라냥. 2단계와 4단계에서 한 그거라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번은 거스름돈, 2번과 3번은 정렬 한 번으로 끝나고, 4번과 5번은 입력이 똑같은데 답이 갈리는 짝이라냥.
풀기 전에 항상 이걸 먼저 정하자냥 — 무엇을 기준으로 고를 거냥? 그리고 왜 그게 이득이냥? 가보자냥~