지금까지 배웠던 DP에서는 최적값을 찾는데에만 집중했지만, 이번 단원에서는 그 최적값을 구성하는 구성 요소들까지 추적해본다. 배낭문제로 예시를 들면, 배낭에 담을 수 있는 물건 가치의 최대값뿐만 아니라 어떤 물건들을 골랐을 때 그 가치가 도출되는까지 추적해야 한다. 각각의 부분 문제들을 해결할 때마다 어떤 상/하방 문제를 선택했는지를 저장하고 한번 더 탐색해 경로를 찾는다. 미로를 탐색할 때, 어떤 갈림길을 선택했는지 표시해두고 다시 돌아갈 때 그 표시를 따라가며 출력하는 것이다. 테크닉 특성 상 문제를 풀며 설명하는게 훨씬 이해하기 쉬우므로 각설하고 문제를 직접 풀어보자.
문제 풀이
- 1로 만들기 2
- BFS 경로 역추적 기본 문제입니다.
- 이전 항목을 기록하고 추적해봅시다.
- 가장 긴 증가하는 부분 수열 4
- LIS를 직접 출력해봅시다.
- 가장 긴 증가하는 부분 수열 5
- LIS를 에 구하고 출력해봅시다.
- LCS2
- LCS를 직접 출력해봅시다.
- 2차원 DP 테이블 추적 연습 문제
- 경찰차
- 보스 문제입니다.
- BFS 경로 역추적 응용 문제입니다.
- 숨바꼭질 4
- BFS 경로 역추적 기본 문제입니다.
- 1로 만들기 2 문제와 같은 문제입니다.
- DSLR
- BFS 경로 역추적 기본 문제입니다.
- 1로 만들기 2 문제와 같은 문제입니다.
- 최소비용 구하기 2
- Djikstra 알고리즘으로 최단거리를 구하고 그 경로를 출력해봅시다.
- 플로이드 2
- Floyd-Warshall 알고리즘으로 최단거리를 구하고 그 경로를 출력해봅시다.