모든 문제는 완전 탐색으로 풀 수 있다. 이 방법은 굉장히 단순하고 무식하지만 "답이 무조건 있다"는 강력함이 있다.
예를 들어, 양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾기 위해서는 배열의 첫 요소부터 마지막 요소까지 전부 확인을 한다면 최대 100 번의 탐색 끝에 원하는 값을 찾을 수 있다.
그렇지만, 문제 해결을 할 때엔 기본적으로 두 가지 규칙이 붙는다.
- 첫 번째, 문제를 해결할 수 있는가?
- 두번째, 효율적으로 동작하는가?
완전 탐색은 첫 번째 규칙을 만족시킬 수 있는 강력한 무기이지만, 두 번째 규칙은 만족할 수 없는 경우가 있다.
양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾으시오.
단, 시간 복잡도가 O(N)보다 낮아야 합니다.
이러한 문제가 나왔을 때, 최악의 경우 100 번을 시도해야 하는 완전 탐색은 두 번째 규칙을 만족할 수 없다.
배열을 작은 수에서 큰 수, 혹은 그 반대로 정렬한 후 이분 탐색을 사용하는 방법 등 다른 알고리즘을 사용해야 한다. 그렇기 때문에, 완전 탐색은 문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 완전 탐색 밖에 없다고 판단될 때 적용할 수 있다.
완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다. 완전히 탐색하는 방법에는 Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있다.
Brute Force 예시
우리 집에는 세 명의 아이들이 있다. 아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분한다. 먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고, 좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 한다. 세 아이의 식성은 이렇습니다.
- 첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)
- 둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)
- 셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)
100 개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때, 가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요? (단, 그 주변의 음식은 반찬의 앞, 뒤로 한정한다.)
이 문제는 단순히 100 개의 반찬을 첫째, 둘째, 셋째의 식성에 맞게 하나씩 대입하여 풀 수 있다.
for(let i = 0; i < 100; i++) {
if(첫째 식성) {
if(싫어하는 음식이 앞뒤로 있는가) {
그냥 넘어가자;
}
좋아하는 음식 카운트;
}
if(둘째 식성) {
if(싫어하는 음식이 앞뒤로 있는가) {
그냥 넘어가자;
}
좋아하는 음식 카운트;
}
if(셋째 식성) {
if(싫어하는 음식이 앞뒤로 있는가) {
그냥 넘어가자;
}
좋아하는 음식 카운트;
}
}
return 많이 먹은 아이;각각 몇 가지 음식을 얼마나 먹을 수 있는지 각각 계산한 후, 제일 많이 먹는 아이와 제일 적게 먹는 아이를 파악할 수 있다. 문제를 풀 때, 반복문이 아닌 배열을 전부 순회하는 메서드를 사용한다거나 간결한 코드를 위한 문법을 사용한다고 하더라도 배열을 전부 탐색하여 세 명의 값을 도출한다는 것엔 변함이 없다.
