알고리즘/동적 계획법 (DP)
동적 계획법 (Dynamic Programming)
동적 계획법 (Dynamic Programming) 하나의 문제는 한번만 풀게 하는 알고리즘 메모리 공간을 약간 더 써서 연산 속도를 비약적으로 증가 시킬 수 있음 메모이제이션 - DP를 구현하는 방법 중 하나 - 메모리(배열)에 한 번 구한 결과를 메모해두고 같은 식을 호출하면 그대로 가져옴 (캐싱) 분할 정복과 다른점 : DP는 분할한 문제들이 서로 영향을 미침 DP 구현 방법 탑다운(하향식) 방식 : 재귀를 이용해 DP 푸는 방법 (큰 문제 해결 위해 작은 문제 호출) 보텀업(상향식) 방식 : 반복문 이용해 DP 푸는 방법 (작은 문제부터 답을 도출함) 1. 점화식 찾기 2. dp 값이 정해져 있다면 넣고 시작하기, dp 초깃값은 큰 값 혹은 작은 값 넣기 3. 모든 dp의 값을 (점화식으로 구한 ..
