※ 배워가고 있는 학생입니다. 틀린 부분에 대한 댓글 환영입니다 😊
1) '브루트 포스'란? (완전탐색이란?)
Brute: 무식한, 짐승같은
Force: 힘
'무식한 힘', 즉 말그대로 무식하게 모든 경우의 수를 일일이 다 계산하면서 답을 찾아내는 알고리즘이다.
무식하게 문제를 접근하니 틀릴 일이 없다는 장점이 있지만, 시간복잡도가 엄청나게 커진다는 단점이 있다.
가령, 1부터 100까지의 합을 구하는 문제가 있다고 치자.
다양한 방법이 있겠지만, 브루트 포스는 그냥 1부터 1+2=3, 3+3=6, 6+4=10...
이런 식으로 100까지 더해갈 것이다.
100은 비교적 작은 숫자이므로, 시간 복잡도가 그리 크지 않을 수 있지만
만약 100억개의 수를 더한다고 치면 시간복잡도는 엄청나게 늘어나고 만다.
즉, 숫자가 커지면 커질수록 시간복잡도가 상상을 초월할 정도로 늘어난다!
2) 종류
브루트 포스 알고리즘은 선형구조를 탐색하느냐, 비선형구조를 탐색하느냐에 따라 적절한 방법을 이용해서 풀면 된다.
선형구조
- 순차 탐색
비선형 구조
-너비 우선 탐색(BFS, Breadth First Search)
-깊이 우선 탐색(DFS, Depth First Search)
BFS와 DFS는 각각의 알고리즘만 해도 말할 내용이 많으니 여기에서는 선형구조만을 다루겠다!
(위에서 말하지 않는 것은 따로 정리해놓을테니, 카테고리를 참고해주면 좋겠다😉)
순차탐색
풀이 방법
1) 주어진 문제를 선형 구조로 구조화한다.
2) 구조화된 자료를 적절한 방법으로 해를 구성할 때까지 탐색한다.
3) 해를 정리한다.
해당 탐색의 예제는 아래 참고자료를 참고하길 바란다.
3) 참고자료
728x90