[알고리즘 ] 완전탐색

완전탐색이란?

완전탐색은 말그대로 모든 경우의 수를 다 찾아서 정답을 찾아가는 방법이다.
말그대로 쥐잡듯이 잡아서 정답을 찾아내는..

이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다.

1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 )
2. 효율적으로 동작하는가?

위 2가지의 규칙에 대해서 생각할 때, 1번은 만족될 수 있는 가장 확실한 방법이겠으나 대부분의 경우 2번의 경우 때문에 이 방법이 사용되는데는 제한이 따른다.

그래서 완전탐색기법으로 문제해결을 할때는 해당문제의 제대로 된 파악이 필요하다.

2. 완전탐색 기법을 활용하는 방법

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법