탐욕법이 실패하는 순간 포착하기
믿기 전에 반례를 찾아봅니다
탐욕법이 실패하는 순간 포착하기은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
그리디는 유혹적입니다
그리디 방식은 짧고 빠르며 당연해 보이기 때문에 오히려 여러분을 함정에 빠뜨릴 수 있습니다. 깔끔한 아이디어가 항상 올바른 아이디어인 것은 아닙니다. ⚠️
동전 교환의 함정
동전 1, 3, 4로 6을 만들 때 그리디 방식은 4를 먼저 고른 뒤 1 두 개가 더 필요하므로 총 세 개의 동전을 사용합니다. 실제 최적해는 3 두 개입니다.
무엇이 잘못되었을까요
가장 큰 동전은 국소적으로는 좋은 선택이었지만 전역 최적해를 가로막았습니다. 그리디 방식은 선택을 되돌릴 수 없어서 동전 두 개로 만드는 답을 놓쳤습니다.
반례를 찾아보세요
가장 빠른 검사는 아주 작은 반례를 찾는 것입니다. 그리디 방식과 실제 최적해가 달라지는 작은 입력이면 됩니다. 하나만 찾아도 그리디 방식을 기각할 수 있습니다.
0/1 배낭 다시 보기
나눌 수 없는 항목에서는 비율을 기준으로 한 그리디 방식이 실패합니다. 밀도가 높은 작은 항목 하나가 그것을 합친 것보다 가치가 큰 두 항목을 밀어낼 수 있기 때문입니다. 나누어 담을 수 있다는 자유가 빠져 있었습니다.
선택이 서로 영향을 줄 때
한 항목을 고르는 일이 다른 항목을 선택할 가치가 있는지에 영향을 준다면 그리디 방식은 자주 실패합니다. 얽힌 의존 관계가 보인다면 DP를 고려하세요.
철저히 시험해 보세요
느린 완전 탐색과 무작위 생성기를 작성한 다음, 수천 개의 작은 사례에서 두 결과를 비교하세요. 한 번의 불일치만으로도 결함을 드러낼 수 있습니다.
for _ in range(10000):
t = random_case()
assert greedy(t) == brute(t)교환 시험
그리디 방식을 믿으려면 교환 논증을 증명해 보세요. 그리디 선택이 어떤 최적해에 포함되도록 만들 수 있음을 보이지 못한다면 계속 의심해야 합니다.
보조 절차로서의 그리디
그리디 방식이 전체 답은 아니더라도 더 큰 DP나 탐색 안에서 구성 요소가 될 수 있습니다. 증명으로 안전하다고 확인된 곳에서 사용하세요.
제약 조건을 읽으세요
N이 작다면 그리디 방식이 전혀 필요하지 않을 수 있습니다. 완전 탐색이나 DP로도 통과할 수 있으며, 정확성에 대한 위험을 아예 피할 수 있습니다.
점수를 지켜 주는 습관
그리디 방식으로 추측한 답을 제출하기 전에 잠시 시간을 내어 반례를 찾아보세요. 이 작은 확인만으로도 아픈 오답 판정을 막을 수 있습니다.
빠른 확인
그리디 전략이 잘못되었을 수 있다고 의심하고 있습니다.
복습
일부 동전 집합과 0/1 배낭 문제처럼 국소적인 이점이 전역 최적해를 가로막으면 그리디 방식은 실패합니다. 믿기 전에 반례를 찾고 철저히 시험하세요. 🚀
자주 묻는 질문
“탐욕법이 실패하는 순간 포착하기” 강의는 무료인가요?
네 — “탐욕법이 실패하는 순간 포착하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“탐욕법이 실패하는 순간 포착하기”에서 뭘 배우나요?
믿기 전에 반례를 찾아봅니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“탐욕법이 실패하는 순간 포착하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 탐욕적 사고방식
- 가장 이른 종료 시간으로 활동 선택하기
- 비율을 이용한 분할 배낭
- 탐욕법이 실패하는 순간 포착하기