완전탐색

오늘은 완전 탐색 알고리즘에 대해 알아보자

 

완전탐색 알고리즘이란?

완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다.

즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다.

이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부른다.

직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다.

오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서

암호 해독법 중 가장 확실하고 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는것이라 정확도가 100%가 항상

보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다.

 

예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자.

이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것이다.

 

 

완전탐색에서도 여러가지가 있지만, 이 글은 단순 Brute-Force만을 다룬다.

 

 

쉬운 예제로는 rook문제가 있다.

https://kimtaesoo99.tistory.com/50?category=1046078 

*완전 탐색* rook(java,알고리즘)

위의 문제는 킹과 룩, 그리고 장애물로 이루어진 체스판 위에서 킹이 룩에게 잡힐 가능성이 있는지 없는지에 대해 판단하는 것이다.

이 문제가 Brute-Force인 이유는 룩을 기준으로 룩이 이동가능한 모든 경우를 탐색하기 때문이다. 이외에도 룩을 기준으로 하는 것이 아닌 킹을 중심으로 가로와 세로에 룩이 있는지 판단하는 방법도 있다.

 

 

다른 문제로는 baseballgame문제가 있다.

https://kimtaesoo99.tistory.com/54?category=1046078 

*완전 탐색* baseballgame

위의 문제는 여러가지 케이스가 주어졌을때, 그에 맞는 수를 찾아내는 것이다. 이때 123~987까지 모든 수를 대입하면서 조건에 부합하는지 확인해야 하기때문에 Brute-Force를 사용하여 풀면된다. 

 

 

 

이외에도 여러가지 문제가 있는데 직접 풀어보고 풀이를 비교해보는 것도 좋은 공부방법 중 하나이다.