[이것이 취업을 위한 코딩 테스트다 with 파이썬] 6. 다이나믹 프로그래밍
·
Computer Science/자료구조 | 알고리즘
다이나믹 프로그래밍메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장 -> 다시 계산하지 않도록 함다이나믹 프로그래밍의 구현 -> 2가지 방식(탑다운 / 보텀업)조건최적 부분 구조(Optimal Substructure)큰 문제 -> 작은 문제 나눌 수 있음, 작은 문제의 답 모아 -> 큰 문제 해결할 수 있음중복되는 부분 문제(Overlapping Subproblem)동일한 작은 문제를 반복적으로 해결해야 함피보나치(Fibonacci) 수열1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...다이나믹 프로그래밍으로 효과적으로 계산할 수 있음피보나치 수열 -> 점화식으로 표현: $a_n = a_{n-1} + a..
