완전 탐색(Brute Force)은 문제의 모든 가능한 경우의 수를 하나하나 전부 확인하는 알고리즘 접근 방식이다. 즉, 해답을 찾기 위해 가능한 모든 후보를 생성하고, 각 후보가 문제의 조건을 만족하는지 검사하는 방법이다.

주요 개념

• 모든 경우의 수 고려: 문제의 해답이 될 수 있는 모든 후보를 나열한다. 예를 들어, 1부터 n까지의 숫자 중 특정 조건을 만족하는 조합을 찾는 문제에서는 가능한 모든 조합을 생성한다.
• 조건 검증: 생성된 각 후보에 대해 문제에서 제시한 조건을 만족하는지 하나씩 확인한다. 조건을 만족하는 후보가 최종 해답이 된다.

장점과 단점

• 장점:
  • 보장된 정확성: 모든 경우를 탐색하기 때문에 조건을 만족하는 해답을 반드시 찾을 수 있다.
  • 구현의 단순함: 알고리즘의 아이디어가 직관적이고 구현이 비교적 간단한다.
• 단점:
  • 계산 비용: 후보의 개수가 많아지면 모든 경우를 탐색하는데 걸리는 시간이 매우 길어질 수 있다.
  • 비효율성: 입력의 크기가 크거나 경우의 수가 많을 때는 실행 시간이 급격하게 증가하므로 다른 효율적인 알고리즘(예: 백트래킹, 동적 계획법 등)이 필요할 수 있다.

예시

예를 들어, “1부터 10까지의 숫자 중 5개를 고르는 조합 중 특정 조건을 만족하는 조합의 개수를 찾는 문제”에서는:

• 후보 생성: 1부터 10까지의 숫자 중 5개를 선택하는 모든 조합, 즉 (10/5) 개의 후보를 생성한다.
• 조건 확인: 각 조합에 대해 문제의 조건(예: 주어진 숫자들과의 공통 요소 개수 등)을 하나씩 확인하여 조건을 만족하는지를 검사한다.
• 결과 도출: 조건을 만족하는 조합의 수를 최종 결과로 반환한다.

이처럼 완전 탐색은 문제의 가능한 모든 경우를 고려함으로써 문제의 해답을 보장하지만, 경우의 수가 많아질 때는 실행 속도가 문제될 수 있으므로 입력 범위를 잘 고려하여 사용해야 한다.

참고

• ChatGPT(o3-mini-high)