[알고리즘] 완전탐색(Brute-Force Search / Exhaustive Search) 기법

zzzzsb·2022년 7월 23일

BFS DFS algorithm bitmask brute force permutation recursive 비트마스크 순열 알고리즘 완전탐색 재귀

자료구조&알고리즘

목록 보기

5/8

완전 탐색이란?

컴퓨터의 계산 능력을 이용해 가능한 모든 경우의 수를 체크하여 답을 찾는 방법을 의미한다.

예를 들어, 4자리 암호로 구성된 자물쇠가 있다고 생각해보자. 자물쇠의 암호를 전혀 알지 못할때, 시도할 수 있는 가장 확실한 방법은 0000~9999까지 모든 조합을 시도해 보는 것이다.
(최대 10000번의 시도로 해결 가능)

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

사용된 알고리즘이 적절한가? (문제를 해결할 수 있는가)

효율적으로 동작하는가?

위 2가지 규칙을 생각했을 때, 완전탐색 알고리즘은 1번 규칙에서는 가장 확실한 방법이 될것이다.
(가능한 모든 경우를 구해 답을 찾기 때문에, 답을 찾지 못하는 경우가 없으므로)
하지만 2번 규칙 때문에 완전탐색 알고리즘에는 제약이 따른다. 모든 경우의 수를 탐색하기 때문에, 답이 될 수 있는 경우의 수가 너무 많으면 제한된 시간 내에 문제를 해결하지 못하고 시간 초과가 되기 떄문이다.

예시로 10개의 정수 수열에서 두 원소를 선택해, 더한 합의 최댓값을 구하는 문제를 생각해보자.
이 예시에서 완전 탐색을 이용한다면 10개의 원소에서 두 원소를 고르는 모든 경우를 다 고려하게 될것이다. 즉, 10C2=45가지의 경우를 모두 구한 후 나온 합 중 최댓값을 출력할 것이다.
이 예시에서는 원소의 개수가 10개로, 모든 경우의 수가 45개 밖에 되지 않기 때문에 주어진 시간내에 충분히 해결이 가능하다.

하지만, 만약 원소의 개수가 10만개라면?
총 경우의 수는 약 50억개로, 제한된 시간 내에 모든 경우를 구할수 없게 된다.

이처럼 완전탐색은 답이 될 수 있는 경우의 수가 너무 많은 경우에는 사용하기 어렵기 때문에,
주어진 문제를 잘 파악하고 신중하게 사용해야 한다.

완전 탐색 기법

완전 탐색은 가능한 모든 경우의 수를 찾는 것이기 때문에 그 자체로 알고리즘이라 부르긴 어렵고, 문제를 푸는 "방법" 정도라고 생각하면 된다. 그렇기에 완전 탐색을 위해 여러 알고리즘이 사용되고 있다.
주로 사용되는 알고리즘은 아래와 같다.

Brute-Force 기법: 반복/조건문을 활용해 모든 경우의 수를 테스트

비트마스크(Bitmask): 2진수 표현 기법을 활용

재귀(Recursive): 재귀 함수 활용

순열(Permutation): n개의 원소 중 r개의 원소를 중복 허용 없이 나열

BFS/DFS

1. Brute-Force 기법

brute: 무식한, force: 힘
단어의 뜻에서만 보아도 알 수 있듯이 무식하게, 가능한 모든 경우의 수를 탐색하며 답을 찾는 방식이다.
for나 while등 반복문과 if 조건문 등을 활용해 모든 경우의 수를 만들어 답을 구한다.
위의 자물쇠 암호를 찾는 예시처럼 모든 경우를 다 찾는 경우에 사용한다.

2. 비트마스크(Bitmask)

비트(bit) 연산을 이용하는 방식이다.
완전 탐색에서 비트마스크는 모든 경우의 수가 각 원소에 포함되는 경우와 포함되지 않는 경우 두가지 선택으로 구성되는 경우에 유용하게 사용할 수 있다.

비트 연산의 종류

AND 연산(&) : 둘 다 1이면 1

OR 연산(|) : 둘 중 1개만 1이면 1

NOT 연산(~) : 1이면 0, 0이면 1

XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0

Shift 연산(<<, >>) : A << B라고 한다면 A를 좌측으로 B 비트만큼 미는 것이다.

예시로 원소가 5개인 집합의 모든 부분집합을 구하는 경우를 생각해보자.
어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두가지 경우만 존재한다. 따라서 5자리 이진수 0~31을 이용해 각 원소의 포함 여부를 체크할 수 있다.

위 그림처럼 0~31까지의 각 숫자들이 하나의 부분집합에 1대1로 대응된다.

3. 재귀(Recursive)

재귀 함수를 호출해 자기 자신을 연속적으로 호출해 연산을 진행하는 방법이다. 일반적으로 재귀 함수는 함수를 단순하게 만들어주고, 변수 사용을 줄여주어 프로그램에 오류가 생길 가능성을 줄여준다.

만약 10번의 반복을 해야하는 프로그램에서, 10중 for문을 만드는 것보다는 재귀호출을 10번 하는 것이 코드를 훨씬 간결하고 이해하기 쉽게 만들어 줄것이다. 하지만 재귀 함수 사용시 종료조건을 제대로 명시해 주지 않으면 무한하게 자기 자신이 호출되어 Stackoverflow와 같은 에러를 유발할 수 있으니 함수 설계시 주의해야 한다.

재귀함수의 대표적인 사용 예시로는 피보나치 수열 문제가 있다.
아래 점화식으로 피보나치 수열을 정의할 수 있다.

f(0)=0, f(1)=1, f(n+2)=f(n+1)+f(n)

위의 점화식을 재귀함수로 구현하면, 아래와 같은 코드가 만들어진다.

function f(n) {
	if(n===0) return 0;
	if(n===1) return 1;
    
    return f(n-1) + f(n-2) // 재귀함수 호출
};

4. 순열(Permutation)

순열은 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다. 기호로는 nPr과 같이 나타낸다.
예를들어, 1 2 3의 숫자를 모든 순서에 대해 순열을 만든다면 3!(321)=6가지의 순열을 만들 수 있다.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

이처럼 순열은 N개의 요소를 서로 다른 순열로 나열하는 경우 N!의 경우의 수를 갖기 때문에 N의 크기가 충분히 작을때만 사용할 수 있다.
(N이 11개만 되어도 약 3900만번의 연산 필요, N이 12인 경우 4억을 넘어가는 연산 필요, 즉 N이 10개만 넘어가도 사용하기 어려워진다.)