문제 해결 알고리즘 기초/동적 계획 (9) 썸네일형 리스트형 동적 계획법에 대해서, 이항 계수 문제 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 동적 계획법 기본적으로 문제를 작은 문제로 나누어 계산한 것으로 원래 문제의 답을 계산한다. (분할 정복과 같은 접근 방식) 이 과정에서 어떤 부분 문제는 두 개 이상의 더 큰 문제를 푸는데 사용된다. 즉, 같은 계산이 여러번 반복된다. 계산의 중복 횟수는 분할의 깊이가 깊을수록 지수적으로 증가하므로 (Combinational Explosion) 알고리즘의 속도 개선을 위해 꼭 해결해야 한다. 동적 계획법에선는 각 부분 문제의 계산 결과를 저장한 뒤 필요할 때 사용하여 중복 계산을 막는다. 이를 Memoization 이라 하는데, Memoization 은 입력이 고정될 때 결과가 항상 같은 함수에만 적용 가능하다. (참조적 투명 함수, 함수의.. 이전 1 2 다음