목록메모이제이션 (1)

넘치게 채우기

[알고리즘] 4. 동적 계획법(Dynamic Programming)

"이미 알고있는 답은 또 구하지 않는다" 사실 전혀 다이나믹하지 않고, 프로그래밍이라고 하기에도 애매하다. 벨만이라는 수학자가 펀딩을 잘 받기 위해서, 눈에 띄는 이름을 지은 것이다. 이광근 교수님의 저서 "컴퓨터과학이 여는 세계"에서는 '기억하며 풀기'라는 이름이 쓰였다. 하나의 큰 문제를 작은 문제로 나누어서, 그 결과를 얻고, 큰 문제의 답을 구하는 방식이다. "분할 정복법"과도 유사하다. 다이나믹 프로그래밍에는 두 가지 방법이 있다: 종류 메모이제이션 타뷸레이션 과정 하향식(Top down) 상향식(Bottom up) 구현 재귀 함수 반복문 장점 직관적이다 시간을 더 아낄 수도 있다 단점 재귀함수의 호출이 잦아 느려질 수 있다. DP테이블을 잘 채워야 한다. 기타 Lazy - Evaluation ..
컴퓨터과학/알고리즘 2023. 4. 29. 02:08
이전 Prev 1 Next 다음