| [ QuizWit ] in KIDS 글 쓴 이(By): ash ( [@_@]) 날 짜 (Date): 1999년 10월 14일 목요일 오후 12시 04분 11초 제 목(Title): Re: [Q] TSP 를 다이나믹 프로그래밍으로 재귀 호출로 피보나치 수열을 구할 수 없다는 말이 아니라. 그렇게 구하면 안된다는 말이었습니다. p(n) = p(n-1) + p(n-2) 를 재귀 호출로 돌리면 p(5) - p(4) - p(3) - p(2) - p(1) - p(0) - p(1) - p(2) - p(1) - p(0) - p(3) - p(2) - p(1) - p(0) - p(1) 위처럼 됩니다. p(5) 를 구하기 위해서 p(2) 가 세 번 호출되지요? p(n) 에서 n 이 커질 수록 p(2) 가 호출되는 회수가 굉장히 많아지게 됩니다. 이터레이션으로 하면 p(2) 는 한번만 계산하면 됩니다. 이런 경우에는 재귀 호출을 사용하면 안됩니다. TSP 를 다이나믹 프로그래밍으로 구현할 때도 마찬가지 입니다. |