동적 계획법 3 설명

지금까지 인자를 설정하고 부분 문제로 분할하고 점화식을 세우는 방법을 알아보았다. 이번 단원에서는 비트마스크라는 테크닉을 추가로 배우고 DP와 연계해 문제를 푸는 방법을 알아볼 것이다.

비트 마스크란?

전구 5개의 상태를 표현할 때, 각 전구들을 모두 별도의 변수들로 저장하면 가장 작은 자료형 char을 사용해도 5byte가 필요하다. 그리고 메모리는 언제나 청크 단위이므로 실제 메모리는 20~40 byte가 소모된다. ( 메모리 최소 단위 참조 ) 전구 하나는 On(1) Off(0)으로 2가지의 상태만 가지므로 5개의 전구는 $2^5=32$가지의 상태를 가질 수 있다. 이걸 표현하기 위해 5byte를 사용하는 것은 너무 비효율적이다. 이와 같이 두 가지 상태만 가지는 배열을 효율적으로 계산하기 위해 각 상태값을 이진수의 자릿수와 매칭시켜 조작하는 기법을 비트 마스크라고 한다. 예를들어 가운데 전구만 꺼진 5개 전구의 상태를 표현하면 다음과 같다. 각각의 전구 상태를 0 / 1에 대응시켜 이진수로 변환하면 $11011_{(2)}=27$이 된다.

이걸 왜 쓰나요?

1. 공간 절약 하나의 이진 상태를 표현하는데 4~8바이트를 사용하는 건 너무 낭비다. ( 메모리 최소 단위 참조 )
2. 시간 절약 비트 상태를 배열로 조작하면 비트 하나를 연산할 때마다 배열을 조작해야 한다. 비트 비스크을 통하면 $O(1)$으로 대부분의 다중 연산을 수행할 수 있다.
3. 코드 간소화 비트 상태 여러개를 바꿀 때마다 반복문을 돌리면 코드가 길고 복잡해진다. 추후 예시에서 비트마스킹을 사용한 코드와 사용하지 않은 코드를 직접 비교해보자.
4. 상태의 인자화 상태를 배열로 나타내면 배열의 인자로 넣을 수 없지만 비트마스크를 사용하면 어떤 상태 자체를 인자로 취급할 수 있다.

어떤 연산들이 있나요?

1. AND & 연산자로 사용하며 연산하는 두 수의 자릿수가 모두 $1$이어야만 $1$이 된다. 조건문의 &&와 동일하다.
2. OR | 연산자로 사용하며 연산하는 두 수의 자릿수 중 하나라도 1이면 1이 된다. 조건문의 ||와 동일하다.
3. NOT ~ 연산자로 사용하며 연산하는 수의 $0$/$1$을 반전시킨다.
4. XOR ^ 연산자로 사용하며 연산하는 두 수의 비트가 같으면 $0$, 다르면 $1$이 된다.
5. LSH / RSH 각각 Left Shift / Right Shift로 이진수 전체를 양쪽으로 밀어내는 연산이다. 쉽게 말해 그냥 나머지 버리는 $÷2$ 와 $\times 2$다.

문제 풀이

첫 문제에서 실제로 비트 마스크를 어떻게 조작하는지 예시를 확인하고 문제를 풀어보자.

1. 집합
   • 비트 마스크를 조작해봅시다.
   • DP 문제는 아닙니다.
2. 할 일 정하기
   • 비트 마스크와 DP를 연계해봅시다
3. 외판원 순회
   • 비트 마스크 DP 웰논
   • TSP ( Traveling Salesman problem ) 문제라고 합니다.
4. 박성원
   • 비트 마스크 보스 문제
   • 무엇을 인자로 삼아야 할지 잘 고민해봅시다.
5. RGB 거리2
   • 환형 DP 문제를 풀어봅시다.
6. 색상환
   • 환형 DP 문제2
   • RGB 거리2와 접근 방법이 다릅니다.