알고리즘 완전탐색(Exhaustive search)이란
완전탐색이란?
완전탐색이란 가능한 모든 경우의 수 를 모두 찾는 방법이다. 이러한 방법은 무식한 한다는 의미로 ‘Brute Force’라고도 이름이 불린다.
완전탐색은 직관적이어서 이해하기 쉽고, 문제에 대한 결과값이 정확하게 얻을 수 있다 는 점에서 가장 확실하고 기초적인 문제 풀이 방법이다.
알고리즘 문제를 풀때에는 기본적으로 두가지를 생각하고 들어간다.
- 해당 알고리즘이 적절한가> -> 문제를 풀 수 있는 방법인가
- 효율적인가? -> 제한된 시간이 안에 알고리즘이 동작하는가
1번의 경우에서의 완전탐색은 가능한 모든 경우의 수를 확인하여 정확한 답은 얻어 낼 수 있다. 반면에 2번 측면에서는 문제와 주어진 조건에 따라 제한된 시간안에 결과값을 도출할 수 없을 수 있다.
완전탐색은 가장 기초적으로 알고리즘 문제를 푸는 방식중 하나이지만 완전탐색을 사용할때는 문제를 잘 파악하여 적용시킬 수 있는지 확인하는것이 중요하다.
완전탐색 기법들
완전탐색은 그 자체로 알고리즘보단 문제 풀이 방법이기 때문에 완전탐색을 구현하기 위한 여러가지 방법들이 존재한다. 주로 이용하는 방법은 아래와 같다.
- Brute-Force
- 비트마스크(Bitmask)
- 재귀함수(Recursion)
- 순열(Permutation)
- DFS/BFS
Brute-Force
단순 Brute-Force는 for문 또는 if문을 사용하여 가능한 모든 경우의 수를 확인하여 답을 구하는 방법이다. 이 방법은 가장 기초적인 문제에서 사용이되거나, 전체의 문제에서 일부분에서만 사용된다. 코딩 테스트에서는 거의 이 방법만으로 푸는 문제는 자주등장하지 않는다.
비트마스크(Bitmask)
비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진 표현을 자료 구조로 사용하는 기법을 말한다.
이진수는 1과 0을 이용하여 하나의 비트에서 사용할 수 있는 가짓수는 2가지이다. 이러한 방식으로 어떤 비트가 1이면 “존재한다” 0이면 “존재하지 않는다”라고 말할 수 있다.
재귀함수(Recursion)
재귀함수란 어떠한 함수에서 자신을 다시 호출하여 작업을하는 방식이다. 재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 함수 안에 반드시 종료 구간 을 정해주어야 합니다.
순열(Permutation)
완전 탐색의 대표적인 유형으로. 순열은 순서에 상관있게 선택하는 혹은 나열하는 것을 말한다. N개의 원소가 주어졌을때 순열의 수는 N!개이다.
ex)[1,2,3]이라는 배열이 주어졌을때, 모든 경우의 수
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 총 6개. -> 3!의 값과 동일한 개수이다
DFS/BFS
약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제와 그래프를 탐색할때 사용하는 알고리즘이다.
댓글남기기