CodingTest/algorithm

부분수열의 합을 구하는 알고리즘 정리 - 완전탐색, 백트래킹, DP, 비트마스크 비교 (Python)

사족보행 개발자 2024. 11. 27. 00:19
728x90

 

부분수열의 합을 구하는 알고리즘: 다양한 접근 방법

부분수열의 합을 구하는 문제는 기본적인 문제 중 하나이다.

주어진 배열에서 가능한 모든 부분수열의 합을 구하거나, 특정 목표 합을 만족하는 부분수열을 찾는 것이 주 목적이다.

이를 해결하기 위해 다양한 알고리즘들이 존재하며, 각각의 장단점이 있다.

 

이번 글에서는 부분수열의 합을 구하는 네 가지 대표적인 알고리즘

- 완전 탐색, 백트래킹, 동적 계획법, 비트마스킹 - 을 정리해 보겠다.

문제 정의

우리가 풀고자 하는 문제는 다음과 같다. 정수 배열 arr이 주어졌을 때, 가능한 모든 부분수열의 합을 계산하거나 특정 조건을 만족하는 부분수열의 합을 찾는 것이다. 예를 들어, 배열 [1, 2, 3]이 주어진다면 가능한 부분수열의 합은 {0, 1, 2, 3, 4, 5, 6}이 될 수 있다. 여기서 합이 특정 값인 경우의 수를 구하거나, 모든 합의 집합을 구하는 문제를 풀어야 할 수도 있다.

1. 완전 탐색 (Brute Force)

완전 탐색은 모든 가능한 부분수열을 생성하고 그 합을 계산하는 가장 직관적인 방법이다.

이 접근 방식은 모든 경우의 수를 살펴보기 때문에 시간복잡도가 On × 2n로 매우 크다.

하지만, 배열의 크기가 작을 때는 가장 단순하게 구현할 수 있는 좋은 방법이다.

from itertools import combinations

def all_subsequence_sums(arr):
    result = set()
    n = len(arr)
    for r in range(n + 1):
        for comb in combinations(arr, r):
            result.add(sum(comb))
    return result

arr = [1, 2, 3]
print(all_subsequence_sums(arr))  # {0, 1, 2, 3, 4, 5, 6}

2. 백트래킹 (Backtracking)

백트래킹은 특정 조건을 만족하지 않는 경우를 가지치기하여 탐색 공간을 줄이는 방법이다.

이 방법은 목표 합이 주어졌을 때 유용하며, 최적의 결과를 찾기 위해서 불필요한 탐색을 줄여 성능을 향상시킬 수 있다.

def count_subsequences_with_sum(arr, target):
    def dfs(index, current_sum):
        if current_sum > target:
            return 0
        if index == len(arr):
            return 1 if current_sum == target else 0
        return dfs(index + 1, current_sum + arr[index]) + dfs(index + 1, current_sum)

    return dfs(0, 0)

arr = [1, 2, 3]
target = 5
print(count_subsequences_with_sum(arr, target))  # 1

이 방법은 불필요한 부분을 탐색하지 않아 효율적이다. 그러나 여전히 최악의 경우 시간복잡도는 O(2n)이다.

3. 동적 계획법 (Dynamic Programming)

동적 계획법은 중복 계산을 줄이기 위해 합의 상태를 저장하는 방식으로, 목표 합을 효율적으로 찾는 데 유용하다.

이는 부분합 문제에 적용하여, 배열의 각 원소를 이용해 특정 합을 만들 수 있는지를 계산한다.

def count_subsequences_with_sum_dp(arr, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for num in arr:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    return dp[target]

arr = [1, 2, 3]
target = 5
print(count_subsequences_with_sum_dp(arr, target))  # 1

이 방법은 시간복잡도가 O(n × m)로, 배열의 크기와 목표 합에 따라 선형적으로 증가하여 매우 효율적이다.

4. 비트마스킹 (Bitmasking)

비트마스킹을 사용하면 각 비트를 통해 부분수열의 포함 여부를 표현할 수 있어 효율적이고 간결하게 부분수열의 합을 구할 수 있다.

비트마스크를 이용한 방법은 배열의 크기가 크지 않을 때 매우 편리하다.

def all_subsequence_sums_bitmask(arr):
    result = set()
    n = len(arr)
    for mask in range(1 << n):
        subset_sum = 0
        for i in range(n):
            if mask & (1 << i):
                subset_sum += arr[i]
        result.add(subset_sum)
    return result

arr = [1, 2, 3]
print(all_subsequence_sums_bitmask(arr))  # {0, 1, 2, 3, 4, 5, 6}

이 방법은 O(n × 2n)의 시간복잡도를 가지며, 코드가 간결하고 이해하기 쉽다.

알고리즘 선택 기준

  • 입력 크기가 작을 때: 완전 탐색 또는 비트마스킹이 적합하다.
  • 목표 합이 명확히 주어졌을 때: 백트래킹 또는 동적 계획법을 사용하는 것이 효과적이다.
  • 모든 합을 계산해야 할 때: 완전 탐색이나 비트마스킹이 좋다.

부분수열의 합 문제는 다양한 알고리즘적 접근이 가능하며, 각 방법의 시간복잡도와 특징을 고려하여 문제에 가장 적합한 방법을 선택하는 것이 중요하다. 배열의 크기나 목표 합에 따라 최적의 성능을 보장하는 알고리즘을 선택하는 것이 문제 해결의 핵심이다.

728x90