PS 이야기

유용한 링크: MIT 강의 자료 어떤 문자열이 있고, 각 알파벳에 바이너리를 할당한다. 할당된 바이너리는 어떤 것이 다른 것의 prefix가 되면 안 된다. 문자열을 알파벳에 할당된 바이너리로 표현할 때 바이너리의 크기를 최소화하는 문제가 있다. 이는 매우 일반적인 압축 알고리즘을 필요로 하는 상황이다. Huffman Coding은 이 문제에 대한 최적해를 $O(N \lg N)$ 시간에 구한다. 각색은 다르지만, Huffman Coding과 같은 상황인 문제는 BOJ 13975번 파일 합치기 3이 있다. Huffman coding - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Technique to c..

유용한 링크: 위키백과, Skew heap visualization, NTU 강의자료 Skew heap(혹은 self-adjusting heap)은 이진트리로 구현된 힙 자료구조다. 우리가 배운 기본적인 힙은 완전이진트리이므로 배열과 인덱스를 이용하여 편하게 구현이 가능하다. 그러나, Skew heap은 완전이진트리가 아닌 그냥 이진트리이므로 배열을 이용한 구현을 할 수 없다. 그렇다면, 일반 힙이 아닌 Skew heap이 필요한 순간은 언제일까? 바로, 서로 다른 두 힙을 하나로 빠르게 합치고 싶은 순간에 쓸 수 있다. 서로 다른 두 힙을 하나로 합치는 것을 merge 연산이라고 한다. Skew heap은 merge 연산 중간, 왼쪽 자식과 오른쪽 자식을 무조건적으로 바꿔주어 균형을 유지한다. 이 me..