📝완전탐색
컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.
🎯완전탐색 특징
- 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.
- 운이 좋다면 빠르게 답을 도출할 수 있지만, 운이 나쁘면 가장 마지막 경우의 수가 답이 되어 계산이 오래 걸릴 수 있다.
- 효율적인 문제 해결에는 적합하지 않은 탐색 알고리즘이다.
완전탐색 기법
완전 탐색 자체가 알고리즘은 아니기 때문에 완전 탐색 방법을 사용하기 위해서 여러 알고리즘 기법을 이용한다. 주로 이용되는 기법들은 다음과 같다.
① 단순 Brute Force 기법
- 반복 / 조건문 등으로 모든 case들을 만들어 답을 구하는 방법이다.
- 아주 기초적인 문제에서 이용되거나 전체 풀이의 일부분으로 이용, 단독으로 사용되는 경우는 거의 없다.
② 순열(Permutation)
- 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다.
- 완전 탐색의 대표적인 유형이다.
- 순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산한다.
- 시간복잡도는 O(N x (N - 1)!) = O(N!)
③ 재귀 호출
- 자기 자신을 호출한다는 의미이다.
- 비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용한다.
✔ 재귀 함수 사용시 주의할 점
1. 현재 함수의 상태를 저장하는 parameter와 재귀를 탈출하기 위한 탈출 조건이 반드시 필요하다.
2. return문을 명확하게 정의해야한다.
④ 비트마스크
- 2진수 표현 기법을 활용하는 방법이다.
- 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용된다.
- 비트 연산의 시간복잡도는 내부적으로 상수 시간 정도로 처리가 되어 O(1)이다.
- 배열 활용만으로 해결할 수 없는 문제를 해결할 수 있다.
⑤ BFS, DFS를 활용하는 방법
- 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.
- 대표적인 유형으로 길 찾기 문제가 있다.
참고자료
도라에몽 암기빵