java algorithm (1) 썸네일형 리스트형 [코딩테스트][알고리즘] 4. DP( Dynamic Programming) 다이나믹 프로그래밍 다이나믹프로그래밍의 기본적인 아이디어는 한 번 풀었던 문제를 다시 풀지 말자! 라는 것이다. 풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다. 이러한 과정을 메모이제이션(Memoization) 이라고한다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다. DP는 분할정복기법( 해결했던 문제도 다시 계산 )을 개선 한 것 인데, 대표적인 예가 피보나치수열을 구하는 것이다. 피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2] 의 공식에 의해 진행되는 수들의 나열이다. 분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.. 이전 1 다음