Tigercow.Door

안녕하세요. 문범우입니다.이번 포스팅부터 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..