외판원 순회 문제를 접하고 비트 마스킹이란 걸 알게되었습니다.
DP를 선언할 때 DP[16][1<<16]으로 표현을해서 각 도시를 방문했는지 안했는지를 표현하게 되는데
비트마스킹을 사용하지않으면 16차원의 bool 배열을 사용해야한다는데 이 부분이 잘 이해가 가지않습니다.
왜 비트마스킹을 사용하지 않으면 N 차원 (N은 도시의 수) 배열을 사용해서 방문 여부를 표시해야하나요 ?
생각을 해봐도 잘 떠오르질 않습니다.
댓글을 작성하려면 로그인해야 합니다.
kokoxg2 6년 전
외판원 순회 문제를 접하고 비트 마스킹이란 걸 알게되었습니다.
DP를 선언할 때 DP[16][1<<16]으로 표현을해서 각 도시를 방문했는지 안했는지를 표현하게 되는데
비트마스킹을 사용하지않으면 16차원의 bool 배열을 사용해야한다는데 이 부분이 잘 이해가 가지않습니다.
왜 비트마스킹을 사용하지 않으면 N 차원 (N은 도시의 수) 배열을 사용해서 방문 여부를 표시해야하나요 ?
생각을 해봐도 잘 떠오르질 않습니다.