차밍이

목차 1. 정의 동적계획법(Dynamic Programming) "DP"라고 많이 부름 큰 문제를 해결하기 위해, 작은 문제를 부분 부분 해결하여 저장해놓고 사용한다. 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과를 이용해서 상위 문제를 해결한다. Memoization 기법을 사용한다. 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용된다. ex) 피보나치 수열 분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각 문제를 풀면서 다시 합병하여 문제의 해답을 찾는다. 다시 합병한다. 하양식 접근법, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀 함수로 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로..