tonirr

동적프로그래밍 동적프로그래밍 방법의 원리 문제의 크기가 작은 소문제에 대한 해를 저장해놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근방법 각각의 소문제는 원래의 문제와 동일하지만 입력의 크기만 줄어듦 입력의 크기가 아주작은 단순한 문제가 되면 쉽게 해를 구할 수 있고 이런 소문제의 해는 다시 사용될 수 있으므로 테이블에 저장 해당 소문제의 해가 필요할 때마다 테이블에서 결과를 바로 이용 동적 프로그래밍(동적 계획법) 해를 구축하는 테이블을 이용함 최적화 문제에 사용됨(최소값, 최대값 찾기) 분할 정복 방법 하향식 접근 방법 상위 레벨의 큰 문제를 순환적으로 부분배열로 분할하고 이들의 해를 결합해서 원래 문제의 해결하는 방법 분할된 작은 문제들은 서로 독립적 이진탐색, ..