[알고리즘/Python] 완전 탐색

1. 개요

💡완전 탐색이란?

• 알고리즘에서 사용되는 기법 중 하나로 '모든 가능한 경우의 수를 탐색'하여 '최적의 결과를 찾는 방법'을 의미합니다.
• 모든 가능성을 고려하기 때문에 항상 최적의 해를 찾을 수 있지만 경우의 수가 매우 많은 경우 시간과 메모리의 부담이 커질 수 있습니다. 그렇기에 문제의 특성에 따라 다른 탐색 기법을 사용하는 것이 좋습니다.
  • 이진 탐색
  • 선형 탐색

2. 완전 탐색의 종류

• 탐색 알고리즘 중에서 '완전 탐색'을 이해하고 각각의 탐색 종류에 대해서 이해합니다.
• 

알고리즘 종류	설명	장점	단점
브루토 포스	'모든 경우의 수를 탐색'하면서 원하는 결과를 얻는 알고리즘을 의미합니다.	가능한 모든 경우를 다 검사하기 때문에 예상된 결과를 얻을 수 있음	경우의 수가 많을 경우 시간이 오래 걸림
비트마스크	'모든 경우의 수'를 이진수로 표현하고 '비트 연산'을 통해 원하는 결과를 빠르게 얻는 알고리즘	이진수 연산을 이용하여 계산 속도가 빠름	경우의 수가 많아 질수록 메모리 사용량이 늘어남
백트래킹	결과를 얻기 위해 진행하는 도중에 '막히게 되면' 그 지점으로 다시 돌아가서 '다른 경로를 탐색'하는 방식을 의미합니다. 결국 모든 가능한 경우의 수를 탐색하여 해결책을 찾습니다.	경우의 수를 줄이면서도 모든 경우를 탐색할 수 있음	재귀 함수를 이용하기 때문에 스택 오버플로우가 발생할 가능성이 있음
순열	'순열'을 이용하여 모든 경우의 수를 탐색하는 방법입니다. 순열은 서로 다른 n개 중에서 r개를 선택하여 나열하는 방법을 의미	경우의 수가 가 적을 때 사용하면 유용함	경우의 수가 많을 경우 시간이 오래 걸림
재귀함수	자기 자신을 호출하여 모든 가능한 경우의 수를 체크하면서 하면서 최적의 해답을 얻은 방식을 의미합니다.	코드가 간결하며, 이해하기 쉽습니다.	스택 오버플로우가 발생할 가능성이 있음
DFS/BFS	깊이 우선탐색(DFS: Depth-First Search) - 루트 노드에서 시작하여 다음 분기로 넘어 가기전에 해당 분기를 완벽하게 탐색하는 방법 너비 우선 탐색(BFS: Breadth-First Search) - 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미합니다.	미로 찾기 등에 유용함	최악의 경우, 모든 노드를 다 방문해야 하므로 시간이 오래 걸림

3. 완전 탐색의 시간 복접도

• 비트마스크 > DFS/BFS > Brute-Force> 재귀함수 > 순열 > 백트래킹

알고리즘 종류	시간복잡도
브루트 포스	O(n^m)
비트마스크	O(2^n *n)
순열	최악의 경우, O(n!)
재귀함수	O(n)
DFS/BFS	O(V+E)