완전탐색 (Brute-Force)

| 완전탐색

완전탐색 (Brute-Force)는 알고리즘이라고 지칭하기는 어렵지만 문제를 해결할 때 필요한 순간이 오며

간단하지만 풀이에는 난이도가 있는 알고리즘이다.

모든 경우의 수를 전부 탐색하기에 무식한 풀이 기법이라는 소리도 있다.

유튜브에서 본 설명을 들었을 때 10억이 든 금고의 암호를 푼다고 한다면

4자리의 암호를 모든 경우에서 조합하여 금고의 암호를 풀것이다.

0000 -> 0001 -> 0002 이런 순서로 정답이 나올때 까지 시도를 할것이다.

여기서 느껴지는점은 완전탐색의 시간복잡도는 N의 크기에 따라 가진다.
이 방법은 간단하고 직관적이지만 경우의 수가 많아질수록 계산 시간이 급격하게 증가할 수 있다

 

| 완전탐색의 과정

1. 모든 경우의 수를 생성

2. 경우의 수 계산

3. 조건 충족 확인

 

| 완전탐색을 구현하는 방법

완전탐색을 구현하는 방법은 총 5가지가 있으며 상황에 따라 사용하면 된다.

 

- Brute Force

가장 무식한 방법이다.

모든 경우의 수를 if-else 또는 switch문 등 조건문을 사용하여 모든 조건을 비교하는 방식이다.

가장 정확한 방법일수 있지만 조건문 중 하나만 잘못되어도 테스트케이스를 통과할 수 없으며

코드의 가독성이 많이 떨어질 수 있다.

 

- Bitmask

컴퓨터의 연산을 이용한 방식이며 부분집합을 구할때 주로 사용된다.

비트마스크를 사용하면 코드가 간결해지고 연산 속도를 향상 시킬 수 있다.

또한 메모리의 사용량이 더 작다.

 

- Recurtion (재귀)

조건에 부합할 때 까지 재귀함수를 실행하는 방식이다.

주로 원소가 포함되는지 여부를 따질때 사용된다.

메모리 사용량을 예민하게 고민하고 작성하여야 한다.

그 이유는 n의 갯수가 많을 때 함수는 계속해서 콜스택에 쌓일것이며 자칫하다가는 테스트케이스에 실패할 수 있다.

 

- 순열

완전탐색에서 가장 대표적으로 사용되는 기법이다.

순열이란 원소의 순서를 고려해서 나열하는 것을 의미한다.

n개의 원소에 대한 순열은 n!(팩토리얼) 개의 경우의 수를 가지며 1부터 n까지의 모든 자연수의 곱을 의미한다.

예를 들어 {1,2,3} 의 순열은 {1,2,3},  {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 이렇게 나열 할 수 있다.

순열은 조합과 달리 순서가 중요하므로 같은 원소를 포함하더라도 순서가 다르면 순열로 간주한다.

 

- BFS/DFS

BFS/DFS는 설명하기에 조금 길기때문에 나중에 따로 정리를 할것이다.

5가지의 방법중에서 가장 난이도가 높다.

주로 길을 찾는 문제에서 사용된다.

하지만 길을 찾다가 장애물이 있을때는 완전탐색으로 장애물 먼저 해결한 뒤 BFS/DFS로 문제를 해결한다.

 

| 완전탐색 구현

 

프로그래머스 [소수찾기]

 

나는 재귀함수로 순열을 생성해서 배열에 추가하는 방식을 선택했다.

완전탐색 문제는 선택지가 많은 만큼 어떠한 해결방법을 선택하여 메모리와 시간을 고려할지가 어려운 방법인것같다.