💻Algorithm/이론
2022. 4. 18.
동적 계획 알고리즘(DP/Dynamic Programming)
동적 계획 알고리즘(DP) 주어진 문제를 부분 문제로 나누어서 푼 다음, 그 결과로 주어진 문제를 푸는 방법 부분 문제의 정보를 저장->시공간적 효율 증가 memoization 활용 최적 부분 구조(기본 문제의 최적해가 부분 문제의 최적해를 포함) DP 적용 여부 판단 방법 1.문제를 같은 형태의 하위 구조로 나눌 수 있는가 2.하위 문제의 계산이 반복되는가 (최적화, 최대화, 최소화, 어떡 작업의 경우의 수를 구하는 문제인가 *애매한 경우에 참고할 수 있는 대표적인 DP 문제 유형) DP 적용 과정 1. 점화식 / 재귀 과정 정의 - 문제를 Top-Down(하향식/재귀) 으로 정의한다 - 문제 풀이에 필요한 기본적인 문제의 하위 부분 값을 초기화 - 종료 조건 추가 2. memoization 적용 3...
