Tigercow.Door

안녕하세요.우리는 지난 포스팅들을 통해서 동적 프로그래밍(Dynamic programming)의 3가지 예시에 대해 살펴보았습니다.이번 포스팅에서는 예시들과 같은 최적화 문제에 동적 프로그래밍을 적용하기 위해 가져야 하는 두 가지 중요한 구성요소,최적 부분 구조와 중복되는 부분 문제에 대해 살펴보도록 하겠습니다.어떤 문제에 대해서 동적 프로그래밍을 적용하기 위해서 해당 문제가 가져야 할 두 가지 구성요소는,최적 부분구조와 중복되는 부분 문제입니다. 하나씩 자세히 살펴보도록 하겠습니다. 1. 최적 부분 구조(Optimal substructure) 동적 프로그래밍을 적용하기 위해 가장 먼저 확인해야 할 것은 최적해의 구조의 특징입니다.기본 문제의 최적해가 부분 문제의 최적해를 포함하고 있을 때, 우리는 그 ..

안녕하세요. 이번 포스팅에서는 동적 프로그래밍(Dynamic Programming)의 예제인 Assembly Line Scheduling과 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다. 동적 프로그래밍과 막대자르기(Rod-Cutting)예제에 대한 내용은 지난포스트를 확인해주시길 바랍니다.1. Assembly Line Scheduling 먼저 Assembly Line Scheduling 예제에 대한 설명을 하겠습니다. 위와 같은 사진을 참고하여 어느 특정 공장에 두 개의 라인이 있습니다.그림에서는 위의 라인이 S1, 아래의 라인이 S2입니다.그리고 각각의 라인에서 진행되는 1부터 n까지의 공정이 있습니다.이때 같은 열에 있는 공정은 같은 공정이지만 라인에 따른 시간차이..

지난 포스팅에서 동적 프로그래밍(Dynamic Programming)에 대해서 알아보고 그에 대한 예제로 막대자르기(Rod Cut)에 대해서 공부하였습니다.이번 포스트에서는 막대자르기 예제에서 단순 하향식 재귀표현법과 상향식 방법을 실제로 python코드로 작성해보고 시간을 비교해보도록 하겠습니다.1. 개요 먼저 이번 포스팅에서 진행할 막대자르기문제에 대한 몇 가지 조건은 아래와 같습니다. ㄱ. P-table(price table)의 값은 임의의 단조증가 형태ㄴ. Rod의 길이 값을 4부터 N으로 변화시키면서 Brute-force방법(하향식 재귀 표현)과 DP방법(상향식 방법)으로 최적의 값과 해결 소요 시간을 비교ㄷ. 소요 시간 비교는 최종적으로 표와 그래프를 이용하여 시각적으로 표현 위의 조건들을 가..

안녕하세요. 문범우입니다.이번 포스팅부터 Introduction to Algorithm (3rd Edition) 책의 15장. 동적 프로그래밍(ch15, dynamic programming)에 대해서 이야기하려 합니다.매주 1~2번 정도 포스팅 될 예정이며, 공부를 하면서 내용을 정리해서 올리기 때문에 잘못된 정보나 지식이 포함되어 있을 수 있으니 참고용으로 확인해주시고, 잘못된 내용에 대해서는 피드백 주시면 감사하겠습니다.오늘은 동적 프로그래밍에 대한 개요와 동적 프로그래밍의 막대 자르기(Rod Cut)에 대해서 알아보겠습니다.1. 동적 프로그래밍(Dynamic programming) 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합하여 문제를 해결합니다.이때, 프로그래밍이란 것은 코딩을 ..