[알고리즘/완전 탐색] 기본 완전 탐색 알고리즘

집중맞은 도둑력·2024년 2월 19일

완전탐색

알고리즘

목록 보기

3/15

0. 🔖 목차

완전 탐색 알고리즘 개요
복잡도
사용처
3-1. 순열
3-2. 조합
3-3. 부분집합

1. 완전 탐색 알고리즘 개요

완전 탐색(Exhaustive Search) 알고리즘은 모든 가능한 해를 시도해보는 방식으로, 주어진 문제에 대한 모든 경우의 수를 탐색하여 해를 찾는 알고리즘이다.

간단하고 직관적이지만, 입력 크기가 큰 경우에는 계산 시간이 급격하게 증가하여 효율성이 낮아지는 단점이 있다.

브루트 포스(Brute Force) 알고리즘이라고도 불리는데 브루트(Brute)는 짐승이라는 뜻이다. 말 그대로 짐승처럼 무식하게 모든 경우를 확인하는 방법이라 붙여진 이름인듯

아래와 같은 특징이 있다.

모든 가능한 경우를 확인: 완전 탐색은 문제의 해가 될만한 모든 경우를 하나씩 확인하며 해를 찾는다. 따라서 반드시 정답을 구할 수 있다.

간결하고 이해하기 쉽다: 구현이 간단하며, 알고리즘이 직관적이다.

효율성이 낮음: 경우의 수가 많아질수록 계산 비용이 증가한다.

2. 완전 탐색 알고리즘의 복잡도

완전 탐색 알고리즘이라는게 특정한 하나의 알고리즘이라기 보단 알고리즘 설계 체계에 가깝다.

따라서 어떤 알고리즘이냐에 따라 복잡도는 다르다.

다음에 나올 내용을 사용처라고 적어놓기는 했지만 사실상 각각 완전 탐색 체계를 기반으로 설계된 알고리즘이라고 생각하면 되며, 각 알고리즘마다 복잡도를 표기하였다.

3. 사용처

3-1. 순열

~~고딩 이후로 순열과 조합을 다시 공부하리라고는 상상도 못했네~~

순열의 정의

순열은 이름 그대로 순서대로 나열시키는 것을 의미한다.

영어로는 Permutation이라고 하며 이때문에 순열을 기호로 나타낼 때 $P$ 라고 표기한다.

순열은 기호로 $_nP_{r}$ 와 같이 사용하며,
이는 $n$ 개의 요소 중 $r$ 개를 뽑아 순서대로 나열하는 경우의 수와 동일한 뜻이다.

가령 동서남북 방향으로 딱 한 번 씩 이동 가능한 사람이 2번 움직였을 때 이 사람의 경로를 모두 구하라고 하면 $_4P_2$ 와 같다.

실제로 경로를 모두 구해보자.

('동', '서')
('동', '남')
('동', '북')
('서', '동')
('서', '남')
('서', '북')
('남', '동')
('남', '서')
('남', '북')
('북', '동')
('북', '서')
('북', '남')

총 12개의 경우의 수가 나온 것을 확인할 수 있으며 이는 $_4P_2=12$ 이라는 뜻이다.
참고로 여기서 중복을 허용한다면 이는 중복순열이라고 하며 기호로는 $_4Π_2$ 로 적힌다.

눈치챘을지 모르겠지만 방금 한 행동이 완전 탐색이다. 위처럼 모든 경우의 수를 나열하여 결과를 구했기 때문이다.

순열의 시간 복잡도

$_nP_r=n!/(n-r)!=n(n-1)(n-2)...(n-r+1)$

위는 순열 공식이다. 보통 알고리즘에서 순열이라 함은 $r=n$ 인 경우, 즉 모든 데이터를 나열할 수 있는 경우의 수를 구하기 때문에

$_nP_n=n!/(n-n)!=n!/(0)!=n!$

라고 생각하면 된다. 따라서 시간 복잡도는 $n!$ 이다.

$_nP_4=n!/(n-4)!=n(n-1)(n-2)(n-3)$

위 수식 처럼 $r$ 의 값이 고정된 경우가 있을 수 있다.("n명의 사람들 중 4명을 뽑아 줄세우는 모든 경우의 수를 구하시오" 등등)이때 위 수식의 최고차항은 $n^4$ 이 된다.

