The 0-1 Knapsack Problem 백트래킹으로 해결하기 노드의 첫 번째 줄: 현재 가방에 들어온 물건들의 가치 합 두 번째 줄: 현재 가방에 들어온 물건들의 무게 합 세번째 줄: 현재 상태에서 최대 가치의 upper bound -> upper bound는 물건을 쪼갤 수 있다는 가정을 통해 얻을 수 있다 public static void knapsack(index i, int profit, int weight) { if ( weight maxProfit ) { maxProfit = profit ; //현재까지 최대이익 numBest = i ; bestSet = include ; } if (promising(i)) { include[i+1] = “yes” ; //i+1번째 아이템 추가했다고 표시..

The m-coloring problem adjacent(인접한) 두 vertice가 같은 색이 되지 않도록 최대 m의 다른 색을 사용하여 undirected graph를 색칠하는 모든 방법을 찾는 문제 * 지도 문제로 적용될 수 있다. public static void m_coloring(index i) { int color ; if (promising(i)) if (i==n) system.out.print( vcolor[1] .. vcolor[n] ) else for (color=1; color

백트래킹 모든 경우를 보다가 해가 아닐 것 같으면 가지치기(prune)하며 되돌아간다. N queens problem : N*N 체스판에 n개의 퀸을 어느 두개의 퀸이 서로를 위협하지 않도록 배치하는 문제 sequence: queens을 놓을 n개의 자리 set: 체스판의 총 자리 -> n^2 criterion: 어느 두개의 퀸이 서로 위협하지 않도록 -> 같은 줄이나 같은 대각선에 있으면 안됨 (퀸은 대각선, 앞,뒤,옆으로 칸갯수 제한 없이 이동 가능 ) 예) 4 queens problem 골라야 하는 경우의 수: C(16,4)=1820 같은 행에 두면 안되므로 -> 4* 4* 4* 4=256가지 경우의 수가 줄어듦 백트래킹을 이용해 N-queens problem 해결하기 1. dfs 알고리즘으로 트리..

The 0-1 Knapsack Problem n개의 items이 있을 때 S는 item들의 집합 wi는 i번째 item의 무게 pi는 i번째 iteml의 가치 W는 배낭에 담을 수 있는 최대 무게 -> item들을 배낭에 담아 최대의 가치를 만들도록 하는 것이 이 문제의 핵심 브루트포스로 해결하기 1. 모든 가능한 경우를 고려 2. 최대 무게를 넘는 경우는 버리기 3. 남아있는 것들 최대의 가치를 만드는 것을 선택 -> 탐색하는데 2^n번의 시간이 걸림 그리디로 해결하기 1. (1) 가치 순서대로 아이템들 정렬 (2) 좋은 가치 순서대로 가방에 담기 (3) 더 이상 못 담으면 종료 -> 최적해를 얻지 못함 2. (1) 가벼운 순서대로 아이템들 정렬 (2) 가벼운 순서대로 가방에 담기 (3) 더 이상 못담..

Huffman Code 데이터 압축을 위한 효율적인 encoding 방법 text file을 표현하는데 variable-length binary code를 사용한다. * variable-length binary code -> 가변 길이 바이너리 코드: 다른 길이의 비트를 사용하여 각 문자를 표현 * Fixed-length binary code -> 고정 길이 바이너리 코드: 같은 길이의 비트를 사용하여 각 문자를 표현 예) 아스키 코드 * Prefix Code 어느 코드도 다른 코드의 앞부분에 있지 않게 구성한 코드 Huffman Code란 결국? -> prefix code이면서 가변길이 바이너리 코드인 코드를 최적이 되도록 (문자 v가 나올 빈도 * 문자 v의 비트 길이)의 최소를 찾는 게 Huffma..

정의 일련의 선택을 함으로써 해결책에 도달 각 선택은 현재단계의 최적 9 -> 전체적으로 최적은 아님 구현 순서 1. Selection Procedure 기준에 따라 아이템을 선택해 집합에 추가하기 2. Feasibility Check 집합에 넣어도 되는지 안되는지 체크하기 3. Solution Check 완성된 집합이 solution이 맞는지 아닌지 결정하기 Minimum Spanning Trees * Acyclic Graph : cycle이 없는 그래프 *Tree: acycli, connected, undirected 한 그래프 (자료구조 트리와는 다름) * Spanning Tree: 주어진 그래프의 모든 vertice를 포함하여 연결시킨 subgraph * Minimum Spanning Tree: ..