동적 계획법 4는 이전에 배웠던 알고리즘들과 DP를 연계하고 응용하는 문제들이기 때문에 별도로 설명할게 전혀 없다. 이 단원의 문제들을 풀기 위한 사전 지식은 앞선 단원들에서 이미 모두 배웠다. 스택, 큐, 세그먼트 트리, 문자열 알고리즘 등등,, 이제 문제들을 풀어보며 직접 인자와 점화식을 설계해보자. 모든 문제가 다 어렵다..
문제 풀이
- 팰린드롬 분할
- Manacher Algorithm을 응용해봅시다.
- 다른 알고리즘의 결과를 응용해 DP를 구현해봅시다.
- 로봇 조종하기
- 탐색 문제일까요?
- 방법을 출력하지 않는 숫자 맞추기
- 방법을 출력하지 않는 경찰차입니다. 문제 구조가 유사해요.
- 숫자 맞추기
- 방법도 출력해봅시다. 경찰차 문제랑 기믹만 다른 같은 문제입니다.
- 타일 채우기 2
- 점화식을 어떻게 계산해야 할까요?
- 컨닝
- 비트 마스크를 응용해봅시다.
- 격자판 채우기
- 비트 마스크를 응용해봅시다.
- 두부장수 장홍준
- 비트 마스크를 응용해봅시다.
- 최솟값 찾기
- 덱을 응용해봅시다.
- Mowing the Lawn
- 덱을 응용해봅시다.
- 연세워터파크
- 덱을 응용해봅시다.