동적프로그래밍, 동적계획법, Dynamic Programming
다음 글은 '코딩인터뷰 완전분석'이라는 책을 정리한 글입니다. 문제가 있거나, 잘못된 부분이 있다면 댓글로 남겨주세요!동적프로그래밍이란? 동적 프로그래밍은 반복적으로 호출되는 부분을 찾아 나중을 위해 결과를 캐시에 저장해 놓는 알고리즘 방식이다. 재귀법으로 구현해보기 피보나치 수열을 예제로 들어보자. 만약 재귀법으로 구현을 한다면 다음과 같을 것이다. int fibonacci(int i) { if (i == 0) return 0; if (i == 1) return 1; return fibonacci(i-1) + fibonacci(i-2); } 하지만, 재귀법으로 구현을 할시 N번째 피보나치 수를 생성하는 데 걸리는 시간이 N이 커짐에 따라 기하급수적으로 증가하므로, 최적화할 방법이 필요하다. 하향식 동적..
알고리즘
2018. 9. 27. 23:20