🐨알고리즘] 비트 필드를 활용한 다이나믹 프로그래밍

비트 필드를 활용한 다이나믹 프로그래밍

다이나믹 프로그래밍은 복잡한 문제를 더 작고 관리 가능한 부분 문제로 나누어 해결하는 방식입니다. 이 방법은 문제의 중복 계산을 피함으로써 효율적인 문제 해결이 가능하게 합니다. 하지만, 많은 다이나믹 프로그래밍 문제는 상태 공간의 크기가 크기 때문에, 메모리 사용량이 문제가 될 수 있습니다. 여기서 비트 필드를 사용하면 상태를 효율적으로 표현하고 메모리 사용을 줄일 수 있습니다.

비트 필드란?

비트 필드는 데이터를 비트 단위로 표현하는 방법입니다. 각 비트는 0 또는 1의 값을 가질 수 있으며, 여러 상태나 플래그를 하나의 정수로 표현할 수 있습니다. 이는 메모리를 절약하고, 비트 연산을 통해 빠르게 데이터를 처리할 수 있는 장점이 있습니다.

비트 연산의 기초

비트 연산은 비트 단위의 연산을 수행합니다. 다음은 가장 자주 사용되는 비트 연산자들입니다:

• & (AND): 두 비트가 모두 1이면 1을 반환합니다.
• | (OR): 두 비트 중 하나라도 1이면 1을 반환합니다.
• ^ (XOR): 두 비트가 서로 다르면 1을 반환합니다.
• ~ (NOT): 비트를 반전합니다.
• <<: 지정된 비트 수만큼 왼쪽으로 이동시킵니다.
• >>: 지정된 비트 수만큼 오른쪽으로 이동시킵니다.

다이나믹 프로그래밍에서의 비트 필드 활용

비트 필드를 다이나믹 프로그래밍에 활용하는 방법은 다음과 같습니다:

1. 상태 정의: 문제의 상태를 비트로 표현합니다. 예를 들어, 집합의 포함 여부를 비트로 표현할 수 있습니다.
2. 상태 전이: 비트 연산을 사용하여 상태를 전이시킵니다. 이는 메모리를 절약하고, 계산을 빠르게 수행할 수 있게 합니다.
3. 최적화: 중복 계산을 방지하기 위해 계산된 결과를 저장하고 재사용합니다. 이를 메모이제이션(memoization)이라고 합니다.

예제: 여행하는 외판원 문제(TSP)

여행하는 외판원 문제는 모든 도시를 정확히 한 번씩 방문하고 시작점으로 돌아오는 최단 경로를 찾는 문제입니다. 비트 필드를 사용하여 각 도시의 방문 상태를 표현할 수 있습니다.

def tsp(dist):
    n = len(dist)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 시작 도시 방문 상태

    for mask in range(1 << n):
        for u in range(n):
            if mask & (1 << u):
                for v in range(n):
                    if mask & (1 << v) == 0:
                        next_mask = mask | (1 << v)
                        dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + dist[u][v])

    return min(dp[(1 << n) - 1][v] + dist[v][0] for v in range(1, n))

이 예제에서는 dist 배열이 각 도시 간의 거리를 나타냅니다.