본문 바로가기

IT/Algorithm16

Heap Heap은 Recursively하게 다음과 같은 속성을 가지고 있다.- Max Heap 일 때 : C 노드가 있을 때, P가 C의 부모 노드라면 P의 값은 C보다 같거나 커야 한다. (C = P)(여기서 P는 부모가 없는 노드로 루트 노드라 일컫는다.) 이렇듯 Heap은 위와 같은 속성을 지닌 "트리" 기반의 자료 구조이다. (일반적으로 Heap의 트리는 완전한 바이너리 트리(Binary Tree)를 사용한다.)또한 Heap은 우선 순위 큐(Priority Queue)로도 볼 수 있는데 우선 순위 큐 방식이 Heap과 동일하게 가장 높은 값을 루트 노드에 놓거나 가장 작은 값을 루트 노드에 놓기 떄문이다.다만 Heap이 바이너리 트리를 사용하기도 하고 무조건 루트를 사용하므로 정렬이 되어있다고 할 수는 .. 2019. 5. 27.
Floyd Warshall 출처 : https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/ Graph 알고리즘 중 하나인 Floyd Warshall 알고리즘에 대해 알아보려고 한다.Floyd Warshall 알고리즘은 가중치 있는 그래프에서 각 정점간의 페어 중 가장 짧은 길이를 찾는 알고리즘이다. 그렇다고 친절하게 가장 짧은 정점을 알려주는 것은 아니고 아래의 예시에서 볼 수 있듯이, 정점과 정점간의 가장 짧은 길이만 계산한다. Input: graph[][] = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} } which represents the following graph 10 (0)-.. 2019. 3. 6.
LZW Compression 이번 포스팅에서는 LZW 압축 알고리즘에 대해 알아보려고 한다. LZW 알고리즘은 Lempel-Ziv-Welch(사람 이름)*의 약자로 무손실 압축 알고리즘이다.* Lempel-Ziv가 만든 LZ78 알고리즘을 개선한 것이다.이 LZW 압축 알고리즘은 단순해서 GIF, TIFF와 같은 파일에 주로 사용되지만 Unix에서 단순 파일을 압축하는 용도로도 많이 사용된다. 그럼 본격적으로 LZW에 대해 살펴보기 전에 간단한 핵심 아이디어를 살펴보면 데이터 공간을 절약하기 위해 패턴을 만들어서 재사용한다. 사실 압축 알고리즘이 패턴을 사용하는 것은 일반적이긴 한데 어떻게 패턴을 만들어서 사용하는지 아래에서 더 자세히 살펴보도록 하자. 일반적으로 ASCII 코드는 각 문자를 8비트로 나타낸다. 때문에 최대 표현할 .. 2019. 2. 18.
허프만 코드 (Huffman Code) 허프만 코드 (Huffman Code)는 최적 프리픽스 (Optimal prefix codes)를 사용하여 데이터를 효과적으로 압축 할 수 있는 알고리즘이다. 이 알고리즘은 무손실 압축* (Lossless compression) 으로 데이터에 따라 20~90%까지 압축이 가능하다.* 무손실 압축은 데이터를 압축하고 복원할 때, 복원한 데이터가 원형의 데이터와 동일한 것을 의미한다. 그럼 알고리즘을 설명하기 전에 몇 가지 기본적인 부분을 살펴보자.위에서 언급했듯이 허프만 코드는 최적 프리픽스 코드를 사용한다. 여기서 프리픽스 코드는 앞의 문자가 뒤의 문자에 접두사 될 수 없는 것이다.예를 들어 아래의 표를 보자. a b 0 101 표를 바탕으로 a의 코드는 0이고 b의 코드는 101이다. 이 떄, 0101.. 2019. 2. 11.

티스토리툴바