BruteForce ( 완전 탐색 )
완전 탐색이란 ?
Brute : 무식한
Force: 힘
말 그대로 모든 경우의 수를 탐색하여 해를 찾아내는 방법이다.
구현하기 쉽고 완벽한 해를 찾을 수 있다는 장점이 있지만
실행시간, 시간복잡도 면에서 매우 비효율적이라는 단점이 존재한다.
브루트 포스의 종류에는 자료구조에 따라 탐색하는 방법과 순열/조합, 비트마스크 등이 있다.
Exhaustive Search 알고리즘이라고도 한다.
자료구조에 따라 탐색
자료구조에 따라 탐색하는 방법에서 자료구조는
선형구조와 비선형구조가 있다.
선형구조란 ?
배열, 큐, 스택, 연결리스트 등의 데이터가 연속적으로 하나의 선 또는 원처럼 이어진 구조를 의미한다.
비선형구조란 ?
트리와 그래프 처럼 데이터가 연속적으로 이어져 있지 않은 구조를 의미한다.
예를 들어 트리를 살펴보면 하나의 데이터 뒤에 오는 데이터들이 하나의 연속적인 구조가 아닌 여러개가 올 수 있다.
일반적으로 선형구조는 순차탐색 방법이 있고
비선형 구조에는 DFS, BFS 가 있다.
선형 구조의 순차탐색
선형구조의 모든 데이터를 순차적으로 탐색하여 해를 찾는 방법이다.
보통 반복/조건문을 활용하여 탐색하고 해를 찾는다.
단순 Brute-Force 라고도 한다.
예를 들어 1~10까지의 배열에서 10의 약수를 찾는다고 하면
반복문을 활용하여 10에서 1~10까지의 모든 원소를 나눠보는 방법으로 해를 구할 수 있다.
이때 모든 원소를 순차적으로 탐색하게 된다.
코드로 보면
let list: [Int] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
var result: [Int] = []
for item in list {
if 10 % item == 0 {
result.append(item)
}
}위와 같은 방식으로 구할 수 있다.
순차탐색의 시간복잡도는
O(n) 이다.
최악의 경우 배열의 개수 n 만큼의 순회하기 때문이다.
순차탐색의 경우 반복/조건문을 사용하기 때문에 구하기 쉽고 단순하지만 그만큼 자원( 시간 복잡도와 같은 )의 제약을 많이 받는다.
