with with

0-1 Knapsack Promble은 각각의 가치(profit)와 무게(weight)를 갖는 여러 아이템을 가방에 추가하는데, 최대 가방이 담을 수 있는 무게를 초과하지 않는 범위에서 아이템의 가치가 최대가 되도록하는 아이템의 집합을 찾는 알고리즘이다. 이 문제를 접근하는 방법은 여러개가 있어 한 번에 소개해보고자 한다. Greedy Approach 그리디한 방법으로 해결하는 접근방식은 다음과 같다. 단위무게당 가격으로 내림차순 정렬을 하고, 무게가 가득 찰 때 까지 집어넣는 방식이다. 하지만 이 방식에는 문제가 존재한다. 바로 항상 최적해를 도출하지는 못한다는 것이다. 단, fractional knapsack problem의 경우에는 그리디한 방법으로도 최적해를 도출할 수 있다. (fractional..

Huffman Code는 데이터를 압축하는데 있어 효과적인 인코딩 방법으로, 텍스트 파일을 가변길이의 이진코드로 변환하는데 사용된다. 예로 들어 허프만 코드로 a: 10, b: 0, c: 11로 변환한다면 ababcbbbc는 1001001100011로 변환된다. ababcbbbc는 9bytes 즉, 72bit를 사용해서 저장해야 하지만, 허프만 체계로 변환된 1001001100011은 13bit면 저장이 가능하다. (복호화에 필요한 헤더 제외) a: 10, b: 0, c: 11와 같은 코드로 변환할 때는 prefix code로 변환해야만 한다. prefix code란, 어떤 문자를 나타내는 코드는 다른 문자를 나타내는 코드의 앞 부분과 반드시 다른 코드체계를 의미한다. prefix code로 구성해야지만..

Prim's Algorithm Minimum Spanning Tree Greedy 알고리즘의 예시인 Prim's Algorithm을 살펴보기 전에 그 알고리즘이 다루는 Minimum Spanning Tree의 정의부터 알아보자. - Tree Graph 구조에서 cycle 구조가 존재하지 않고, 연결되지 않 with611.tistory.com 저번에는 Prim's Algoritm을 이용해서 graph에서 minimum spanning tree를 구하는 방법을 알아봤다. Kruskal's Algorithm역시 graph에서 minimum spanning tree를 구하는 알고리즘이지만, 접근 방식에서 약간의 차이가 있다. Prim 알고리즘은 vertex를 중심으로 설계했다면, Kruskal 알고리즘은 edg..

Minimum Spanning Tree Greedy 알고리즘의 예시인 Prim's Algorithm을 살펴보기 전에 그 알고리즘이 다루는 Minimum Spanning Tree의 정의부터 알아보자. - Tree Graph 구조에서 cycle 구조가 존재하지 않고, 연결되지 않은 vertex가 없고, edge에 방향성이 없는 그래프. - Spanning Tree 오리지널 Tree의 부분 트리. 즉, 오리지널 Tree에서 일부 edge가 없는 트리를 의미한다. - Minimum Spanning Tree Spanning Tree 중, edge의 weight의 합이 최소가 되는 트리. G1이 오리지널 트리라 했을 때, G4, G5만이 G1의 Minimum Spanning Tree이다. G2의 경우에는 G1에 S..