반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 19: 스테이트 컴프레션 동적 계획법 (State Compression DP) 스테이트 컴프레션 동적 계획법 (State Compression DP)스테이트 컴프레션 동적 계획법(State Compression DP)은 상태를 비트마스크로 표현하여 동적 계획법을 적용하는 기법입니다. 이는 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 이 기법은 상태를 효율적으로 관리하고, 메모리 사용량을 줄일 수 있습니다.문제 예시: 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 스테이트 컴프레션 DP를 사용할 수 있습니다. 여기서 dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.스테이트 컴프레션 DP 구현다음은 C++로 스테이트 컴프레션 DP를 사용하여 문제를 해결하는 예제입니다.#.. 2024. 8. 1. 이전 1 다음 반응형
