동적프로그래밍

동적 프로그래밍 (Dynamic Programming) : 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 목적 수행 시간을 단축하고자 만든 알고리즘 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도 개선 메모리 사용: 배열 또는 자료구조 생성 중복 연산 줄임 : 한 번 연산한 결과를 배열에 저장 푸는 과정 테이블 정의하기 점화식 찾기 초기값 정하기 구현 방법 1. Memoization 중복되는 계산은 한 번만 계산 후 메모 하향식 접근 (Top-down), 재귀 기반 코드 한 번 계산 후 저장해놓고, 저장해둔 결과를 꺼내서 사용하며 구현 2. Tabulati..