1.1 완전탐색 (Exhaustive search)

<aside> 💡 "완전탐색"은 문제의 해를 찾기 위하여 가능한 모든 해를 찾아내어 그 중 주어진 조건을 만족하는 최적해를 찾는 패러다임 입니다.

</aside>

완전탐색은 알고리즘 패러다임중 하나로 가능한 모든 해를 찾아내어 그 중 조건을 만족하는 최적해를 찾아내는 방법입니다. 완전탐색은 모든 가능성을 확인하기때문에 가장 정확하고 최적의 해를 구할 수 있지만, 시간복잡도가 매우 높아질 수 있습니다.

모든 문제에 대해 완전탐색을 적용시키면 항상 답은 구해지겠지만 코딩테스트가 제한하는 시간안에 문제를 해결하지 못할 가능성이 큽니다. 그렇기에 완전탐색을 사용해야 할 시점은 다음과 같습니다.

1. 주어진 입력의 범위가 작아 가능한 모든 해를 찾는 시간이 적게 들 때즉, 시간복잡도를 계산하고 될거같다 싶으면 일일이 다 하면 됩니다. 반복문이 몇개든, 비효율적인 풀이같아 보여도 상관 없이 풀이를 작성해나가면 됩니다.
2. 코딩테스트의 문제는 대체로 시간복잡도가 10^8이내인 경우 통과가 됩니다. 그렇기에 입력의 범위가 100과 같이 작은 경우 완전 탐색으로 걸리는 시간복잡도가 O(n^2)이라면 해당 방법은 10^4의 시간복잡도를 갖기에 통과가 될 것입니다. 이와 같이 주어진 입력의 범위가 작아 완전 탐색의 시간복잡도 또한 낮아지는 경우 완전 탐색으로 빠르게 구현하여 문제를 해결할 수 있습니다.
3. 우선적으로 답을 구하고 그 과정을 최적화하여 시간을 줄이고 싶을 때
   • 정렬
   • 메모이제이션
   • 투포인터
   • DP
   • 백트래킹
   • 이진탐색
4. 주어진 입력의 범위가 커서 완전 탐색으로는 시간 제한을 맞추지 못하는 문제에도 우선 완전탐색을 적용시키는 방법을 고려할 수 있습니다. 완전 탐색은 앞서 설명했듯이 문제를 푸는 가장 기초적인 방법입니다. 그렇기에 완전 탐색을 우선 구현한 후 해당 방법을 개선해 나감으로써 시간 제한을 맞출 수 있습니다. 또한 완전탐색을 통해 진행되는 문제의 과정을 보고 문제의 유형을 파악할 수 있는 등 문제의 명확한 풀이방법을 찾지 못했을 경우에는 우선 완전탐색으로 구현하는 것도 좋은 방법입니다.

<aside> ❓ 완전 탐색 vs 브루트 포스 위 완전탐색과 브루트포스는 종종 혼용되어 사용하는데 차이는 존재합니다. 두 패러다임 모두 가능한 모든 해를 찾아내는 것은 같지만, 완전탐색은 그 모든 해를 찾아나가는 과정이 보다 체계적인 방면 브루트포스는 모든 해를 찾아나가는 과정이 이름 그대로 무식(Brute)하게 모든 해를 찾아나간다는 것이 패러다임의 차이입니다. 하지만 강의에서 두 용어를 엄밀하게 구분하진 않을 겁니다.

</aside>

코딩테스트에서 자주 나오는 완전탐색 문제는 다음과 같습니다

• 모든 가능성 탐색: 모든 가능성을 탐색해보고 문제에서 원하는 결과와 일치하는 값을 찾는 문제
• 부분집합 생성: 모든 부분집합을 생성하여 특정 조건을 만족하는 부분집합을 찾는 문제.
• 순열과 조합: 주어진 요소들로 가능한 모든 순열 또는 조합을 생성하는 문제.
• 격자 탐색: 격자 내의 모든 위치를 탐색하며 특정 조건을 만족하는 위치를 찾는 문제.

---

구현

• 반복문
• for i in range(n):
•     for j in range(i+1, n):
•  
• 재귀
• a.append()
• backtrakcing()
• a.pop()
•  
• 비트마스크

예제

1. twosum
2. 부분집합, 순열, 조합