[Algorithm] 완전 탐색

완전 탐색?

• 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 말합니다.
• 효율성 관점에서는 최악의 방법입니다.
• '무식하게 답을 찾는다'라고 하여 Brute-Force(브루트 포스)라고도 불립니다.

완전 탐색 기법

• 완전 탐색 기법을 이용하기 위해서는 여러 알고리즘 기법이 사용된다.
• 완전 탐색 기법만을 가지고는 알고리즘 문제를 풀기에는 적합하지 않습니다.

주로 사용되는 알고리즘 기법

1. 단순 Brute-Force
   • 알고리즘 기법을 사용하지 않고 단순히 반복문을 통해 답을 구하는 방법입니다.
2. 비트 마스크(Bitmask)
   • 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식입니다.
3. 재귀 함수
   • 재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식입니다.
   • 무한루프에 빠질 수 있음을 주의해서 작성해야 합니다.
4. 순열(Permutation)
   • 완전 탐색의 대표적인 유형으로 서로 다른 N개를 나열하는 순열을 구하는 방식입니다.
5. BFS / DFS
   • 완전 탐색과 BFS/DFS 문제가 코딩 테스트에 많이 나오고 있으며, 대표적인 문제로 길 찾기 문제가 있습니다.