[알고리즘] 완전탐색 / 브루트포스, 부분집합, 비트마스크, 순열, 조합, 재귀

 

 완전탐색 ( Complete Search) 이란?

 

 

 

 

완전탐색을 알기 전에 상위 개념인 탐색에 대해 알아야 하는 탐색(Search) 알고리즘은 많은 데이터 중 목적에 맞는 데이터를 찾기 위한 방법이다. 탐색 알고리즘에는 여러 가지 탐색 방법이 존재하는데 완전 탐색은 그중 대표적인 알고리즘 중 하나이다.

 

완전탐색(Complete Search) 은 말그대로 "모든 경우의 수를 검사" 하는 방식으로 브루트포스( Bruth-Force) 알고리즘으로 불리기도 한다. "brute"는 "무식한",  "force"는 "힘"을 의미하는데 무식한 힘 즉 무식하게 전체 모든 경우의 수를 검사하는 알고리즘을 의미한다. 

 

 

 

 

 

 

완전탐색(Complete Search)은 전체 모든 경우의 수를 검사하기 때문에 매우 큰 메모리를 사용하며, 시간이 오래 걸린다는 치명적인 단점을 가지고 있지만, 모든 경우의 수를 검사하여 결과를 도출하기 때문에 목적에 맞는 정확한 결과를 도출할 수 있다는 장점을 가지고 있다. 

 

 

완전탐색(Complete Search)에는 알고리즘으로 풀이하기에 여러 방법들이 존재하는데  Bruth-Force, 부분집합, 비트마스크, 순열, 조합, 재귀, DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등이 있다. 

각 방법들은 "모든 경우의 수를 검사"라는 공통적인 부분이 있지만, 구현방법이 각기 다르고 시간복잡도도 조금씩의 차이가 존재한다. DFS와 BFS는 그래프 개념에도 포함되기도 하기에 추후에 따로 포스팅하도록 하겠다.

 

 

 

 

 알고리즘 개념에 대해 공부를 하다보면 재귀는 분할정복! 또는 재귀는 완전탐색!과 같이 생각하기 쉬운데, 알고리즘 개념 공부에서는 한 알고리즘이 여러 범주에 들어갈 수도 있다는 것을 주의 해야한다. 재귀란 재귀함수로 반복적으로 함수를 호출하는 경우인데 이는 분할정복 또는 이분탐색에서도 사용할 수 있으며, 완전탐색, dp에서도 사용할 수 있는 개념으로 여러 범주에 속한다. 이처럼 한 알고리즘을 공부하기 위해서는 "어떤 개념이 무엇이다."와 같은 방식보다는 알고리즘 = 사용될 수 있는 도구라 생각하며 개념을 잡아나가는 것을 추천한다.

 

 

 

 

 

 

 

완전탐색 사용이 가능한 문제는?

 

 

앞서 완전탐색(Complete Search) 알고리즘의 치명적인 단점으로 시간이 오래 걸린다, 즉 시간복잡도가 크다는 단점을 가지고 있다. 알고리즘 문제의 경우 대부분 시간초과를 해결하기 위해서는 더 적은 시간복잡도의 알고리즘을 선택하여 풀수록 유리하기에 대부분 더 적은 시간복잡도를 가진 알고리즘을 위해 최선의 선택을 한다.

 

그렇다면 완전탐색(Complete Search) 알고리즘은 언제 사용해야 할까?

모든 알고리즘 문제에서는 알고리즘 선택 힌트를 준다. 즉 문제의 힌트를 통해 완전탐색(Complete Search) 알고리즘을 선택할 수 있다.

 

 

  1초 = 10^8

 

컴퓨터에서 10의 8승은 굉장히 많은 것을 의미하고 있다. 언어에 따라 다를 수 있지만 기본적으로 컴퓨터의 10^8번 계산은 1초가 걸린다. 

 

알고리즘 문제를 풀이할 때 입력 조건과 제한시간이 존재한다. 이때 입력 조건 n이 최대 범위가 100이라 하는 경우에 제한시간이 1초라면 대략 시간 복잡도 O(n^3) 풀이가 통과된다. (100*100*100=10^8)

다른 문제의 예시로 입력조건 n이 최대 범위가 10^8승이고 제한시간이 1초인 경우 시간 복잡도 O(n)의 풀이인 알고리즘을 선택해야 풀 수 있는 것이다. 

 

입력 범위와 제한시간에 따라 선택 알고리즘이 달라진다는 것은 당연하게 받아들일 수 있지만,

10^8이 1초라는 사실에 입각하여 입력범위와 제한시간에 따라 가능한 시간복잡도를 알게 된다면 문제에 대한 알고리즘을 명확하게 선택할 수 있게 된다.

 

 

 

 

 

