[이론] 완전 탐색 Brute force

정글 알고리즘 1주차의 주제는 완전 탐색, 이분 탐색, 재귀 함수, 정렬, 시간 복잡도였다. 이 중에서 이번 글에서는 완전 탐색에 대해 정리해보려고 한다.

 

완전 탐색

우선 '완전 탐색'이라는 용어의 개념을 분명하게 밝히고 글을 시작하는 게 좋을 것 같다. 완전 탐색은 어떤 곳에서는 Brute force와 동의어로 쓰이기도 하고 어떤 곳에서는 Brute force의 상위 개념으로 쓰이기도 한다. 완전 탐색 공부를 시작하기도 전에 이 부분에서 잠깐 혼란에 빠져서 조금 헤매고 있었는데 코치님께 여쭤본 결과 개념을 알면 되지 어떤 용어를 사용하는지가 중요한 게 아니라는 답을 주셨다! 이 글에서는 완전 탐색과 Brute force를 같은 개념을 가리키는 용어로 보고자 한다.

 

코치님께서 알려주신 '완전 탐색'의 의미는 다음과 같다.

(1) 답이 될 수 있는 후보들을 생각하기

(2) 후보들을 중복되지 않게 모두 나열하기

(3) 모든 후보들을 하나씩 정답이 되는 조건에 맞는지 테스트하기

 

이 설명을 미루어 볼 때 완전 탐색의 핵심은 답이 될 수 있는 "모든" 후보를 탐색한다는 점이다. 예를 들어, [1, 2, 3, 4, 5, 6, 7, 8, 9] 이와 같은 배열에서 값 '8'을 찾아야 한다고 했을 때 완전 탐색의 경우, 배열의 처음 [0]번 요소(값: 1)부터 마지막 [9]번 요소(값: 10)까지 차례대로 하나씩 "모두" 탐색하며 정답에 해당하는 '8'를 찾는다.

 

완전 탐색과 대조되는 검색 방법으로는 이진 검색이 있다. 똑같이 [1, 2, 3, 4, 5, 6, 7, 8, 9] 배열에서 '8'를 찾아야 한다고 했을 때 이진 탐색의 경우 굳이 모든 요소를 하나씩 탐색하지 않는다. 배열이 오름차순되어 있다는 전제 하에 전체 요소들의 중간값인 [4]번 요소(값: 5)를 정답인 '8'과 비교한다. '8'이 '5'보다 왼쪽에 있는지 오른쪽에 있는지를 판단하여 정답이 될수 있는 후보의 범위를 절반으로 줄인다.

 

완전 탐색은 이진 검색과 비교해 봤을 때 한눈에 봐도 성능이 좋아보이지 않는다. 이진 검색보다 검색 범위가 더 넓기 때문이다. 두 검색법의 시간 복잡도를 비교하면 다음과 같다.

 

시간 복잡도 비교

• 선형 검색: O(n)
• 이진 검색: O(log n)

완전 탐색을 했을 때 최악의 경우는 배열에서 찾고자 하는 값이 가장 마지막 요소에 있을 때와 같은 경우이다. 이런 경우 배열 n개의 요소를 모두 탐색하게 되므로 시간 복잡도는 빅 오 표기법으로 O(n)이 된다.

이진 검색을 했을 때 최악의 경우는 배열에서 찾고자 하는 값을 찾기까지 배열을 더 이상 나눌 수 없을 때까지 이등분을 하게 되는 경우이다. 이 경우 배열 n개의 요소를 2로 가능한 끝까지 나누게 되므로 2^k = n 번 수식에서 k번 수행을 하게 된다. 이때의 시간 복잡도를 빅 오 표기법으로 표현하면 O(log n)이 된다.

 

그럼에도 완전 탐색은 가장 기본이 되는 알고리즘으로 완전 탐색을 잘 할 줄 알아야 이를 응용하여 좋은 알고리즘을 만들 수 있다고 한다. 어떤 문제가 주어지든 완전 탐색 코드를 잘 짤 수 있도록 연습하자!