동적 계획법 알고리즘 문제풀이 기초와 예제(Assembly-line scheduling)
우선 동적계획법에 대한 기본 설명과 대표적 문제 4개(Assembly-line scheduling, Rod cutting, Lcs, Matrix-chain multiplication)에 대한 소개는 ( http://www.leafcats.com/71 ) 을 참고 바란다. 이 글을 읽기 전 저 링크를 먼저 읽고 접근하는 것이 좋을 것이다. 이번 글에서는 Assembly-line scheduling에 대해 풀어 볼 것이다. 간단하게 요약해 동적계획법이란 복잡한 문제를 푸는 알고리즘의 한 종류로서, 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결 한뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다.피보나치 수열을 예로 들어보자. 피보나치 수열은 아래와 같이 표현할 수 있을 것이다. 하나의 수열 항목을..
