문제 제기 만약 도둑이 도둑질을 하러 가방을 들고 상점을 들어갔는데 도둑의 입장에서는 배낭의 무게 W 물건의 가치 v 가있다면 W를 넘어서지 않으면서 훔치는 물건의 가격이 최대가 되는 부분집합을 원할 것이다. 우리는 여기서 어떠한 기준을 잡아서 선택할 것이다. 1. 가격이 높은 것 부터 선택 {5, 2, 1}이 될건데 이는 {3, 4} 보다 적은 비율이다. 2. 무게가 가벼운 것부터 선택 {1, 2, 3}이 선택될 건데 이는 적은 가치이다. 3. 단위 무게당 가격이 높은 것 부터 선택 여기서는 1 -> 1 2 -> 3 3 -> 3.6 4 -> 3.8 5 -> 4 가 된다. 여기서도 당연히 안되는 결과가 나온다. 순환식 opt(i, w): 배낭 용량이 w일 때 아이템 1,2,....i로 얻을 수 있는 최대..

행렬경로문제 행렬 경로 문제는 우상단에서 좌하단까지 이동하는 방법이다. 단 오른쪽이나 아래쪽방향으로만 움직일 수 있다. 방문칸에 가중치를 최소화하여 이동해야한다. 위와 같이 해결하는 방법이다. 이 문제를 해결하기 위해 우리는 동적계획법을 사용해야하는데 동적 계획법의 절차는 1. 순환식을 세운다. 2. 순환식을 계산하는 방식이다. (i, j)까지 이동하는 방법의 이전 단계에서는 (i-1, j)이거나 (i, j-1)에서 이동하는 방법이다. 결과가 모두 최선이 되어야 하기 때문에 각각의 상황 (i-1, j)과 (i, j-1)는 최선의 상황이어야 한다. 순환식 mij는 (i, j)의 가중치이다. L[i, j]는 1, 1에서 부터 i, j 까지의 가중치이다. 첫번째 경우는 첫시작이니 당연히 첫번째 값의 값이 나올..

DP는 Dynamic Programming이라는 말은 줄인말이다. Memoization memoization은 같은 계산이 반복 될 때 이를 기록해두어 계산을 진행하지 않고 저장된 값을 불러오는 것이다. fibonacci의 예를 들면 int fibo(int n){ if( n == 1 || n == 2) return 1; else return fibo(n-1) + fibo(n-2); } 일반적인 코드는 위와 같이 작성한다. 하지만 위와 같이 작성되면 단점이 있는데 같은 계산이 반복되는 것이다. 아래의 경우 fib(2), fib(1), fib(3) 등의 재귀 함수가 반복되는 것을 볼 수 있다. 했던 계산식을 계속해서 반복하는 단점이 존재한다. 그래서 아래와 같이 작성을 한다. int fibo(int n){ ..

Prim의 알고리즘 1. 임의의 노드를 출발 노드로 선택한다. 2. 출발 노드를 포함하는 트리를 점점 키워감 3. 매 단계에서 이미 트리에서 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택한다. 실제 실행 순서 실행 해보면 누가 봐도 특별한 어려움이 없을 것이다. 크루스칼이나 프림이나 이론은 별로 어려운 것이 없는 것 같다. 언제나 그렇듯 실제 구현이 문제이다. 가중치가 최소인 엣지 찾기에 대해 논해보겠다. key는 엣지가 가장 작은 정점 파이는 가장 작은 가중치의 도착점이다. 예를 들면 아래와 같다. 가중치가 최소인 엣지를 찾기 보단 key값이 최소인 엣지를 찾는 것이 중요하다. key값이 최소인 엣지를 찾는 것은 적어도 n개 보다 작은 수의 엣지를 봐야함으로 O..

Kruskal 알고리즘 1. 에지들을 가중치가 오름차순으로 정렬한다. 2. 에지들을 그 순서대로 하나씩 선택해간다. 만약 사이클을 이루게 된다면 선택하지 않는다. 3. n-1개의 에지들이 선택되면 종료된다. 위의 그림을 보며 신장트리를 만들어보자! (웨이트가 같은 엣지가 있으면 아무거나 선택해도 된다.) 왜 신장트리가 찾아지고 만들어지는 것일까? 임의의 한단계를 생각해보자! A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자! 두개의 cut에 cross되지 않는 엣지들 중 최소를 고르면 당연히 사이클이 만들어지지 않고 안전하게 연결될 것이다. 그렇고 보니 이론은 정말 간단하다 ! 정렬 후! 사이클 확인! 최소 가중치의 엣지 더하기 순서를 반복하면 되는 것이..

최소 신장 트리는 일반적으로 kruskal Alogorithm과 Prim의 알고리즘으로 이루어져있다. 이 두 알고리즘을 알아보기전에 두 알고리즘은 공통적인 특징을 가지고 있는데 이를 Generic MST라고 한다. Generic MST에 대해 알아보자!!! Generic MST 처음에는 A = 공집합 으로 둔다. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다. (MST의 규칙을 어기지 않는 에지를 찾은 후) 에지의 수 n-1이 될 때 까지 2번을 반복한다. 안전한 엣지 찾기 그럼 위의 알고리즘을 완성하기 위해 안전한 엣지를 찾는 방법에 대해 알아보자 1. 그래프의 정점들을 두 개의 집합 S와 V-S로 분할한 것을 cut(S, V-S)라고 부른다. 2. 에지 (u, v)에 대해서 u가 ..