빅오 표기법의 수학적 의미에서 설명했듯 빅-오 표기법을 작성할 땐 증가율이 높거나 같은 $g(n)$ 을 사용해도 된다고 했다. 따라서 이 경우에는 증가율이 같은 $O(n^4)$ 이라고 표현해도 아무 문제가 없다. 최악의 경우에서도 $n^4$ 의 증가율을 보이기 때문.

알고리즘으로 구현하기

순열은 어떻게 구현하면 좋을까? 막연하게 생각해보자.

위치 바꾸기(Swap)를 이용한 구현
1. 공을 아무렇게나 전부 배치
2. 특정 두 공의 위치를 바꾸는 모든 경우의 수를 시도 후 기록
갑자기 무슨 이상한 소리냐고 생각할 수 있는데 이렇게 생각해보자

위 그림처럼 숫자가 써진 퍼즐 매트가 있다. 알고리즘을 모르는 어떤 아이가 저 퍼즐 매트의 모든 나열 가능한 경우의 수를 구하고자 한다면 아래처럼 할 것이다.
1. 저 퍼즐 중 하나와 다른 하나를 떼서 서로 위치를 바꾸고 기록
2. 또 하나와 다른 하나를 떼서 서로 위치를 바꾸고 기록
3. 또 하나와 다른 하나를 떼서 서로 위치를 바꾸고 기록
4. ...
아이의 시간과 의지력과 기억력만 충분하다면 언젠간 정답을 구하기 마련이다. 따라서 두 퍼즐의 위치를 바꾸는 모든 경우의 수를 시도한다면 모든 나열 가능한 경우의 수를 구할 수 있는 것이다.

다행이도 컴퓨터는 위에서 예시로 들었던 아이처럼 완전 탐색을 할만한 시간과 의지력과 기억력이 충분하다.

알고리즘은 아래와 같다.

Swap을 통해 구현한 순열의 알고리즘

result = []
arr = [1, 2, 3]

def permute(arr, start, end):
    if start == end:
        result.append(arr.copy()) # 기록
    else:
        for i in range(start, end + 1):
            # 위치 바꾸기
            arr[start], arr[i] = arr[i], arr[start]
            # 재귀 호출
            permute(arr, start + 1, end)
            # 원상 복구
            arr[start], arr[i] = arr[i], arr[start]

permute(arr, 0, len(arr) - 1)

print(result)

처음 gif는 위 코드가 실행되면서 생기는 arr의 변화를 순서대로(재귀 감안) 나타낸 gif다. 재귀 함수로 들어갈 때마다 어두워지도록 그렸으니 참고하면 된다.

순열의 시간 복잡도 체감

위에서 순열의 시간 복잡도는 $n!$ 이라고 했다. 실제로 그럴까?

permute는 Swap을 통해 구현한 순열 알고리즘 함수이다. $n$ 이 3~13일때의 소요 시간을 구한 결과는 Output에서 볼 수 있다.(3~6은 시간이 너무 짧아서 출력되지 않았다)

만약 정말 순열이 $n!$ 의 증가율을 따른다면 $f(x)=kx!$ 에서 $k$ 를 적절히 조절한다면 데이터 포인트들이 다 $f(x)$ 위에 있어야만 한다.

실제로 $k=10^{-6}$ 일 때 얼추 맞는것을 보니 증가율을 $n!$ 이라고 추정할 수 있겠다.

물론 저정도 데이터 포인트로 추정을 한다는게 웃기긴 하지만 n=12부터는 내 컴퓨터가 비명을 질러서 값을 구할 수 없었다. 나열할 데이터의 수가 12개 이상이라면 순열 알고리즘을 사용하면 안되겠다는 교훈까지 얻었다.

3-2. 조합

조합의 정의

조합이란, 주어진 집합에서 몇 개의 원소를 순서 상관 없이 뽑아내는 거야

영어로는 Combination이라고 하며 이때문에 조합을 기호로 나타낼 때 $C$ 라고 표기한다.

조합은 기호로 $_nC_{r}$ 와 같이 사용하며,
이는 $n$ 개의 요소 중 $r$ 개를 뽑아 순서에 상관없이 조합하는 경우의 수와 동일한 뜻이다.

순열 때 예를 들었던 동서남북 방향으로 딱 한 번 씩 이동 가능한 사람이 2번 움직였을 때를 생각해보자 이 사람의 경로의 조합을 구하라고 하면 $_4C_2$ 와 같다.

실제로 경로의 조합을 모두 구해보자.

