🐨BOJ#1086]박성원\비트 필드 활용 다이나믹 프로그래밍

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

1086번: 박성원

 

2 초

128 MB

10482

3074

2089

26.813%

문제

서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예로, {5221, 40, 1, 58, 9}로 5221401589를 만들 수 있다. 합친 수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.
하지만, 박성원은 이 문제를 풀지 못했다.
따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제에는 정답이 여러 개 있을 수도 있고, 박성원이 우연히 문제의 정답을 맞출 수도 있다. 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.

입력

첫째 줄: 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수.
둘째 줄부터 N개의 줄에는 집합에 포함된 수. 각 수의 길이는 길어야 50인 자연수이다.
마지막 줄: K가 주어진다. K는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 기약분수 형태로 출력
p/q꼴로 출력하며, p는 분자, q는 분모이다.
정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력.

예제 입력 1 복사

3
3
2
1
2

예제 출력 1 복사

1/3

예제 입력 2 복사

5
10
100
1000
10000
100000
10

예제 출력 2 복사

1/1

예제 입력 3 복사

5
11
101
1001
10001
100001
10

예제 출력 3 복사

0/1

예제 입력 4 복사

9
13
10129414190271203
102
102666818896
1216
1217
1218
101278001
1000021412678412681
21

예제 출력 4 복사

5183/36288

문제의 이해

너무나 오랫동안 다양한 방법으로 틀리고 심지어 컨닝하고 풀어도 시간초과가 떠서 황당했다.비트필드를 이용한 다이내믹프로그래밍에 대해 제대로 공부하기 위해 완전히 보고 풀기로 했다 ㅠㅠ일단 이걸 dp로 풀라고 하는데...점화식을 못 만들겠다.
(dp공부부터 더 해야...) 여기저기서 찾아 보았다.

dp[i][j] : i(비트)번 숫자들을 사용했을 때 나머지가 j(정수)인 경우의 수 (j ≤ K)
dp[방문한곳][현재 나머지]:방문한 숫자들을 나타내는 비트마스크 상태와 그 상태에서의 나머지 기록
DP[k][bit]: 현재까지 선택한 숫자들의 집합을 나타내는 비트마스크 bit 상태에서, 
나머지가 k일 때, 나머지 숫자들을 모두 사용하여 K로 나누었을 때 나머지가 0이 되는 순열 개수저장

세 방식은 모두 비트마스킹으로 선택된 숫자를 표현, DP로 주어진 나머지 상태에서 순열의 경우의 수를 계산한다.

1. dp[i][j]: i는 비트마스크로 선택된 숫자들을 나타내고, j는 해당 선택에서의 나머지를 나타낸다. 즉, 선택된 숫자들이 나머지 j를 가지는 순열의 경우의 수를 저장한다.
2. dp[방문한곳][현재 나머지]: 비트마스크(방문한곳)로 어떤 숫자들이 선택되었는지 나타내고, 현재 나머지는 이 선택에서의 나머지를 나타낸다. 이 역시 선택된 숫자들이 특정 나머지를 만들 수 있는 경우의 수를 저장한다.
3. DP[k][bit]: bit는 선택된 숫자들의 집합을 비트마스크 형태로 나타내고, k는 이때의 나머지이다. 이 배열은 비트마스크 상태에서 나머지가 k일 때, 나머지 숫자들을 모두 사용하여 K로 나누었을 때 나머지가 0이 되는 순열의 개수를 저장한다.

세 방식에서 설명된 dp[i][j], dp[방문한곳][현재 나머지], 그리고 DP[k][bit]는 사실상 같은 방식으로 동적 프로그래밍을 적용하고 있다. 이 세 가지 방식은 모두 다음과 같은 동일한 핵심 구성 요소를 사용한다:

1. 비트마스크를 활용하여 어떤 숫자들이 선택되었는지 표현
2. 나머지 값으로 현재 숫자 조합이 조건(여기서는 K로 나눈 나머지)을 충족하는지 판단
3. 동적 프로그래밍 테이블(dp 배열)이 비트마스크와 나머지를 인덱스로 중복 계산을 피하고 효율적으로 결과 저장

생각해 보기

