완전 탐색 (Brute Force)

완전 탐색

브루트 포스로도 불리는 완전 탐색은 제목 그대로 싸그리 찾는 컨셉이다.
무식하게 때려박을 수 있는 문제는 이것부터 써내려가곤 한다.
1차적으로 해결이 목표일 때는 여기서 시작해서, 차차 코드를 시간복잡도가 더 우세한 영역으로 고치곤 한다.
백준의 N과 M(1) - (12)을 생각하면 보다 빠르게 감을 잡을 수 있다.

파일럿 코 :
구현이 간단하고 직관적인 완전 탐색은 일반적으로 성능이 상대적으로 좋지 못합니다.
경우의 수가 매우 많은 경우를 걸러내지 못하고 비효율적으로 작동하는 경우가 잦기 때문입니다.
완전 탐색은 기본적인 접근법일 뿐이며, 효율적인 해결책을 위해 보통 더 딥한 알고리즘으로 대체하곤 합니다.

덩치 큰 복잡도 유형들이 여러가지 있다.

• 모든 가능한 조합을 탐색 : Combination Search
  주어진 집합에서 가능한 조합을 생성하여 확인한다. 요구하는 조건을 찾을 때까지 모든 조합을 검사한다.
  시간 복잡도는 n COMBINATION k, (n! / (k! * (n - k)!)로 나타낸다.
• 모든 가능한 수열을 탐색 : Permutation Search
  가능한 모든 순서로 배열된 순열을 생성하여 탐색한다. 순서가 중요한 문제에서 자주 사용된다.
  주어진 숫자로 만들 수 있는 모든 순열을 찾는게 주 목표이다. 시간 복잡도는 O(n!)이다.
• 모든 가능한 부분 집합을 탐색 : Subset Search
  모든 부분 집합을 생성하고 이를 하나씩 확인한다.
  부분 집합 문제는 집합 내의 원소 중 일부만 선택하여 조건을 만족하는지 확인하는데 필요하다.
  부분 집합의 갯수는 2^n 만큼 증가하므로 시간 복잡도는 O(2^n)이다.

• 탐색 공간을 모두 순회하는 방식 : Exhaustive Search
  문제 해결을 위해 모든 가능한 상태를 하나씩 순차적으로 탐색하는 방식 이는 가능한 모든 상태를 탐색하는 방법이므로,
  상태 공간이 커질수록 시간이 급격하게 증가한다. 배열에서 특정한 값이 존재하는지 확인하는 문제등에서 사용한다.
  시간 복잡도는 문제의 크기 n에 따라 최소 O(n)이다.

• 백트래킹 : Backtracking
  조건을 만족하지 않는 경우 이전 단계로 돌아가서 다른 가능성을 시도하는 방식이다.
  불필요한 탐색을 줄이기 위해 사용하며 일반적인 완전 탐색보다는 보다 효율적이고 다방면에서 이용된다.

일반적인 완전 탐색의 최적화 방안이다보니 난이도는 상대적으로 좀 있는 편이었다고 체감한다..

• 최적화 문제에서의 완전 탐색 (Optimization Search)
  최적화 문제에서 가능한 모든 해를 탐색하는 문제이다. 가장 효율적인 방법, 최소값 또는 최대값을 찾는 문제에서 활용한다.
  경우의 수가 커지기 때문에, 이 문제는 실제로 완전 탐색이 다른 방법과 비교하면 매우 비효율적이다.
  보통 동적 계획법이나 근사 알고리즘의 내용으로 같은 문제를 해결하곤 한다.

• 그리디 알고리즘과 결합된 완전 탐색
  그리디 알고리즘을 이용하여 탐색하는 동안, 선택을 할 때마다 최적의 선택을 하는 방식이다. 그리디를 여전히 사용하지만, 모든 경우를 탐색하며 최종적으로 가장 좋은 선택을 찾는다.

요약하면, 작은 문제나 단기적으로 정확한 해를 구하는 문제에서 효과적으로 사용된다고 한다.
큰 문제도 일단 이거 때려박아야 하는경우도 있지 않을까..