반응형 분류 전체보기340 [알고리즘] 동적 계획법(Dynamic Programming) - 6 동적 계획법(Dynamic Programming) - 6 이번 시간에는 동적 계획법의 또다른 고전 중에 Knapsack Algorithm에 대해 알아보자Knapsack은 배낭을 가리키는 말인데 배낭 알고리즘 이라고도 한다.이 알고리즘에는 재미있는 이야기가 숨어있는데, 도둑이 상점에 물건을 훔치기 위해 배낭 하나를 들고 왔다고 했을 때,가지고 나갈수있는 무게가 한정적이지만 최대의 비용을 낼 수있게 해야한다. 각각의 물건 마다 무게와 가격이 다 다르다.따라서 n개의 아이템과 배낭의 용량 W가 주어질 때배냥의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합을 구해야 한다.. 예를 들어 위의 그림에서 {1,2,5}는 가격의 합이 35,{3,4}는 가격의 합이 40,{3,5}는 가격의 합이46 이지만 배낭의.. 2017. 6. 10. [기술의역사] 파이썬(Python) 파이썬(Python) "인생은 너무짧다. 그래서 파이썬이 필요하다."파이썬은 짧은 코드에서 나오는 효율성 뿐만아니라 들여쓰기로 만들어지는 자동 정렬,어떤 분야든 가리지 않고 닥치는대로 사용할 수있는 범용성 등 많은 무기를 가지고 있다.이 때문인지는 몰라도 2017년 6월 기준 프로그래밍 점유율 수준은 당당하게 4위를 차지하고 있다. (파이썬의 창시자 - 귀도 반 로썸) 파이썬이 최근에 주목받고 있다고 생각할지 모르겠지만 발표시기는 1991년,웹 서비스가 일반인들에게 널리 상용화되기 전에 나온 언어이다.언어를 만든이는 귀도 반 로썸(Guido van Rossom)으로 1989년 크리스마스 주에 연구실이 닫혀있어 심심한 김에 만들었다고 한다.리누스나 귀도 둘다 심심한 김에 걸작을 만들었다는데 있어서, 위대한.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 5 동적 계획법(Dynamic Programming) - 5 이번 시간에는 Longest Common Subsequence를 알아보자Longest Common Subsequence는 줄여서 LCS라고 부르는데, 약어로 부르는것은 그만큼 유명하다는 뜻이다.입력으로 2개의 문자열이 주어지며, bcdb는 문자열 의 subsequence이다.또한 는 문자열 와 의 common subsequence(공통 부분 문자열)이다. 우리가 고려해야할 부분은 LCS인데, 입력으로 2개의 문자열이 주어졌을때, common subsequence중에서 가장 긴것을 찾으면 된다.예를 들어, 는 와 의 LCS가 되는 것이다. 그렇다면 위의 그림에서 x라는 문자열과 y라는 문자열이 입력으로 주어진 문자열이며,z가 우리가 원하는 최적해라고.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 4 동적 계획법(Dynamic Programming) - 4 이번에는 동적 계획법 알고리즘에서 가장 유명한 알고리즘인 Matrix chain multiple을 알아보자이것은 말그대로 두 행렬을 곱하는 알고리즘이다.위의 코드는 pxq인 A 행렬과 qxr인 B 행렬의 곱하기 이다.3개의 반복문으로 돌아가며 곱셈 연산의 횟수는 pqr번이고 결과값은 C에 저장된다. 그러나 우리가 지금 하려는 것은 Matrix chain이다. ABCD의 행렬을 차례로 곱해야 하는 것이다.행렬은 결합 법칙이 성립하므로 계산 순서에 따라서 곱셉 연산의 횟수가 달라진다.그럼 n개의 행렬을 곱할 때 최적의 순서는 무엇일까 이 문제를 동적 계획법으로 접근할때 어떻게 풀어야 하는지를 생각해보면,subproblem으로 나눠서 optimal su.. 2017. 6. 9. 이전 1 ··· 27 28 29 30 31 32 33 ··· 85 다음 반응형