('동', '서')
('동', '남')
('동', '북')
('서', '남')
('서', '북')
('남', '북')

총 6개의 경우의 수가 나온 것을 확인할 수 있으며 이는 $_4C_2=6$ 이라는 뜻이다.
참고로 여기서 중복을 허용한다면 이는 중복조합이라고 하며 기호로는 $_4H_2$ 로 적힌다.

순열은 n개의 요소에서 r개를 "뽑아서" 순서대로 나열하는 것이다.
조합은 순열에서 뽑아놓고 나열하지 않는 것이라고 생각해도 된다.

순열계산하려고 $n$ 개에서 $r$ 개를 뽑은 경우의 수를 $A$ 라고 하면 이 $r$ 개를 배치하기 위한 경우의 수는 $r!$ 이다. 따라서 순열의 경우의 수는 $Ar!=_nP_r=n!/(n-r)!$ 이라는 뜻인데 여기서 조합은 $A$ 에 해당한다. 따라서 양변에 $r!$ 을 나누면 쉽게 구할 수 있다.

$_nC_r=n!/(r!(n-r)!)$

조합의 특징은 아래와 같다

$_nC_r=_nC_{n-r}$
- 100개중 99개를 선택하라는건 100개중 선택하지 않을 1개를 찾으라는 것과 같음
$_nC_0=_nC_{n}=1$
- 100개중 100개를 선택 = 100개중 아무것도 선택X => 경우의 수는 1개
$_nC_r=_{n-1}C_{r}+_{n-1}C_{r-1}$
- 조합의 점화식, 조합의 점화식은 파스칼의 삼각형의 성질을 띔

3번의 특징을 좀 더 직관적으로 표현한 그림이다. 그리고 이를 활용해서 알고리즘을 구현할 수 있다.

앞선 그림에서 n이 4인 경우를 생각해보면 위 그림과 같다.

1부터 4까지의 모든 조합을 구하는 경우를 위 그림처럼 트리를 통해 이동하다보면 크게 두 가지 경우에 끝이난다.

더 선택 할 게 없어서( $r=0$ )
더 선택 안 할 게 없어서( $n=r$ )

저런 조합 삼각형(?)의 특성상 왼쪽 대각으로 내려가면 $n$ 과 $r$ 이 감소, 오른쪽 대각으로 내려가면 $n$ 만 감소하기 때문에 1번의 경우는 왼쪽 대각으로, 2번의 경우는 오른쪽 대각으로 모여있는 걸 확인할 수 있다( $r$ 은 $n$ 보다 항상 작다).

따라서 재귀호출로 구현하며 종료 조건을 위의 두 경우로 설정하면 쉽게 구현 가능하다.

알고리즘으로 구현하기

def combination(arr, r):

    result = []

    def comb(arr, r, c=[]):
        if r == 0: 
            result.append(c)
        elif len(arr) == r: 
            result.append([*c, *arr[:]])
        else:
            comb(arr[1:], r-1, [*c,arr[0]])
            comb(arr[1:], r, c)

    comb(arr,r)

    return result
        
arr = [1,2,3,4,5,6,7,8,9,10]

print(len(combination(arr, 5)))

3-3. 부분집합

알고리즘으로 구현하기

재귀적 접근법
기본 아이디어는 하나의 원소를 선택하고, 선택한 원소를 포함하는 경우와 포함하지 않는 경우로 나누어 부분집합을 구하는 것. 위의 조합을 구하는 알고리즘에서 종료 조건을 타깃 집합이 공집합이 될 때까지 분기를 나누고 공집합이 되면 지금까지 선택된 집합을 저장.

def subset(arr):

    result = []

    def sub(arr, c=[]):
        if len(arr) == 0:
            result.append(c)
            return
        else:
            sub(arr[1:], [*c, arr[0]])
            sub(arr[1:], c)

    sub(arr)

    return result

arr = [1, 2, 3, 4]

print(subset(arr))

비트마스킹 방법
n개의 원소를 가진 집합의 부분집합을 표현하기 위해 n비트의 이진수로 모든 경우의 수를 나타낸다.

def subset_mask(arr):
    result = []
    n = len(arr)
    for i in range(2**n):
        bit = bin(i).split('b')[-1].zfill(n)
        mask = [int(b) for b in bit[::-1]]
        res = [arr[idx] for (idx,m) in enumerate(mask) if m]
        result.append(res)
    
    return result

arr = [1,2,3]

print(subset_mask(arr))