LCS (1) 썸네일형 리스트형 다이나믹 프로그래밍 Dynamic Programming 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming의 개념 큰 문제를 작은 문제로 나누어 문제를 푸는 기법 divide and conquer 기법과 달리 작은 문제의 중복이 발생하지 않는다. 분할된 모든 작은 문제들은 한번만 풀어야 하기 때문에 작은 문제의 정답은 구한 뒤 메모해 둔다. 그리고 큰 문제를 풀다가 동일한 작은 문제가 나타나면 앞에 메모한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복적으로 일어나는 경우 같은 문제를 구할 때마다 결과값이 같은 경우 메모이제이션 Memoization 한번 계산한 작은 문제의 결과값을 저장해두는 것 Bottom-up 구현 def fibonacci_bottom_up(n): if .. 이전 1 다음