[PCCP] 알고리즘 - 동적계획법

1. 이론

- Dynamic Programming은 전체 문제를 한 번에 해결하는 것이 아닌 작은 부분 문제들을 해결하여 이를 활용하여 전체 문제를 해결하는 것

- DP 활용 조건

    - Optimal Substructure(최적부분구조): 큰 문제를 작은 문제로 나누었을 떄 동일한 작은 문제 반복 등장

    - Overlapping Subproblem(중복부분문제): 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성

- 해결과정

    1) 점화식 세우기

    2) 메모이제이션 저장소 생성

    3) 재귀함수 정의 && 종료조건

- 최장증가부분수열(Long Increasing Subsequence)

    - 부분수열: 주어진 수열 중 전후 관계를 유지하며 일부를 뽑아 새로 만든 수열

    - LIS: 부분수열의 원소가 오름차순 유지하며 길이가 긴 수열

    - LIS 길이 구하기: 수열의 숫자 크기와 위치를 동시에 고려

- 최장공통부분수열(Longest Common Subsequence)

    - LCS: 두 수열이 어떤 기준에 따라 양쪽에서 공통으로 잘견 할 수 있는 가장 긴 부분 수열

   

 

2. 언어별 문법

<C++>

 

<Python>

 

3. 추천 문제

 

<Programmers>

- Lv2: 피보나치 수

- Lv2: 2 x n 타일링

- Lv2: 땅따먹기

- Lv2: 가장 큰 정사각형 찾기

- Lv3: 정수 삼각형

- Lv4: 도둑질

- Lv4: 단어 퍼즐

 

4. 참고자료

- 이것이 코딩테스트다 2021 다이나믹 프로그래밍

- 코딩테스트 필수 알고리즘(DP)

- 코딩테스트 합격자되기(파이썬) 16. 그리디