반응형
Dynamic Programming 동적 프로그래밍
동적 프로그래밍에는 문제를 더 작은 문제로 쪼개는 과정을 포함하고 있음.
(작은 문제를 해결해야 그 다음 문제를 해결할 수 있는 구조가 되려나)
동적 프로그래밍은 작은 문제를 해결한 다음 이에 대한 결과를 메모리에 저장해
필요 시 언제든 해결된 문제의 결과에 접근할 수 있게 한다.
(배열이나 객체 등 저장할 수 있는 것을 반드시 포함하겠구나 예상되네)
동적 프로그래밍의 규칙
이미 계산된 값들을 저장하고 해당 값들을 사용해야한다.
(단, 이 방법은 중복 부분 문제와 최적 부분 구조가 존재하는 문제에만 적용할 수 있음)
동적 프로그래밍은 부분 문제의 해결책을 해시 테이블과 배열, 행렬에 저장하며,
이러한 방식을 메모이제이션이라고 부른다.
동적 프로그래밍은 문제 해결 시 중복 부분 문제가 많은 경우 유용하다.
어떤 문제의 최적 해결책을 해당 문제의 부분 문제들의 최적 해결책들을 사용해 찾을 수 있을 때
이를 최적 부분 구조라 한다.
반응형
