[ 다이나믹 프로그래밍 = 동적계획법 ] 알고리즘 내용 정리

😃 동적계획법 ( Dynamic Programming )

- 전체 문제를 작은 부분 문제로 나누어 푸는 방법

- 한 번 계산한 결과를 재활용하는 알고리즘 ( 중복되는 부분을 한번만 계산하도록 ) 

 

😃 동적 계획법 조건

1. 최적 부분 구조 : 부분 문제의 최적을 이용해 지존의 답을 구하는 구조!

출처 : https://hongjw1938.tistory.com/47

 

2. 중복되는 부분 문제

출처 : https://hongjw1938.tistory.com/47

 

😃 동적 문제 방식

1. Memoization   - 하향식 

- 중복되는 계산을 한번한 뒤 메모해두는 방식 

- cache에 저장하고 보통 재귀함수 사용

- 배열 값을 -1로 모두 초기화, 배열 값이 음수이면 계산한 후 저장, 양수이면 그대로 활용

 

2. Tabulation - 상향식

- 반복문 기반으로 해결하는 방식 ( 누적시켜 전체 큰 문제를 해결 )

 

😃 동적 계획법 문제 접근방식

1. 동적 계획법으로 풀 수 있는 문제인지 확인한다. 

2. 문제의 변수를 파악한다. 

3. 변수 간의 관계식을 만든다. * 점화식*

4. 메모한다.

5. 기저 상태 파악한다. = 가장 작은 문제의 상태를 파악 후 저장한다.

6. 구현한다. 

 

🎯 관련 문제

1. 백준 11726 - 2*n 타일링 : https://www.acmicpc.net/problem/11726

핵심 아이디어 : 길이가 1인거 추가 가능, 길이가 2인거 추가 가능! ( -1,-2일 때의 경우의 수를! 사용 )

 

2. 백준 15990 - 1,2,3 더하기 5 : https://www.acmicpc.net/problem/15990

핵심 아이디어 : 연속중복이 안되므로 마지막에 사용된 숫자를 기록

 

3. 백준 11053 - 가장 긴 증가하는 부분 수열 : https://www.acmicpc.net/problem/11053

핵심 아이디어 : LIS 알고리즘 - 최장 증가 부분 수열 : https://4legs-study.tistory.com/106

* 최장 증가 부분 수열 :  어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미 *

 

🎯 문제 풀어보기

- https://www.acmicpc.net/workbook/view/9376

문제집: 코딩 테스트 준비 - 기초 (code.plus)

 

- https://www.acmicpc.net/workbook/view/9377

문제집: 코딩 테스트 준비 - 기초 (code.plus)

 

---