local-choiceexchange-argumentoptimality

Greedy algorithm을 설명해 주세요

예상 시간
6분
30초 답변

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

Greedy가 실패하는 대표적인 예는 무엇인가요?

부가 설명

Greedy는 직관적으로 좋아 보여서 오히려 위험합니다. 매번 가장 큰 값을 고르거나 가장 가까운 곳으로 가는 선택이 전체 답을 망칠 수 있습니다. 그래서 Greedy 문제에서는 구현보다 “왜 이 선택을 해도 나중에 손해 보지 않는가”를 먼저 확인해야 합니다.

증명에는 교환 논증이 자주 등장합니다. 최적해가 있다고 가정하고, 그 안의 어떤 선택을 Greedy 선택으로 바꿔도 답이 나빠지지 않음을 보이면 됩니다. Greedy 선택의 근거가 약하면 DP나 완전탐색이 더 적절할 수 있습니다.

한 줄 정리

Greedy는 지금의 최선이 전체 최선으로 이어진다는 근거가 있을 때만 안전합니다.