완전 탐색도 유효한 전략입니다

모든 가능성을 시도하는 것은 실제로 인정받는 전략입니다. 입력이 작다면 가장 단순한 답이 가장 현명한 경우가 많습니다. 🙂

완전 탐색 해법은 모든 후보 답을 열거하고 하나씩 확인합니다. 영리한 요령 없이 모든 경우를 보장하는 방법입니다.

완전 탐색은 작성하기도 쉽고 신뢰하기도 쉽습니다. 미묘한 오류가 생기는 일이 드물기 때문에, 대회 중에는 안전한 첫 해법이 됩니다.

제약 조건에서 N이 최대 20 또는 100이라고 한다면 완전 탐색이 대개 시간 제한 안에 들어옵니다. 입력이 작다면 단순한 반복문을 사용할 수 있습니다.

확인해야 할 후보가 몇 개인지 추정해 보십시오. 그 개수가 대략 10^8보다 작다면 완전 탐색이 시간 안에 끝날 가능성이 큽니다.

작은 목록에서 합이 목표값이 되는 쌍을 찾는다면 모든 쌍을 확인하면 됩니다. 이 경우에는 중첩 반복문 두 개면 충분합니다.

작동하는 완전 탐색 해법은 지금 바로 점수를 얻도록 해 줍니다. 나중에 언제든 최적화할 수 있지만, 빠르면서 틀린 답보다 느리더라도 올바른 답이 낫습니다.

N이 크더라도 완전 탐색을 기준 해법으로 작성해 두십시오. 검사할 때 빠른 해법을 이 해법과 비교할 수 있습니다.

시간 제한과 N을 함께 보면 사용할 수 있는 예산을 알 수 있습니다. 완전 탐색이 그 예산에 들어간다면 문제를 지나치게 복잡하게 생각할 이유가 없습니다.

40개 항목의 모든 부분집합을 확인하는 것처럼 후보의 개수가 폭발적으로 늘어나면 완전 탐색은 실패합니다. 그때는 더 똑똑한 방법을 사용해야 합니다.

항상 먼저 한 가지를 물어보십시오. 입력이 얼마나 커질 수 있을까요? 이 한 번의 추정으로 완전 탐색이 올바른 선택인지 알 수 있습니다.

완전 탐색은 모든 후보를 열거하며, N이 작다면 정확하고 단순하면서도 충분히 빠릅니다. 먼저 개수를 추정한 다음 선택하십시오. 🚀