순열이 {5221,40,1,58,9} K가 10이면, dp[10101][9]은,

1. `11001(2)`: `1`,`4`,`5`번이 선택된 상태. `5221`,`58`,`9`
2. [5221589, 5221958, 5852219, 5895221, 9522158, 9585221]
3. 나머지는 각각 [9,8,9,1,8,1] 이 중 9는 2개 `dp[10101][9] = 2`
4. 모든 경우의 수 중 나머지가 0이 되는 경우의 수를 구해야 하니까
5. 비트가 n개 필요하고 모든 비트가 0인 경우는 제외한 dp[$2^n-1$]중 [0]값들의 합이 정답의 개수
6. 모든 dp값의 합이 전체 경우의 수다.

만약 비트필드를 사용하지 않는다면,

1. 리스트 또는 배열 사용

• 숫자들의 선택 상태를 리스트나 배열에 저장하여 관리할 수 있습니다. 예를 들어, selected=[False, False, True, True, True]와 같은 방식으로 각 숫자의 선택 여부를 표현할 수 있습니다.
• 이 방식은 인덱싱이 직관적이지만, 상태 전이나 메모리 접근에 있어서 비트마스크보다 더 많은 계산과 메모리를 필요로 할 수 있습니다.

2. 순열 및 조합을 이용

• 모든 가능한 순열을 생성하고 각 순열에 대해 나머지를 계산하여 조건을 만족하는 경우를 카운트합니다. 이 방식은 계산량이 매우 많아 비효율적일 수 있습니다.
• 파이썬의 itertools.permutations 같은 라이브러리 함수를 사용하여 모든 순열을 생성할 수 있습니다.

3. 해시 테이블 활용

• 각 숫자 조합을 문자열이나 다른 형태의 키로 변환하여 해시 테이블에서 관리할 수 있습니다.
• 이 방식은 상태 관리에 유연성을 제공하지만, 해시 충돌 관리나 키 생성으로 인한 추가 계산이 필요합니다.

4. 재귀 함수의 깊이 제한

• 순열의 경우에는 깊이 제한을 두고 재귀적으로 숫자를 선택하면서 해결할 수도 있습니다. 이 경우 선택된 숫자의 리스트를 파라미터로 전달하거나 전역 변수를 사용할 수 있습니다.

성능과 복잡도 측면

비트마스크를 사용하는 방식은 상태 전이가 매우 빠르고 메모리 사용이 효율적입니다. 숫자들의 선택 상태를 정수 하나로 표현할 수 있기 때문에, 동적 프로그래밍 테이블의 인덱싱과 접근이 간단하고 빠릅니다. 반면, 비트마스크를 사용하지 않을 경우, 상태를 관리하고 전이하는 데 더 많은 리소스가 소모될 수 있으며, 코드의 복잡성도 증가할 수 있습니다. 따라서 대체 방법들은 비트마스크에 비해 성능과 복잡도 측면에서 일반적으로 불리하다고 볼 수 있습니다.

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

비트 필드를 이용한 다이나믹 프로그래밍은 문제의 상태를 효율적으로 표현하고 메모리를 절약하는 데 도움을 주는 기법입니다. 이 방법은 특히 상태가 여러 요소의 조합으로 구성될 때 유용하며, 각 요소가 두 가지 상태(예: 포함/비포함) 중 하나를 가질 때 자주 사용됩니다. 이러한 특징 때문에 비트 연산을 통해 상태를 쉽게 표현하고 관리할 수 있습니다.

비트 필드의 기본 개념

비트 필드는 정수의 각 비트를 독립적인 부울 값(참 또는 거짓)으로 사용하여 여러 상태를 한 번에 저장할 수 있는 방식입니다. 예를 들어, 정수 하나를 사용하여 최대 32개의 부울 값을 저장할 수 있으며, 이는 각 비트가 하나의 부울 값에 해당하기 때문입니다.

비트 연산자

비트 필드를 다룰 때는 주로 다음과 같은 비트 연산자를 사용합니다:

