1. 완전 탐색
1.1. 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법
그 중에서도 Back-Tracking 을 통해야 하는 상황을 해결하기!
모든 코테 문제에서 기본적으로 접근해 봐야 한다. 많은 연습이 필요!
장점.
- 부분 점수 얻기 좋음.
- 어떻게든 해결하고자 하면 풀림
단점.
- 시간 복잡도가 좋지 않음
1.2. 완전 탐색 종류
완전 탐색은 함수 정의를 잘 하면 반 이상 해결 가능
1) N개 중 중복을 허용해서 순서 있게 나열
ex) N과M (3)
시간복잡도 : $O(N^M)$ 1초 안에 해결 가능
공간복잡도 : O(M)
2) N개 중 중복을 허용하지 않고 순서 있게 나열
ex) N과M (1)
시간복잡도 : $O(N!/(N-M)!)$
공간복잡도 : O(M)
3) N개 중 중복을 허용해서 M개를 고르기
ex) N과M (4)
시간복잡도 : $O(N^M)$
공간복잡도 : O(M)
4) N개 중 중복을 허용하지 않고 M개를 고르기
ex) N과M (2)
시간복잡도 : $O(N!/(M!(N-M)!))$
공간복잡도 : O(M)
1.3. 완전 탐색 접근
- 고를 수 있는 값의 종류 파악하기
- 중복을 허용하는 지
- 순서가 중요한 지
