조합 알고리즘

8.1 조합 알고리즘 정의

조합 알고리즘은 다른 조합 구조를 계산하고, 나열하고, 생성하는 문제를 해결하기 위해 설계된 알고리즘이야. 이 알고리즘은 집합, 부분집합, 순열, 조합 및 다른 조합 객체를 다루기 위해 사용돼.

주요 조합 문제 유형

• 순열: 집합의 요소들로 만들 수 있는 모든 가능한 순서 조합.
• 조합: 주어진 크기의 순서 없는 모든 가능한 부분집합.
• 배치: 주어진 크기의 순서 있는 모든 가능한 부분집합.
• 분할: 집합을 부분집합으로 나누는 모든 가능한 방법.
• 조합 객체: 그래프, 행렬 등과 같은 다른 구조.

조합 알고리즘의 장점과 단점

장점:

• 완전 나열: 이 알고리즘은 모든 가능한 조합을 나열할 수 있어서 철저한 탐색 문제에 유용해.
• 유연성: 조합과 관련된 다양한 문제를 해결할 수 있게 조절할 수 있어.
• 직관성: 많은 사람들이 재귀적 접근과 백트래킹 기술 덕분에 알고리즘을 쉽게 이해하고 구현할 수 있어.

단점:

• 조합 폭발: 입력 데이터가 증가하면 실행 시간과 메모리 사용량이 급격히 증가할 수 있어 (예: O(n!)).
• 비효율성: 많은 조합이 있을 경우 이 알고리즘은 비효율적일 수 있고, 더 진보된 기법으로 개선하거나 대체해야 할 수 있어 (예: 동적 프로그래밍이나 탐욕 알고리즘 사용).

조합 알고리즘의 시간 및 공간 복잡성

시간 복잡성:

• 순열: O(n!), 여기서 n은 집합의 요소 수야.
• 조합: O(C(n, k)), C(n, k)는 이항 계수로, n! / (k! * (n - k)!)야.
• 배치: O(A(n, k)), A(n, k)는 배치 수로, n! / (n - k)!야.
• 부분집합: O(2^n), 각 n 요소가 부분집합에 포함될 수도 있고 포함되지 않을 수도 있기 때문이야.

공간 복잡성:

일반적으로, 재귀적 빌드 과정에서 중간 결과를 저장하기 위해 O(n)이 필요하지만, 최종 메모리는 모든 결과를 저장하기 위해 필요할 수도 있어 (예: 순열의 경우 O(n * n!)).

조합 알고리즘 예시

8.2 순열 생성

문제:

주어진 집합의 모든 고유한 순열을 찾아라.

알고리즘:

재귀 또는 반복 방법을 사용하여 요소의 모든 가능한 순서 조합을 생성해.

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

print(permute([1, 2, 3]))

8.3 조합 생성

문제:

집합에서 주어진 크기의 모든 조합을 찾아라.

알고리즘:

재귀 또는 반복을 사용하여 주어진 크기의 모든 가능한 부분집합을 생성해.

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))
        

8.4 집합 분할 생성

문제:

집합을 부분집합으로 나누는 모든 가능한 방법을 찾아라.

알고리즘:

재귀를 사용하여 집합의 모든 가능한 분할을 생성해.

import copy

def partition_set(s):
    result = []

    def backtrack(part, rest):
        if not rest:
            result.append(copy.deepcopy(part[:]))
            return
        for i in range(len(part)):
            part[i].append(rest[0])
            backtrack(part, rest[1:])
            part[i].pop()
        part.append([rest[0]])
        backtrack(part, rest[1:])
        part.pop()

    backtrack([], list(s))
    return result

print(partition_set({1, 2, 3}))
        
        

copy.deepcopy(part[:])는 part 리스트의 깊은 복사를 생성해. 이는 원래 part와 연결되지 않은 새롭고 독립적인 리스트를 생성한다는 것을 의미해. 따라서 result의 각 요소는 고유한 분할을 나타내게 돼.