알고리즘/시작하기
2020. 4. 14.
완전 탐색 (Brute Force)
완전 탐색은 문제를 풀 때, 가능한 모든 경우를 살펴보면서 답을 찾는 방법을 말합니다. 일반적으로 가장 간단하고 쉽게 생각할 수 있는 방법이면서도, 제대로 구현했다면 절대 틀릴 수 없는 방법이기도 합니다. PS에 입문하는 사람들이 문제를 풀 때 많이 하는 실수 중 하나는 입력이 작은 문제에 대해 완전 탐색 풀이를 쓸 생각을 하지 못한다는 것입니다. 예를 들어 \(N\)이 최대 1000이고, 완전 탐색으로 \(O(N^2)\)으로 풀 수 있는 풀이가 있다면, \(O(NlogN)\)이나 \(O(N)\)에 동작하는 더 나은 풀이에 대해 생각할 필요가 없습니다. 물론 개인적인 공부를 위해서라면 충분히 가치가 있겠지만, 만약 목표가 지금 앞에 있는 문제를 푸는 것이라면 의미가 없다는 것을 알아야 합니다. 대회에서는..