동적 계획법 3 설명

지금까지 인자를 설정하고 부분 문제로 분할하고 점화식을 세우는 방법을 알아보았다. 아직도 이 단원을 포함해 동적 계획법 단원이 3개나 남아있는데, 사실 DP 자체에 대해서 더 배울건 없다. 이제 DP를 활용한 실제 문제 풀이나 곁가지 테크닉을 배워 DP와 연계하는 방법들을 배울 것이다. 이번 단원에서는 비트마스크라는 테크닉을 추가로 배우고 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. 코드 간소화 비트 상태 여러개를 바꿀 때마다 반복문을 돌리면 코드가 길고 복잡해진다. 추후 예시에서 비트마스킹을 사용한 코드와 사용하지 않은 코드를 직접 비교해보자.

어떤 연산들이 있나요?

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와 접근 방법이 다릅니다.