동적계획법 (1) 썸네일형 리스트형 Dynamic Programming(DP) 알고리즘 - 동적프로그래밍, Python으로 푸는 피보나치 Dynamic Programming 큰 문제를 나누어 작은 문제로 푸는 것 하나의 문제는 단 한 번의 풀이만 한다. Dynamic Programming 과 Recursion(재귀)의 차이점 DP와 재귀는 얼핏보면 '같은 문제가 반복적으로 일어나는 점' 에서 비슷하다고 생각할 수 있다. 하지만, 큰 차이점은 일반적인 재귀를 단순히 사용하면 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 가장 대표적인 예시는 피보나치 함수이다. DP 조건 두 가지 조건을 만족해야 한다. 1. 같은 문제가 반복적으로 발생 2. 최적 부분 구조 동일한 작은 문제들이 반복적으로 일어날 때, 같은 문제는 항상 정답도 같다. 즉, 중복 사용이 가능하다. DP 문제 풀이 방법 모든 작은 문제는 한 번.. 이전 1 다음
