재귀 vs 비트마스킹

알고리즘 문제를 풀다 보면 브루트포스 문제들이 자주 나온다.

그중에서도 몇 개를 탐색하는지 정해지지 않고 1개일 때, 2개일 때... N개일 때 전부 탐색해봐야 하는 경우가 있다.

이 때 사용할 수 있는 두 개의 알고리즘을 백준 1182번 문제에 적용하며 비교해 보겠다.

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

재귀

1182번 문제는 주어진 집합(수열)의 모든 부분집합을 구한 뒤 그 합을 계산하여 주어진 값과 비교하는 문제이다.

대표적인 방법인 재귀를 적용시켜보자!

def sol(depth,curr):
    global answer
    if depth == N:
        if curr == S:
            answer += 1
        return
    sol(depth+1,curr+lst[depth])
    sol(depth+1,curr)

재귀의 깊이가 N이 될 때 까지 현재 깊이(인덱스)의 값을 더하는 경우, 더하지 않는 경우로 분기하여 재귀를 진행하는 방식으로 구현하였다.

 

비트마스킹

for i in range(1,pow(2,N)):
    curr = 0
    bit = bin(i)[2:]
    for j in range(0, len(bit)):
        if bit[j] == '1':
            curr+=lst[len(bit)-j-1]
    if curr == S:
        answer+=1

1부터 N까지인 모든 비트를 구하여 비교하는 방식으로 구현하였다.

10진수를 2진수로 바꾸는 bin 메서드를 사용하면 앞에 '0b'가 붙은 스트링이 반환되기 때문에 이를 주의하여 사용해야한다.

 

결과

첫번째가 비트마스킹, 두번째가 재귀

비트마스킹에 비해 재귀가 훨씬 빨랐다!

 

이유는 다음과 같다.

우선 연산 횟수는 두 방식 전부 2^N 번으로 동일하다.

다만 비트마스킹 방법에서는 각 연산마다 비트를 조회하고 값을 더해주는 과정이 있어야하기 때문에 시간이 훨씬 많이 걸리게 된 것이다.

즉 재귀는 O(2^N)의 시간복잡도를 갖고, 비트마스킹은 O(2^N)*N의 시간복잡도를 가지게 된다.

 

항상 시간 복잡도를 고려하여 적절한 알고리즘을 선택하자!