[Algorithm] 1. 완전 탐색(Brute Force Search)

완전탐색, Brute Force Search란?

발생 가능한 모든 경우의 수를 전부 탐색 하면서 조건에 맞는 답을 찾아내는 방법

✔️ 일반적으로 경우의 수가 상대적으로 작을 때 유용

✔️ 상대적으로 빠른 시간에 문제 해결(알고리즘 설계) 가능

✔️ 모든 경우의 수를 확인하기 때문에 정답 확률이 매우 높음

✔️ 먼저 완전탐색으로 푼 후에 시간 개선을 위해 다른 알고리즘을 사용해 보는 것이 효율적

완전 탐색의 종류

1. 브루트 포스 (Brute Force)

• 반복문과 조건문을 사용하여 가능한 모든 방법을 단순하게 찾는 기법
• ex) 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) : 최대한 넓게 이동한 다음, 더 이상 이동할 곳이 없을 때 아래로 이동하는 방식, 큐를 이용해 구현