Tigercow.Door

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

안녕하세요. 이번 포스팅에서는 동적 프로그래밍(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) 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합하여 문제를 해결합니다.이때, 프로그래밍이란 것은 코딩을 ..

안녕하세요.이번에는 python을 이용한 CSP algorithm 중 하나인 Einstein's puzzle(아인슈타인 퍼즐) 해결 코드를 작성해 보겠습니다. 먼저 아인슈타인 퍼즐에 대해 소개해 드릴게요.아인슈타인의 퍼즐은 아래와 같은 문제입니다. * 문제의 배경1. 색깔이 서로 다른 5채의 집이 일렬로 지어져 있다.2. 각 집에는 서로 다른 국적의 사람이 살고 있다.3. 다섯 사람은 서로 다른 음료를 마시고, 서로 다른 담배를 피며, 서로 다른 동물을 기른다. * 15개의 정보1. 영국인은 빨간 집에서 산다.2. 스웨덴인은 개를 기른다.3. 덴마크인은 차를 마신다.4. 초록집은 하얀집의 왼쪽 집이다.5. 초록집에 사는 사람은 커피를 마신다.6. 펠몰 담배를 피는 사람은 새를 기른다.7. 노란집에 사는 ..

많은 사람들에게 유명한 missionaries and cannibals problem (선교사와 식인종 문제) 강의 왼쪽에 선교사 3명과 식인종 3명이 있고 모두를 강 오른쪽으로 건너게끔 해야한다. 1. 강의 왼쪽이나 오른쪽에서 선교사의 수보다 식인종의 수가 많으면 안된다. 2. 보트에는 최대 2명이 탑승할 수 있으며 최소1명이 탑승해야 움직일 수 있다. 학교 AI시간에 각 state와 action에 대해서 제출하라는 과제가 있었는데 그것을 통해 DFS algorithm을 응용하여 python으로 구현해보았다. 분명히 잘못된 부분이나 부족한 부분이 있을 것 같은데 일단 포스팅을 진행하고 천천히 더 공부해야 겠다. 123456789101112131415161718192021222324252627282930..