반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 17: 비트마스크 동적 계획법 (Bitmask DP) 비트마스크 동적 계획법 (Bitmask DP)비트마스크 동적 계획법은 상태를 이진수로 표현하여 여러 상태를 효율적으로 관리하는 기법입니다. 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 상태를 이진수로 표현하면 각 비트가 특정 원소의 포함 여부를 나타내어 간결하게 표현할 수 있습니다.문제 예시: 외판원 문제 (Traveling Salesman Problem, TSP)외판원 문제는 주어진 도시들을 방문하여 모든 도시를 한 번씩 방문하고 시작점으로 돌아올 때, 이동 비용의 합이 최소가 되도록 하는 경로를 찾는 문제입니다. 비트마스크 DP를 사용하여 해결할 수 있습니다.문제 정의주어진 도시 수 (n)각 도시 간의 거리 (dist[i][j])최소 이동 비용을 계산하여 출력비트마스크 DP 구현다음은 C+.. 2024. 8. 1. 이전 1 다음 반응형
