728x90
반응형

동적 프로그래밍 6

알고리즘 #8_ 최장 공통 부분 수열(LCS: Longest Common Subsequence)

안녕하세요.이번 포스팅에서는 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보도록 하겠습니다.궁금하신 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)1. 최장 공통 부분 수열(LCS: Longest Common Subsequence) 먼저 최장 공통 부분 수열이 어떠한 것인지 알아보도록 하겠습니다.문제를 이해하기 위해 다음을 가정합니다. X = Y = 이러한 두 수열 X, Y가 있습니다. 이때, 는 X와 Y의 공통 부분 수열입니다.X = Y = 위에서 X 수열과 Y 수열에 밑줄을 쳐놓은 부분을 통해 는 X와 Y의 공통 부분 수열이라는 것을 알 수 있습니다.꼭 연결되어 있어야 하는 것이 아니며, 단지 단조 증가하는 수열로써 존재하면 되는 것이죠.그렇다면 ..

알고리즘 #7_ 동적 프로그래밍: 동적 프로그래밍의 요소

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

알고리즘 #6_ 동적 프로그래밍: 행렬 체인 곱셈(Matrix-chain Multiplication)

이번 포스팅에서는 동적 프로그래밍의 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서 알아보도록 하겠습니다.1. 행렬 체인 곱셈(Matrix-chain Multiplication) 이번 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)문제는 n개의 행렬을 곱하는 것에 대한 문제입니다.먼저 행렬의 곱은 아래의 수도코드와 같은 방식으로 진행됩니다. 위의 수도코드를 보면 A행렬이 p*q이고 B행렬이 q*r일때, 이 두 행렬의 곱을 통한 새로운 행렬 C를 계산하는데 걸리는 시간은 수도코드의 8행에 따른 곱셈의 횟수, pqr번에 의해서 결정됩니다.예를들어, 아래와 같은 세개의 행렬이 있을 때, 두가지 방법의 곱셈이 가능할 것입니다. A1와 ..

알고리즘 #5_ 동적 프로그래밍: Assembly Line Scheduling

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

알고리즘 #4_ 파이썬을 통한 막대자르기(Rod cut) 시간비교

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

알고리즘 #3_동적 프로그래밍: 막대 자르기(rod cut algorithm)

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

728x90
반응형