dynamic programming (1) 썸네일형 리스트형 Dynamic Programming에 대하여 Dynamic Programming(이하 동적계획법)은 Divide and Conquer(이하 분할정복법)와 같이 문제를 작은 문제들로 나누어 연산을 반복해 최종 해답을 얻는 방식이다. 하지만 분할정복법과 다른 부분은 바로 Memoization을 사용한다는 것이다. 즉, 분할정복법에서는 작게 나눈 문제가 중복될 경우 낭비가 발생하지만 동적계획법은 값을 저장함으로서 중복된 문제를 풀때의 낭비가 없도록 한다. 대표적인 예시로는 피보나치 수열이 있겠다. fun fibo(n): Long { if(n == 1) return 1 else if(n == 2) return 1 else return fibo(n-1) + fibo(n-2) } 아주 대표적인 피보나치 수열의 값을 얻는 함수이다. 위처럼 작성하면 굉장히 간단.. 이전 1 다음