배운내용

완전탐색을 써야하는 경우

1. 주어진 입력의 범위가 작아 가능한 모든 해를 찾는 시간이 적게 들 때

코딩테스트의 문제는 대체로 시간복잡도가 10^8이내인 경우 통과가 됩니다. 그렇기에 입력의 범위가 100과 같이 작은 경우 완전 탐색으로 걸리는 시간복잡도가 O(n^2)이라면 해당 방법은 10^4의 시간복잡도를 갖기에 통과가 될 것입니다. 이와 같이 주어진 입력의 범위가 작아 완전 탐색의 시간복잡도 또한 낮아지는 경우 완전 탐색으로 빠르게 구현하여 문제를 해결할 수 있습니다.

즉, 시간복잡도를 계산하고 될거같다 싶으면 일일이 다 하면 됩니다. 반복문이 몇개든, 비효율적인 풀이같아 보여도 상관 없이 풀이를 작성해나가면 됩니다._

2. 우선적으로 답을 구하고 그 과정을 최적화하여 시간을 줄이고 싶을 때

주어진 입력의 범위가 커서 완전 탐색으로는 시간 제한을 맞추지 못하는 문제에도 우선 완전탐색을 적용시키는 방법을 고려할 수 있습니다. 완전 탐색은 앞서 설명했듯이 문제를 푸는 가장 기초적인 방법입니다. 그렇기에 완전 탐색을 우선 구현한 후 해당 방법을 개선해 나감으로써 시간 제한을 맞출 수 있습니다. 또한 완전탐색을 통해 진행되는 문제의 과정을 보고 문제의 유형을 파악할 수 있는 등 문제의 명확한 풀이방법을 찾지 못했을 경우에는 우선 완전탐색으로 구현하는 것도 좋은 방법입니다.

- 정렬
- 메모이제이션
- 투포인터
- DP
- 백트래킹
- 이진탐색

References

노씨데브 킬링캠프 강의 자료 활용