• & (비트 AND): 두 비트 모두 1이면 결과는 1, 그렇지 않으면 0
• | (비트 OR): 두 비트 중 하나라도 1이면 결과는 1
• ^ (비트 XOR): 두 비트가 서로 다르면 결과는 1, 같으면 0
• ~ (비트 NOT): 비트를 반전(0은 1로, 1은 0으로)
• << (왼쪽 시프트): 비트를 왼쪽으로 이동시키고, 새로운 비트는 0으로 채움
• >> (오른쪽 시프트): 비트를 오른쪽으로 이동시키고, 새로운 비트는 0으로 채움

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

여행하는 외판원 문제는 모든 도시를 정확히 한 번씩 방문하고 시작점으로 돌아오는 최단 경로를 찾는 문제입니다. 이 문제는 비트 필드를 사용하여 다이나믹 프로그래밍으로 효율적으로 해결할 수 있습니다.

문제 설정

• 도시의 수: $n$
• 거리 배열: $\text{dist}[i][j]$는 도시 $i$에서 도시 $j$ 까지의 거리

DP 배열

• $\text{dp}[S][i]$ : 현재까지 방문한 도시 집합이 ( S )이고, 마지막으로 방문한 도시가 ( i )일 때의 최단 경로 길이

점화식

• $ \text{dp}[S][i] = \min(\text{dp}[S][i], \text{dp}[S \setminus {i}][j] + \text{dist}[j][i]) $ 여기서 $ j $  는 $ S $ 에 속하고 $ i \neq j $

파이썬 코드 예시

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

    for S in range(1 << n):
        for i in range(n):
            if S & (1 << i):
                for j in range(n):
                    if S & (1 << j) and i != j:
                        dp[S][i] = min(dp[S][i], dp[S ^ (1 << i)][j] + dist[j][i])

    return min(dp[(1 << n

) - 1][i] + dist[i][0] for i in range(1, n))

# 예제 거리 배열
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

print(tsp(dist))  # 최단 경로의 길이 출력

위 코드는 모든 도시를 한 번씩 방문하는 최소 비용을 계산합니다. 비트 필드를 이용해 각 상태를 표현하고, 이를 기반으로 다이나믹 프로그래밍을 적용합니다.

비트 필드를 사용하여 상태를 표현하는 것은 여러 상태를 조합해서 하나의 정수로 요약하는 방식입니다. 각 비트는 독립적인 상태 정보를 나타내며, 비트가 1이면 해당 상태가 "활성화"되었음을, 0이면 "비활성화"되었음을 의미합니다. 이를 통해 여러 조건을 한 번에 체크하고 수정할 수 있어 다이나믹 프로그래밍에서 매우 유용하게 사용됩니다.

예시: 여행하는 외판원 문제의 상태 표현

4개의 도시를 여행하는 외판원 문제를 예로 들어 상태를 비트 필드로 표현하는 방법을 시각화해 보겠습니다. 각 도시를 A, B, C, D라고 하고, 각 도시의 방문 여부를 각각 한 비트로 표현합니다.

• A: 첫 번째 비트
• B: 두 번째 비트
• C: 세 번째 비트
• D: 네 번째 비트

비트 필드 예시

• 0000: 아직 어떤 도시도 방문하지 않음
• 0001: 도시 A만 방문함
• 0010: 도시 B만 방문함
• 0100: 도시 C만 방문함
• 1000: 도시 D만 방문함
• 0011: 도시 A와 B를 방문함
• 0101: 도시 A와 C를 방문함
• 0110: 도시 B와 C를 방문함
• 1011: 도시 A, B, D를 방문함
• 1111: 모든 도시를 방문함

각 상태는 정수로 표현되며, 이 정수를 이진수로 변환했을 때 각 비트의 값이 각 도시의 방문 여부를 나타냅니다. 예를 들어, 1011은 이진수로 표현하면 $ 2^3 + 2^1 + 2^0 = 8 + 2 + 1 = 11 $ 입니다. 이는 도시 A, B, D를 방문했음을 의미하며, C는 방문하지 않았습니다.

https://velog.io/@e_juhee/python-%EB%B0%B1%EC%A4%80-2098-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-DP-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9-lso2bk58

[python] 백준 2098 :: 외판원 순회 (DP, 비트마스킹)

