탐욕적 사고방식

탐욕적 알고리즘은 답을 단계별로 만들면서 그 순간 가장 좋아 보이는 선택을 항상 취하고, 나중에 그 선택을 되돌리지 않습니다. ⚡

매 순간 한 가지를 자문하십시오. 어떤 하나의 선택이 현재 상황에서 가장 큰 도움을 줄까요? 그것을 선택한 뒤 다음 결정으로 넘어가십시오.

탐욕 알고리즘은 선택을 확정하고 절대 되돌리지 않습니다. 되돌아가며 탐색하는 방법과 달리 다른 경로를 살펴보지 않기 때문에 매우 빠릅니다.

단계마다 한 번만 결정하므로 탐욕 알고리즘은 정렬 후 대개 O(n) 또는 O(n log n)에 실행됩니다. 대회에서 가장 큰 장점은 바로 이 속도입니다.

대부분의 탐욕 해법은 항목을 정렬하는 것부터 시작합니다. 순서를 보면 각 단계에서 어떤 요소를 선택해야 하는지 분명해집니다.

탐욕 알고리즘은 현재 상황에서 가장 좋은 선택이 전체적으로 가장 좋은 답의 일부일 때만 작동합니다. 이것이 탐욕적 선택 속성입니다.

지금 가장 좋아 보이는 단계를 선택해도 전체적으로는 실패할 수 있습니다. 홀수 단위의 동전으로 거스름돈을 만드는 문제는 탐욕 알고리즘이 잘못된 합계를 내는 대표적인 사례입니다.

탐욕 알고리즘을 믿기 전에 교환 논증으로 정당성을 설명하거나, 작은 입력에 대해 완전 탐색과 비교하는 스트레스 테스트를 수행하십시오.

교환 증명은 탐욕적 선택을 최적의 답에 넣고 그 결과가 더 나빠지지 않음을 보입니다. 이것이 성립하면 탐욕 알고리즘을 안전하게 사용할 수 있습니다.

거의 모든 탐욕 알고리즘은 다음과 같은 형태입니다. 정렬한 뒤 한 번 훑으면서 규칙에 맞는 것을 선택합니다.

선택의 순위를 정하는 명확한 순서가 있고 하나의 규칙이 계속 좋은 결과를 낼 때 탐욕 알고리즘을 시도하십시오. 선택들이 복잡하게 서로 영향을 준다면 DP를 고려하십시오.

탐욕적인 접근이 믿을 만한지 결정하려고 합니다.

탐욕 알고리즘은 대개 먼저 정렬한 뒤 현재 상황에서 최선인 단계를 선택하고 뒤돌아보지 않습니다. 빠르지만 탐욕적 선택이 성립함을 증명할 수 있을 때만 정확합니다. 🚀