[Algorithm] 완전 탐색과 종류 (Brute Force Search)

완전 탐색, Brute Force Search 란?

완전 탐색과 브루트 포스의 이름에서 유추할 수 있듯이 이 알고리즘의 방법은 발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법이다. 이 알고리즘의 대표적인 장점은 모두 확인하기 때문에 100%의 확률로 정답만을 출력한다는 것이다. 하지만 확실하게 확인하는 만큼 시간이 오래 걸리는 탐색기법이다.

💡 Brute : 무식한, 짐승 같은 + Force : 힘 - 무식하게 풀기

 

완전 탐색의 종류

구조로 나누어보면 선형 구조를 전체적으로 탐색하는 방법인 순차 탐색과 비선형 구조를 전체적으로 탐색하는 방법인 DFS / BFS가 대표적인 탐색 방법이다.

1. 브루트 포스 (Brute Force)

• 브루트 포스는 반복문과 조건문을 사용하여 가능한 모든 방법을 단순하게 찾는 기법이다.
• 예를 들어, 3자리로 구성된 자물쇠를 풀어야 한다면 000부터 999까지 모든 경우의 수를 입력하는 기법이라고 생각하면 이해하기 쉽다. 확실하게 정답을 찾을 수 있지만, 정말 단순하고 무식한 방법이기에 시간이 오래 걸리게 된다.

2. 백트래킹 (Backtracking)

• 백트래킹은 답을 찾는 과정에서 이 경로가 답이 아니라고 판단되면 버리고 다른 경로를 탐색하는 방법이다. 이 방법을 가지치기(Pruning)라고 표현하는데 불필요한 가지를 처내면서 답을 찾아내서 붙은 이름이다.
• 보통 반복문의 횟수를 줄일 수 있어 효율적이지만, 최악의 경우에는 여전히 완전 탐색을 하기 때문에 경로를 찾아 가지치는 방법이 효율성을 결정하게 된다.

3. 비트 마스크 (Bit Mask)

• 비트 마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하는 방식이다. 이진수를 활용하기 때문에 문제에서 확인해야 하는 경우가 A 또는 B와 같이 두 가지 선택으로 구성되는 경우를 확인하기에 유용한 방법이다. 

4. 순열 (Permutation)

• 순열은 완전 탐색의 대표적인 유형으로 서로 다른 n개의 원소에서 r개를 중복 없이 골라 순서대로 나열하는 것(정렬이 되어있음)이다.

5. 재귀 함수 (Recursion Function)

• 재귀 함수는 자기 자신을 답을 찾을 때까지  반복적으로 참조하는 함수를 의미한다. 직관적이고 간단하다는 장점이 있지만, 자기 자신을 반복적으로 호출하는 과정에서 종료조건이 포함되거나 만족하지 못하면 무한루프에 빠질 수 있다는 위험성이 있으므로 종료조건을 고려해서 작성해야 한다.

6. 깊이우선탐색 (DFS)  /  너비우선탐색 (BFS)

• 깊이 우선 탐색 (DFS, Depth-First Search)은 최대한 깊게 내려간 뒤, 더 이상 내려갈 곳이 없을 경우 옆으로 이동하는 방식이다. 스택 또는 재귀함수로 구현한다.
• 너비 우선 탐색 (BFS, Breadth-First Search)은 최대한 넓게 이동한 다음, 더 이상 이동할 곳이 없을 때 아래로 이동하는 방식이다. 큐를 이용해서 구현한다.
• 두 방식 모두 그래프를 탐색하는 방법이며, 모든 노드를 검색하기 때문에 시간 복잡도는 동일하다.

 

완전 탐색의 장단점

장점

• 알고리즘을 구현하는 것이 상대적으로 쉽다.
• 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

단점

• 알고리즘의 실행 시간이 상대적으로 오래 걸린다.
• 모든 경우의 수를 탐색하기에 메모리를 비효율적 사용한다.