목록2025/07/31 (1)
Elevation
비트필드를 이용한 다이나믹 프로그래밍 (비트마스킹)
비트마스킹(bitmasking)은 기본적으로 이진수 표현을 활용해서 자료를 저장하는 기법이다. 컴퓨터는 기본적으로 이진수 단위로 연산하다 보니 비트마스킹을 활용하면 메모리와 시간의 절약이 가능하다. 가령 0과 1로만 이루어진 자료를 표현할 때, [0, 1, 1, 0, ...]처럼 정수의 배열로 표현하는 것보다는, 0110...(2)로 묶어 하나의 정수로 담으면 더 효율적일 것이다. 다만 ps에서 비트마스킹이 필수일 정도로 시간/공간복잡도가 빡빡한 문제는 많지는 않다. 대신 이렇게 비트필드를 이용하면 자료를 하나의 수로 표현할 수 있음을 이용해, 서브 문제의 상태를 비트마스킹하여 dp 배열에 저장하는 방식으로 문제를 푸는 기법이 있다. 이를 비트필드를 이용한 DP라고 한다. 외판원 순회 문제(TSP)TS..
ps/dp
2025. 7. 31. 04:45