불리언 배열과의 비교

비트 필드가 불리언 배열보다 나은지 여부는 사용하는 문제의 특성과 요구 사항에 따라 달라집니다. 각 방식의 장단점을 비교해 보겠습니다.

비트 필드의 장점

1. 메모리 효율성: 비트 필드는 각 상태를 비트 하나로 표현하기 때문에 불리언 배열에 비해 훨씬 적은 메모리를 사용합니다. 예를 들어, 32개의 불리언 값을 저장하기 위해 불리언 배열을 사용하면 32바이트가 필요하지만, 비트 필드는 단 4바이트(정수 하나)로 같은 정보를 저장할 수 있습니다.
2. 속도: 비트 연산은 CPU에서 매우 빠르게 처리됩니다. 따라서 여러 불리언 값을 동시에 처리해야 하는 경우 비트 필드를 사용하는 것이 효과적일 수 있습니다.
3. 연산 편의성: 여러 상태를 한 번에 처리할 수 있는 비트 연산(AND, OR, XOR 등)을 사용할 수 있어, 복잡한 조건을 효율적으로 처리할 수 있습니다.

불리언 배열의 장점

1. 가독성과 접근성: 코드를 읽고 이해하기 쉽습니다. 각 요소에 이름을 부여하거나, 인덱스로 직접 접근할 수 있기 때문에 프로그래밍이 간편합니다.
2. 유연성: 불리언 배열은 비트 필드보다 덜 제한적입니다. 예를 들어, 배열의 크기를 동적으로 변경하거나, 복잡한 자료구조에 통합하기 쉽습니다.

사용 상황에 따른 선택

• 비트 필드 사용 권장: 메모리 사용을 최소화해야 하거나, 상태를 빠르게 처리해야 하는 최적화가 필요한 알고리즘에 적합합니다. 예를 들어, 비트마스크를 활용한 다이나믹 프로그래밍 문제나, 상태의 전체 조합을 효율적으로 검사해야 할 때 유리합니다.
• 불리언 배열 사용 권장: 코드의 명확성과 유지보수성이 중요하거나, 개별 요소에 자주 접근해야 할 때 적합합니다. 코드를 처음 보는 사람도 쉽게 이해하고 수정할 수 있습니다.

결국, 문제의 요구 사항과 프로젝트의 우선 순위에 따라 적절한 방식을 선택하는 것이 중요합니다. 메모리와 성능 최적화가 중요한 상황에서는 비트 필드가 유리할 수 있지만, 코드의 가독성과 유지보수가 더 중요한 경우 불리언 배열을 선택하는 것이 좋습니다.

비트마스크 비트필드 자꾸 용어가 왔다갔다 해서 찾아보았다.

레퍼런스(이거 보고 풀었음ㅠ)

https://cantcoding.tistory.com/2

1086 박성원 (비트,DP)

https://velog.io/@kevin622/BOJ-1086-%EB%B0%95%EC%84%B1%EC%9B%90

BOJ 1086 박성원

import sys
from math import gcd, factorial

def input():
    return sys.stdin.readline().strip()

