완전탐색
- 문제를 해결하기 위해 확인해야 하는 모든 경우의 수를 전부 탐색하는 방법
- 무식하게 한다는 뜻으로 Brute-Force라고도 한다
- 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실한 방법이다
종류
- 순열
Permutation: 선택 순서가 결과에 영향을 미치는 경우 - 백트래킹
- BFS
완전탐색 구현 과정
- 가능한 모든 가짓수를 계산해본다 -> 입출력 제한이 중요하다
- 어떤 식으로 구현할지 생각한다 -> 단순 for문 사용, 순열, 재귀(백트래킹) 등이 있다
시간계산
- 보통 1억번의 연산 == 1초
- O(N) : 1억
- O(NlogN) : 5백만
- O(N^2) : 1만
- O(N!) : 11
코딩테스트에 나오는 완전 탐색 종류
- N개 중에서
- 중복을 허용해서
- 중복 없이
- M개를
- 순서있게 나열하기
- 고르기
