자료구조 & 알고리즘
[Algorithm/Java] DP(다이나믹 프로그래밍, 동적 계획법)
다이나믹 프로그래밍 (DP , 동적 계획법) 크고 복잡한 문제를 여러 개의 작고 간단한 문제들로 분리하여 문제를 해결하는 방법이다. 답을 찾아가는 과정에서 작은 문제들을 계산한 결과를 기록하고, 재활용하며 문제의 답을 구하는 방식이다. 중간 계산 결과를 기록하기 위한 메모리가 필요하다. 한번 계산한 부분을 기록해두기 때문에 다시 계산하지 않아서 속도가 빠르다. DP 핵심 원리 DP를 사용하려면 큰 문제를 작은 문제 여러개로 나눌 수 있어야 한다. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다. DP 구현 방법 메모이제이션(memoization) 방법 : 모든 작은 문제들을 한 번만 계산해서 DP 테이블에 저장하여, 그 값들을 재사용하는 방법 타뷸레이션(Tabulati..
