[알고리즘] 완전 탐색

✅ 완전탐색(Brute-Force)

• 가능한 모든 경우의 수를 탐색하여 최적해를 찾는 방법
• 주어진 문제의 해를 찾기 위해 계산 복잡도가 높을 수 있음
• 특히 작은 문제나 규모가 작은 문제에 대해 사용됨
• 효율성 관점에서는 좋지 않음

과정

1. 해를 구성하는 모든 요소들의 경우의 수를 나열
2. 각 경우를 시도
3. 해가 유효한지를 검사, 유요한 해를 발견했을 경우 최적해인지 검사
4. 모든 경우를 시도하면서 최적해를 찾음

종류

1. 순열 완전 탐색 : n개의 원소로 이루어진 배열에서 가능한 모든 순열을 생성하여 탐색
2. 조합 완전 탐색 : n개의 원소로 이루어진 배열에서 가능한 모든 조합을 생성하여 탐색
3. 비트마스크 완전 탐색 : 이진수를 사용하여 가능한 모든 부분집합을 생성하여 탐색
4. 백트래킹 완전 탐색 : 가능한 모든 경우를 탐색하되, 일부 조건을 만족하지 않으면 더 이상 탐색하지 않고 이전 상태로 되돌아감
5. DFS 완전 탐색 : 그래프에서 가능한 모든 경로를 탐색하여 최적해를 찾는 방법
6. BFS 완전 탐색 : 그래프에서 가능한 모든 경로를 탐색하여 최적해를 찾는 방법