프로그래밍/알고리즘 (45) 썸네일형 리스트형 동적 계획법(5) - Knapsack Dynamic Programming (5) Knapsack Problem - n개의 물건과 배낭이 있다. - 각 물건은 무게 $w_i$와 가격 $v_i$를 가진다. - 배낭의 용량은 W라고 한다. - 목적 : 배낭의 용량을 초과하지 않는 선에서 가격이 최대가 되는 부분집합을 찾는다. - Ex) 배낭의 용량은 11이라 한다. i = {1, 2, 5}는 가격의 합이 35가 된다. i = {3, 4}는 가격의 합이 40이 된다. i = {3, 5}는 46이 되나 배낭의 용량인 11을 초과하게 된다. - 문제 해결 방식 : Greedy 1) 가격이 높은 것부터 선택한다. 2) 무게가 가벼운 것부터 선택한다. 3) 단위 무게당 가격이 높은 것부터 선택한다. ∴ 단순한 접근으로는 최적의 답을 찾을 수 없게 된다. .. 동적 계획법(4) - 행렬 곱 & LCS Dynamic Programming (4) 행렬의 곱샘- p x q 행렬 A와 q x r 행렬 B를 곱한다.void product (int[][] A, int[][] B, int[][] C) {for (int i = 0; i 이 코드에서 곱셈연산의 횟수는 pqr이 된다. Matrix-Chain 곱하기- 행렬 A는 10 X 100, B는 100 X 5, C는 5 X 50행렬이다.- 세 행렬의 곱 ABC는 두 가지 방법으로 계산할 수 있다. (결합법칙이 성립한다.)(AB)C : 7500번의 곱셈 필요 (.. 동적 계획법 (3) - 퀵정렬 & 최장 경로 Dynamic Programming (3) 동적 계획법 - 일반적으로는 최적화 문제(촤대값 & 최소값, Optimisation Problem) 혹은 카운팅(Counting) 문제에 주로 적용된다. - 주어진 문제에 대한 순환식(Recurrence Equation)을 정의한다. - 정의한 순환식을 Memorization 혹은 Bottom-Up방식으로 변환한다. - Sub Problem들을 풀어 원래의 문제를 푸는 방식이다. 그러한 의미에서 본다면 분할 정복법과도 공통점을 찾을 수 있다. - 분할 정복법에서는 분할된 문제들이 서로 Disjoint하지만, 동적계획법은 그렇지 않다. - 서로 Overlapping하는 sub problem들을 해결함으로 원래의 문제를 해결하게 된다. 분할 정복법 vs 동적 계획법.. 동적 계획법 (2) - 경로 탐색 Dynamic Programming Basic Problem 행렬 경로 문제- 정수들이 저장된 N X N 행렬의 좌상단부터 우하단까지 이동한다. 단 오른쪽 또는 아래 방향으로만 이동이 가능하다.- 방문한 칸에 있는 정수들의 합이 최소화되도록 프로그래밍해라. 행렬 - Key Obervation- (i, j)에 도달하기 위해서는 (i, j - 1)이나 (i - 1, j)를 거쳐야 한다.- 또한 (i, j - 1) 혹은 (i - 1, j)가지는 최선의 방법으로 이동해야 한다. 행렬 - 순환식- L[i, j] : (1, 1)부터 (i, j)까지 도달하는 최소 경로의 길이 합$m_{ij}$는 (i, j)위치에 저장되어 있는 숫자를 의미한다.i와 j가 각각 1일때는 가장 구석에 위치해 있는 것으로 각각 오른쪽과 아.. 동적 계획법 (1) - Fibonacci & Binomial Dynamic Programming (1) Fibonacci Numbersfibonacci (int n) {if (n == 1 || n == 2)return 1;elsereturn fiboncci(n - 2) + fibonacci(n - 1);}- Recursion을 이용하여 피보나치 수를 구하는 과정에서 많은 계산이 중복된다는 문제가 있어 비효율적이다.- 중복 계산을 구하는 방법에는 Caching기법과 Dynamic Programming기법이 있다. Fibonacci - Memorization- 중간 계산 결과를 caching하여 중복 계산하는 문제를 회피하게 된다.fibonacci (int n) {if (n == 1 || n == 2)return 1;else if (f[n] > -1) // 배열 f의.. 압축 (4) 보호되어 있는 글입니다. 압축 (3) Compression (3) HuffmanCoding- Huffman Coding 알고리즘은 트리들의 집합을 유지한다.- 매 단계마다 가장 빈도가 작은 두 트리를 찾는다.- 두 트리를 하나로 합친다. 이 때 부모 노드는 두 자식 노드를 합한 값이다.- 위 연산에 가장 적합한 자료구조는 최소 힙(minimum heap)이다.- 힙에 저장된 각 원소들은 하나의 트리이다. (노드 또는 런이 아니다.) 최소 힙위 트리의 각 구성요소들은 전부 트리들이다. (single node tree) 그렇기 때문에 위 트리는 5개의 single node tree가 있다고 할 수 있다. 왼쪽 트리는 개념적인 구조이며 오른쪽 배열은 트리를 실제로 구현한 것이다.extractMin작업을 하게 될 경우 루트가 항상 가장 작기 때문에.. 압축 (2) Compression (2) Huffman Method with Run-Length Encoding- Huffman과 Run-Length를 적절히 결합한 알고리즘이다.- 파일을 구성하는 각 런들을 하나의 super-symbol로 본다. 그 후 이들에 대해 Huffman Coding을 적용하게 된다.- Ex) 문자열 AAABAACCAABA는 5개의 super-symbol인 AAA, B, AA, CC, A로 구성된다.위 그림은 각 슈퍼 심볼의 빈도와 길이를 표시한 테이블이다. Run과 Frequency 찾기- 압축할 파일을 처음부터 끝까지 읽어 파일을 구성하는 런들과 이들 각각의 등장횟수를 구한다.- 각 런들을 표현할 하나의 class Run을 우선 정의한다. 클래스 run은 적어도 세개의 데이터 맴버인 s.. 이전 1 2 3 4 ··· 6 다음
