완전탐색이란
모든 경우를 탐색하는 방법.
부분점수를 얻기 좋으나 시간 복잡도가 일반적으로 높은 편.
완전탐색 문제를 접근할 땐
- 고를 수 있는 값의 종류 파악
- 중복을 허용하는지
- 순서를 중요시 하는지
위 세가지를 파악해자.
문제 유형
완전탐색 문제는 크게 4가지로 나눌 수 있다.
- N개에서 중복 허용해서 M개를 순서 있게 나열하기
- N개에서 중복 허용하지 않고 M개를 순서 있게 나열하기
- N개에서 중복 허용해서 M개를 순서 없이 고르기
- N개에서 중복 허용하지 않고 M개를 순서 없이 고르기.
즉 완전탐색 문제는 두 개의 양의 정수를 구하고, 배열이나 리스트에 나열하는 방법의 개수를 묻는 방식으로 푼다.
복잡도 파악
완전 탐색은
위 유형마다 시간 복잡도 / 공간 복잡도를 정리해보자
- 중복허용, 순서중요 : O(N^M) , O(M)
- 중복불허, 순서중요 :O(N!/(N-M)!), O(M)
- 중복허용, 순서불허 : O(N^M), O(M)
- 중복불허, 순서불허 : O(N!/M!(N-M)!), O(M)
대체로, 순서를 신경쓰는 경우가 더 복잡하다.