브루트 포스(brute force) 기법

브루트 포스(brute force)

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

• 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
• 선형 구조(저장되는 자료의 전후관계가 1:1 )를 전체적으로 탐색하는 순차탐색,
• 비선형 구조(데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프)) 전체를 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

 

     *너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊음

 

문제해결 방법

1.  주어진 문제를 선형 구조로 구조화한다.
2.  구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
3.  구성된 해를 정리한다.

 

예제 및 알고리즘

1. 10의 약수의 합을 구하기

10의 약수가 될 수 있는 모든 자연수를 구조화 하자.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 자료를 선형으로 구성하였다.

 

구조화된 자료가 선형 구조이므로 순차 탐색을 활용하여 첫 번째 원소부터 마지막 원소까지 탐색한다.

탐색하면서 10의 약수가 되는 값만 남겨두고 10의 약수가 될 수 없는 값을 배제한다.

10의 약수는 10을 현재 원소로 나누어떨어지면 그 원소는 10의 약수이다.

위의 과정을 거치면 집합은 다음과 같이 정리된다.

{1, 2, 5, 10}

 

마지막으로 탐색결과를 정리하여 최종 해를 구한다.

1 + 2 + 5 + 10 = 18

 

너비 우선 탐색(BFS, Breadth-first search)

•  그래프에서 완전탐색 방법 중 하나
•  탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향으로 탐색을 진행해 나가는 방식

 

 

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 한다.
• 해가 존재하지 않는다면 유한(finite) 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
•  무한(infinite) 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.