다이나믹 프로그래밍 (Dynamic programming)

*동적 계획법
다음과 같은 조건을 만족해야 한다.
1.최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며  
작은 문제의 답을 모아서 큰 문제를 해결할 수 있다
2.중복되는 부분 문제 (Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 한다


*메모이제이션 (Memoization)
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다
한 번 계산한 결과를 메모리 공간에 메모하는 기법이다
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다

*탑다운(하향식) VS 보텀업(상향식)
상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고,
하향식은 맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다
결과 저장용 리스트는 DP 테이블이라고 부른다

*다이나믹 프로그래밍 문제에 접근하는 방법
주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다
가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다
다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해 보자
일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이
큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다

 

*가장 긴 증가하는 수열 LIS(Longest Increasing Subsequence)

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

*배낭 문제 (knapsack problem)
배낭에 담을 수 있는 무게의 최대값이 정해져 있고,
일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때,
가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

연속해서 뽑지 못하는 수열에서 최댓값 찾기
ex)연속으로 3개의 계단을 오르지 못하며 마지막 계단은 무조건 밟아야한다.
    백준 2156, 2579

참고 https://freedeveloper.tistory.com/276

[이것이 코딩 테스트다] 6. 다이나믹 프로그래밍