Algorithm/다이나믹 프로그래밍 (4) 썸네일형 리스트형 Dynamic Programming Dynamic Programming 다이나믹 프로그래밍은 특정 알고리즘이 아닌 디자인 패러다임입니다. 우리가 알고 있는 이러한 디자인 패러다임은 분할 정복, 백트레킹 등이 있습니다. 최적화 문제: optimal value를 찾는 솔루션, 최대화 최소화 문제 우리는 최적의 선택을 모른다. 따라서 우리는 미리 계산한 하위 문제의 비용을 기반으로 하위 문제를 모두 시도한다. 우리가 내리는 선택에 따라 해결해야 할 하위 문제가 결정된다. 최적화 예시 최단거리 문제: 포항에서 서울까지가는 길은 많습니다. 최단 경로, 가장 경치 좋은 경로, 가장 빠른 경로를 계산하려고합니다. 잡 스케줄링: 여러 프로세서에서 작업 세트를 예약하는 방법에는 여러 가지가 있습니다. 프로세서의 다양한 기능과 작업의 다양한 리소스 요구 사.. [DP] Knapsack problem Knapsack Problem 도둑이 박물관에 침입했습니다. 멋진 그림, 조각품, 보석이 사방에 있습니다. 도둑은 이러한 물건의 가치를 잘 알고 있으며, 각각 이 진귀한 물건들이 시장에서 수백 또는 수천 달러에 거래 되는 것도 잘 알고 있습니다. 그러나 도둑은 현장에 배낭 하나만 가져 왔고, 가방의 수용량 만큼만 가지고 나갈 수 있습니다. 도둑은 가치를 극대화하기 위해 어떤 품목을 가져 가야합니까? 문제에는 두가지 버전이 있습니다. 1. Fraction knapsack problem 2. 0-1 knapsack problem 차이점은 보물을 가루로 만들어 일부만 취할 수 있는지 없는지 여부입니다. 1번의 경우에는 그리디 알고리즘으로 간단하게 해결이 가능합니다. 각 항목에 대해 파운드당 가치를 계산합니다... [DP] Multiply Chain Matrix Algorithm Multiply Chain Matrix Algorithm MCM algorithm이란? 두 개 이상의 행렬을 곱할 때, 곱하기 연산을 최소로 할 수 있게 적절히 계산 순서를 바꿔주는 문제이다. 행렬의 곱셈은 다음과 같이 결합법칙이 성립된다. A x B x C = (A x B) x C = A x (B x C) 하지만 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라지게 된다. 예를 들어, A = 20 x 1, B = 1 x 30, C = 30 x 10, D = 10 x 10 의 크기를 가진 행렬들이 있다고 가정하자 A x B x C x D의 값을 구하려면 적절히 괄호를 쳐서 아래와 같은 경우의 수를 만들 수 있다. ((A x B) x C ) x D) = (20 x 1 x 30) + (20 x 30 x 10) .. [DP] LCS (Longest Common Subsequence) Substring vs Subsequence substring: 연속되고 진행 순서도 맞는 부분 문자열 subsequence: 연속적이지는 않지만 진행 순서는 맞는 부분 문자열 ex) Iamhungry substring: "mhun" subsequence: "mugy" LCS의 길이 구하기 예시로 설명하는게 편하기 때문에 예시를 하나 들어보겠다. 문자열 ACAYKP와 CAPCAK가 있다고 가정해보자. ACAYKP 를 기준 string으로, CAPCAK를 비교 String으로 두자. 그렇다면, 아래의 표와 같은 모양이 생성된다. 첫 번째로 할일은 문자열 맨 앞에 0을 추가해 첫번째 행과 열을 모두 0으로 만드는 것이다. 이유는 나중에 LCS를 찾을 때 0이 되면 반복문을 종료하기 위해서이다. 여기가 (0,.. 이전 1 다음