def mod_exp(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2:
            res = (res * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return res

def count_perms(len, vis, rem):
    if vis == (1 << n) - 1:
        return 1 if rem == 0 else 0
    if memo[vis][rem] != -1:
        return memo[vis][rem]
    
    cnt = 0
    for i in range(n):
        if not vis & (1 << i):
            new_vis = vis | (1 << i)
            new_rem = (rem + rem_mod[i][len]) % k
            cnt += count_perms(len + lens[i], new_vis, new_rem)
    
    memo[vis][rem] = cnt
    return cnt

n = int(input())
nums = [int(input()) for _ in range(n)]
lens = [len(str(num)) for num in nums]
k = int(input())
memo = [[-1] * k for _ in range(1 << n)]
rem_mod = [[-1] * sum(lens) for _ in range(n)]

for i in range(n):
    for l in range(sum(lens)):
        rem_mod[i][l] = (nums[i] * mod_exp(10, l, k)) % k

valid = count_perms(0, 0, 0)
perms = factorial(n)

if valid == 0:
    print('0/1')
else:
    g = gcd(perms, valid)
    print(f'{valid // g}/{perms // g}')

 

이 코드는 주어진 숫자 리스트를 재배열하여 만들 수 있는 모든 숫자 조합이 주어진 수 ( K )로 나누어 떨어지는 비율을 계산하는 알고리즘을 구현합니다. 코드는 동적 프로그래밍(Dynamic Programming, DP), 비트 마스킹, 그리고 모듈러 연산을 활용합니다.

코드 상세 설명

입력 및 초기화

n = int(input())
nums = [int(input()) for _ in range(n)]
lens = [len(str(num)) for num in nums]
k = int(input())
memo = [[-1] * k for _ in range(1 << n)]
rem_mod = [[-1] * sum(lens) for _ in range(n)]

• n: 숫자의 개수입니다.
• nums: 각 줄에서 입력받은 숫자들의 배열입니다.
• lens: 각 숫자의 자릿수를 저장합니다.
• k: 나눗셈에 사용될 모듈러 값입니다.
• memo: DP를 위한 메모이제이션 테이블입니다. 각 비트마스크 상태(방문된 숫자들)와 현재까지의 나머지에 대한 결과를 저장합니다.
• rem_mod: 각 숫자를 다양한 길이의 (10)의 거듭제곱과 곱한 후 ( k )로 나눈 나머지를 저장합니다.

User
for i in range(n):
    for l in range(sum(lens)):
        rem_mod[i][l] = (nums[i] * mod_exp(10, l, k)) % k

이 코드 부분은 rem_mod 이라는 2차원 배열을 채우는 과정입니다. 여기서 주요 목적은 각 숫자를 10의 l제곱 만큼 곱한 후 k로 나눈 나머지를 계산하는 것입니다. 이것은 나중에 숫자들의 순열을 만들 때 각 숫자의 위치에 따라 변하는 나머지를 빠르게 계산하기 위해 사용됩니다.

1. for i in range(n): - 이 루프는 입력된 숫자들의 배열 nums를 순회합니다.
2. for l in range(sum(lens)): - lens 배열은 각 숫자의 자릿수를 저장하고 있습니다. sum(lens)는 모든 숫자들의 총 자릿수를 의미하며, 이것은 최대 가능한 숫자 위치를 나타냅니다.
3. rem_mod[i][l] = (nums[i] * mod_exp(10, l, k)) % k - 여기서 각 숫자 nums[i]는 10의 l 제곱 만큼 곱해진 후 k로 나눈 나머지를 계산합니다. 이 계산은 숫자가 순열에서 다른 위치에 있을 때 필요한 나머지 변환을 미리 계산해 놓는 것입니다.

이렇게 계산하는 이유:
숫자의 순열을 구성할 때, 각 숫자의 위치에 따라 그 영향을 k를 모듈로 하는 나머지에 반영해야 합니다. 예를 들어, 숫자 123과 456이 있고 k=100일 때, 123456과 456123은 서로 다른 값으로 계산됩니다. 숫자의 순서와 위치에 따라 나머지가 달라지기 때문에, 이를 미리 계산해두면 순열을 효율적으로 구할 수 있습니다.

이 배열을 사용하면, 숫자의 순서를 바꾸는 다양한 순열을 생성할 때 매번 긴 숫자를 계산하지 않고, 미리 계산된 나머지를 이용하여 빠르게 최종 나머지를 결정할 수 있습니다. 이는 시간 복잡도를 크게 줄여주는 효과적인 최적화 방법입니다.

모듈러 지수 연산 함수

def mod_exp(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2:
            res = (res * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return res

• 이 함수는 주어진 base를 exp 승한 결과를 mod로 나눈 나머지를 효율적으로 계산합니다.

유효 순열 계산 함수

def count_perms(len, vis, rem):
    if vis == (1 << n) - 1:
        return 1 if rem == 0 else 0
    if memo[vis][rem] != -1:
        return memo[vis][rem]
    
    cnt = 0
    for i in range(n):
        if not vis & (1 << i):
            new_vis = vis | (1 << i)
            new_rem = (rem + rem_mod[i][len]) % k
            cnt += count_perms(len + lens[i], new_vis, new_rem)
    
    memo[vis][rem] = cnt
    return cnt

 

이 count_perms 함수는 주어진 숫자들을 사용하여 만들 수 있는 모든 순열 중에서, 모듈로 k를 사용한 나머지가 0인 순열의 개수를 계산하는 재귀 함수입니다. 이 함수는 동적 프로그래밍과 백트래킹 기법을 활용하여 중복 계산을 방지하고 효율적으로 문제를 해결합니다.

매개변수 설명

• len: 현재까지 구성된 숫자의 길이입니다.
• vis: 방문한 숫자들을 비트마스크 형태로 나타내는 정수입니다.
• rem: 현재까지 구성된 숫자를 k로 나눈 나머지입니다.

함수의 작동 원리

1. 기저 조건 (Base Case):
   • if vis == (1 << n) - 1: 모든 숫자가 한 번씩 사용되었는지 확인합니다. 만약 모든 숫자가 사용되었다면 (vis 비트마스크가 모든 비트가 1인 상태),
     • return 1 if rem == 0 else 0: 최종적으로 구성된 숫자의 나머지가 0이면 이는 유효한 순열로 간주하여 1을 반환하고, 그렇지 않으면 0을 반환합니다.
2. 메모이제이션 (Memoization):
   • if memo[vis][rem] != -1: 이미 계산한 vis와 rem 상태의 결과가 메모리에 있다면 그 값을 반환합니다. 이는 중복 계산을 방지하고 성능을 향상시키는 중요한 단계입니다.
3. 순열 구성 (Permutation Construction):
   • cnt = 0: 가능한 순열의 수를 카운트합니다.
   • for i in range(n): 모든 숫자를 순회합니다.
     • if not vis & (1 << i): 현재 숫자 i가 아직 사용되지 않았다면,
       • new_vis = vis | (1 << i): 현재 숫자를 사용했다고 표시합니다.
       • new_rem = (rem + rem_mod[i][len]) % k: 새로운 나머지를 계산합니다. 여기서 rem_mod[i][len]은 이전에 계산해 둔 nums[i]를 10^len으로 곱하고 k로 나눈 나머지 값입니다.
       • cnt += count_perms(len + lens[i], new_vis, new_rem): 새로운 상태로 재귀 호출을 수행하고 반환된 값을 cnt에 추가합니다.
4. 결과 저장 및 반환:
   • memo[vis][rem] = cnt: 계산된 결과를 메모리에 저장합니다.
   • return cnt: 현재 상태에서의 가능한 순열 수를 반환합니다.

이 함수는 모든 가능한 순열을 시도하면서 각 순열이 주어진 조건 (나머지가 0인 경우)을 만족하는지 검사하고, 만족하는 경우의 수를 세어 결과를 도출합니다. 동적 프로그래밍을 사용함으로써, 이미 계산한 결과는 재계산하지 않고 메모리에서 바로 가져오므로 계산 효율이 크게 향상됩니다.

 

비트 연산과 비트 마스크를 사용하는 방식을 이해하기 위해 간단한 예시를 들어 설명드리겠습니다. 예를 들어 n = 3이라고 가정하고, 각 숫자가 방문되었는지 여부를 추적하는 상황을 살펴보겠습니다.

초기화

숫자가 3개 있고 각 숫자의 방문 여부를 표현하기 위해 3비트를 사용합니다. 각 비트는 숫자가 사용되었는지를 나타냅니다.

• 000 : 아직 어떤 숫자도 방문하지 않은 상태입니다.

숫자 방문

각 숫자를 방문할 때마다 해당 숫자에 해당하는 비트를 1로 설정합니다.

• 숫자 0을 방문: 1 << 0 연산을 수행합니다. 결과는 001입니다.
• 숫자 1을 방문: 1 << 1 연산을 수행합니다. 결과는 010입니다.
• 숫자 2를 방문: 1 << 2 연산을 수행합니다. 결과는 100입니다.

비트 마스크 검사

숫자가 방문되었는지 확인하려면 & 연산을 사용합니다.

• vis = 001 (숫자 0만 방문)
  • vis & (1 << 0) 결과는 001 (0이 방문되었음)
  • vis & (1 << 1) 결과는 000 (1이 아직 방문되지 않음)

모든 숫자 방문 여부

모든 숫자가 방문되었는지 확인하려면 vis가 111이 되었는지 확인합니다.

• if vis == (1 << 3) - 1: 이는 if vis == 7과 동일하며, 이진수로는 111입니다.

예시: 숫자 0과 1 방문 후 상태 변경

• 초기 vis = 000
• 숫자 0 방문: new_vis = 000 | (1 << 0) → new_vis = 001
• 숫자 1 방문: new_vis = 001 | (1 << 1) → new_vis = 011
• 검사: 011 & (1 << 0) → 001 (0번 방문됨), 011 & (1 << 1) → 010 (1번 방문됨)

이런 식으로 비트 연산을 사용하면 각 숫자의 방문 여부를 효율적으로 관리하고 확인할 수 있습니다.

결과 출력

valid = count_perms(0, 0, 0)
perms = factorial(n)

if valid == 0:
    print('0/1')
else:
    g = gcd(perms, valid)
    print(f'{valid // g}/{perms // g}')

• 모든 가능한 순열 중 ( K )로 나누어 떨어지는 경우의 수를 계산하고, 이를 총 순열 수로 나누어 기약분수 형태로 결과를 출력합니다.

비트필드를 이용한 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 상태 공간을 효율적으로 관리하고, 메모리 및 계산 시간을 절약할 수 있는 방법 중 하나입니다. 이 방법은 특히 "상태"를 이진 숫자의 형태로 표현할 수 있는 경우에 유용합니다. 예를 들어, 여러 요소(예: 도시, 아이템, 숫자 등)의 집합에서 각 요소가 선택되었는지 여부를 비트로 표현할 수 있습니다.

비트필드와 DP

비트필드는 각 비트가 특정 상태(예: 선택됨/선택되지 않음)를 나타내는 이진수입니다. 동적 프로그래밍에서 비트필드를 사용하면, 각 상태를 배열의 인덱스로 쉽게 매핑할 수 있으며, 이를 통해 상태 전이를 매우 빠르게 처리할 수 있습니다.

비트 연산자 활용

비트필드를 사용한 DP에서는 비트 연산자들이 중요한 역할을 합니다:

• AND 연산(&): 특정 요소가 선택되었는지 확인할 때 사용합니다.
• OR 연산(|): 새로운 요소를 선택 상태에 추가할 때 사용합니다.
• XOR 연산(^): 요소의 상태를 토글할 때 사용합니다.
• SHIFT 연산(<<, >>): 비트를 좌우로 이동시키며, 요소의 인덱스 조정에 사용합니다.

예시 코드 설명

위에서 주어진 코드에서 비트필드와 DP를 사용하는 부분을 다시 살펴보겠습니다:

memo = [[-1] * k for _ in range(1 << total_numbers)]

• memo 배열은 모든 가능한 선택 상태(1 << total_numbers는 2^total_numbers)와 각 상태에서 가능한 나머지(k)에 대한 결과를 저장합니다.

for num in range(total_numbers):
    if not visited_numbers & (1 << num):
        new_visited = visited_numbers | (1 << num)
        new_remainder = (current_remainder + remainder_mod[num][current_length]) % k
        count += count_valid_permutations(current_length + number_lengths[num], new_visited, new_remainder)

• 각 숫자가 아직 선택되지 않았다면 (not visited_numbers & (1 << num)), 이 숫자를 선택 상태에 추가합니다 (visited_numbers | (1 << num)).
• 새로운 나머지를 계산하고, 이 상태를 가지고 재귀적으로 다음 순열을 탐색합니다.

이와 같은 방식으로 비트필드를 활용한 DP는 문제의 상태 공간이 크고 복잡할 때 매우 유용하게 사용될 수 있습니다. 각 상태를 비트로 표현함으로써 상태 전이를 매우 빠르게 수행할 수 있고, 필요한 메모리도 상당히 절약할 수 있습니다.

https://youtu.be/ut-2i7ixg5E?t=6

https://en.wikipedia.org/wiki/DIP_switch