[알고리즘 개념정리] 3. 동적계획법(DP)

**본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.**

 

Dynamic Programming

: 전체 문제를 작은 부분 문제(subproblem)로 나누어 푸는 방법
                         -> DP, 분할 정복,...

• 중복되는 부분 문제는 한 번만 계산
• 메모이제이션
  : memoization 배열 -1로 초기화,
    배열 값 음수이면 계산 후 저장, 양수이면 저장해둔 값 재활용
• 기저 조건(Base Case) 설정
• 최적 부분 구조
  : 전체 문제의 최적해가 부분 문제의 최적해로부터 구해짐.
  
  
  
  

★ DP 문제 판별법

1. 문제를 읽는다.
2. 입력 조건 & 시간제한 & 메모리 제한을 확인한다.
   ex) 입력 조건 : 상태 개수를 정의. k=100, n=100000 -> kn=10000000 정의할만하네!
   
3. 상태에 대한 전이(transaction)가 정의되는가? (과거-현재-미래 상태 연결여부)
   현재 상태로부터 다음 상태 정의 가능?
   현재 상태 이용해서 직전 상태 정의 가능?
   전이에 따른 반복 횟수는 큰가 작은가?
4. 부분 문제가 나오는지, 나온다면 그게 겹치는지 확인한다.
   안 겹치면 메모이제이션 필요 없음

-> 그 결과, DP가 아니다?
    그럼 그리디, 분할 정복 등을 생각해보자.

 

★ DP 문제 접근법

1. 최적해의 구조를 정의해본다.
2. 최적해의 값을 정의하기 위한 관계식(점화식)을 짜 본다.
3. 부분 문제부터 최적해를 구해나가며 전체 문제를 구한다.

 

 

관련 문제

2022.01.19 - [PS/Baekjoon] - [백준/C++] 1932번: 정수 삼각형(S1)

2022.01.19 - [PS/Baekjoon] - [백준/C++] 11053번: 가장 긴 증가하는 부분 수열(S2)

2022.01.19 - [PS/Baekjoon] - [백준/C++] 11055번: 가장 큰 증가하는 부분 수열(S2)

2022.01.20 - [PS/Baekjoon] - [백준/C++] 11049번: 행렬 곱셈 순서(G3)

2022.01.21 - [PS/Baekjoon] - [백준/C++] 9177번: 단어 섞기(G4)

2022.01.21 - [PS/Baekjoon] - [백준/C++] 9251번: LCS(G5)