위에서 10^8이 무엇인지 알게 되었다면, 완전탐색 알고리즘이 가능한 문제를 알 수 있게 될 것이다. 완전탐색의 시간 복잡도의 경우 방법에 따라 다르기도 하지만 순열과 같이 오래 걸리는 경우는 O(2^n)과 O(n!)처럼 매우 오래 걸리는 경향이 있다.

하지만 1초는 10^8 임을 알고 있기 때문에 시간복잡도와 제한시간을 비교해 볼 수 있다. 입력조건의 최대범위를 시간복잡도 n에 대입하여 계산하여 제한시간과 비교할 수 있는 것이다. 

이때 완전탐색의 시간복잡도가 제한시간 범위 안에 들어간다면, 완전탐색의 단점인 메모리와 시간이 오래 걸린다는 점은 무시한 채 쉬운 로직과 정확한 목푯값을 알 수 있는 장점을 활용할 수 있는 것이다.

 

 

 

 

 

완전탐색 기법

 

 

Bruth-Force ( 브루트포스)

 

 

단순 브루트 포스 방법은 순차적으로 모든 경우의 수를 검사하는 방법이다.

어떠한 이중 리스트에서 특정 값을 찾아야 하는 경우 순차적으로 이중 for문 등으로 모든 경우를 찾는 예시들이 이에 해당된다. 완전탐색의 기본 방식으로 특정 값을 찾기 위해 전부 검사하는 형식이기에  Bruth-Force ( 브루트포스)라는 용어를 어렵게 느낄 필요는 전혀 없다. 

 

 

 

 

부분집합 /  비트마스크

 

 

arr=[ 2, 4, 6, 8]

 

위와 같은 리스트가 있을 때, 이를 부분집합으로 나타내는 경우 새로운 리스트를 만들어서 subset=[ [ 2, 4], [ 2, 4, 6]]과 같이 나타 낼 수 있다. 

이때 비트 마스크는 위의 2 부분 집합을 [ 2, 4]인 경우 [ 1, 1, 0, 0]으로 나타내고, [ 2, 4, 6]은 [ 1, 1, 1, 0]으로 나타낸다. 위와 같이 비트마스크 기법을 사용하면, 부분집합을 이진수와 같이 표현할 수 있게 되는 것이다.

 

부분집합	2	4	6	8
{ 2}	1	0	0	0
{ 4}	0	1	0	0
{ 2, 4}	1	1	0	0
{ 2, 6}	1	0	1	0
{ 2, 8}	1	0	0	1
{ 4, 6}	0	1	1	0
{ 4, 8}	0	1	0	1
{ 6, 8}	0	0	1	1
{ 2, 4, 6}	1	1	1	0

 

이처럼 모든 부분집합을 비트마스크 기법을 통해 이진수로 표현할 수 있게 된다.

 

 

 

 순열 / 조합

 

 

-순열 

 

 서로 다른 n개의 원소에서 중복 없이 순서를 고려하여 r개를 나열하는 것을 순열이라 한다.

수식으로는 P(n, r) = n! / (n-r)!로 나타낼 수 있다.  전체 집합의 부분집합으로 볼 수 있는데 이로 인해 완전탐색 알고리즘 범주안에 있기도 하며, 시간복잡도는 O(n!)을 가진다.

 

 

파이썬 언어에는 순열과 조합을 쉽게 구현할 수 있는 라이브러리가 존재한다.

itertools라이브러리를 활용하면 간단하게 구현할 수 있다. 

 

permutations( 배열, 부분집합 원소 수)와 같이 사용하며, 해당 리턴값은 list가 아닌 itertools. permutations인 점을 인지한 채로 사용해야 한다.

<class 'itertools.permutations'>

 

• 코드 구현

from itertools import permutations

arr=[ 2, 4, 6, 8, 10]
print(list(permutations(arr,2)))

 

 

 

-조합

 

n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것을 조합이라 한다.

수식으로는  C(n, r) = n! / [(n-r)! * r!]로 나타낼 수 있다. 시간 복잡도는 O(nCr)이며, 순열과 마찬가지로 전체 배열에서의 부분집합을 선택하는 것을 의미하기에 완전탐색에 속한다.

 

 

순열과 마찬가지로 조합도 파이썬에서는 라이브러리로 간단히 구현 가능하다.

 

• 코드 구현

from itertools import combinations

arr=[ 2, 4, 6, 8, 10]
print(list(combinations(arr,2)))

 

 

 

재귀

 

 

재귀적 반복을 통해 모든 경우의 수를 검사하는 방법이다. 대표적인 예시로는 피보나치수열 문제가 있는데 피보나치수열은 어떤 자연수 N은 N-1과 N-2의 합으로 이루어져 있다. 피보나치수열을 파이썬으로 재귀함수로 풀이하면 다음과 같다.

(첫 번째 수를 0, 두 번째 수를 1이라고 한 경우) 

 

• 코드 구현

def fibo(n):
    if n==1:return 0
    elif n==2:return 1

    return fibo(n-1)+fibo(n-2)


print(fibo(10))