필요성
일반적으로 DP를 사용할 때 저장된 값의 인덱스는 정수이다. 그러나 저장하려는 값이 정수가 아니라 배열일 경우 캐쉬에 해당 값을 저장하고 불러오는 게 매우 불편하다. 이 때 map자료구조를 사용할 수 있는데 , map자료구조는 비교와 연산에 시간이 오래걸리기 때문에 적합하지 않다
일대일 함수
입력에 대해 정수와 일대일 함수를 만들어 주면 배열과 같은 입력도 캐쉬의 인덱스로 사용할 수 있다. 만약 배열의 원소가 될 수 있는 수의 범위가 1부터 10이라면 총 10!개의 정수를 할당하고 각 배열과 연결해 주면 일대일 함수를 만들 수 있다.
boolean값 배열
배열의 원소가 참 거짓 두개의 값만을 가진 경우 비트마스크를 사용해 효율적으로 입력을 나타낼 수 있다. 비트마스크를 통해 나타나는 값을 십진수로 표현하면 배열의 인덱스로 사용할 수 있다. 이는 그래프에서 해당 정점의 방문 여부와 같은 사례에서 사용된다.
입력의 범위가 좁은 경우
입력의 범위가 좁은 경우 각 배열의 원소를 십진수 자리수로 설정해 나타낼 수 도 있다. 예를 들어 9,8,2,1과 같은 원소를 가진 배열이라고 하면 십진수 9821로 표현하는 것이다.
예제 - 여행하는 외판원 문제
여행하는 외판원 문제를 완전 탐색 문제로 접근할 경우 도시의 개수 n!만큼의 경로를 생성해야 하는데 이는 n이 매우 작은 경우를 제외하고는 지나치게 큰 수 이다.
사실 외판원 문제에서 새로운 경로를 설정할 때 필요한 정보는 지금까지의 도시 방문 여부와 남은 경로의 길이이다. 모든 경로를 저장하게 될 경우 n!의 부분 문제가 필요하지만 이렇게 문제를 축소할 경우 n*2^n개의 부분 문제로 문제를 해결할 수 있다.
비트마스크
1<<n은 1을 n만큼 왼쪽으로 민 이진수이므로 1과 n만큼의 0으로 나타난 수가 된다 이 수에서 -1을 빼게 된 경우 n만큼 1로 채워진 수가 되므로 모든 배열의 값이 true인 상황을 나타낼 수 있다.
특정 배열의 원소(정점) next를 true로 바꿔주고 싶은 경우 원래 값에 1<< next를 더해주면 된다. 이렇게 되면 원래 값의 해당 순서에 0이었던 값이 next자리에 1이 들어간 이진수와 + 연산되어 1, 즉 true가 된다.
