ghkdtlwns987

그래프에 대해 간단히 찍먹하는 느낌으로 알아보자. 먼저, 그래프를 공부하는데 정점과 간선에 대해 알아야 한다. 그림을 보면 알겠지만 정점은 노드 자체를 가리키고, 간선은 노드를 잇는 선을 간선 이라고 한다. 예를 들면 위 그림은 일명 다리 문제라고 불리는데, 여기서 A,B,C,D 는 정점이라 푸를 수 있고, 그 점들을 잇는 선을 간선이라 부를수 있다. 다음으론 방향 그래프와 무방향 그래프이다. 먼저 방향 그래프는 정점과 간선 사이에 방향을 표시해 놓은 그래프이고 무방향 그래프는 정점과 간선 사이를 그냥 연결만 되어 있다고 생각하면 된다. 표현 방법은 아래와 같다. 무방향 그래프 V(G1) = {0, 1, 2, 3} E(G1) = { (0,1), (0,3), (1,3), (2,3)} 방향 그래프 V(G1)..

허프만 코드에 대해 알아보자. 이번 글은 허프만 코드를 주제로 했지만, 우선순위 큐(Priority Queue) 를 먼저 선행하고 와야 한다. 먼저 허프만 코딩이 무엇인지 알아보자. 허프만 코딩은 문자의 빈도 또는 확률정보를 압축하는 알고리즘이다. 예를 들어 aaaabbbc 라는 문자가 있다고 가정했을 때, a = 4 , b = 3 , c = 1 로 표현하고 이를 통해 빈도가 높은 문자(a) 빈도가 낮은 문자(c) 로 표현할 수 있다. 여기서 a 에 111(2) 이란 값을 부여하고 b 와 c 는 111(2) 를 부여하면 중복되는 문제가 발생한다. 이는 복호화할 때 문제가 발생할 수도 있기 때문에, 값이 겹치면 안된다. 허프만 코드를 만들기 위해선 다음과 같은 과정을 거쳐야 한다. 1. 주어진 텍스트에서 ..

우선순의 큐에 대해 알아보자. 큐(Queue) 라고 하면 흔히 먼저 들어온게 먼저 나간다는(First in First out)구조이다. 하지만 우선순위 큐(Priority Queue) 는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 의미한다. 우선순위 큐는 힙(Heap) 이라는 자료구조를 가지고 구현할 수 있다. 우선순위 큐는 배열을 이용해 구현할 수 있고, 연결리스트, 힙 기반 으로도 구현할 수 있다. 들어가기 전 각 기반에 따른 시간 복잡도에 대해 알아보자. 배열 기반 삽입 : O(n) 배열 기반 삭제 : O(1) 힙 기반 삽입 : O(log2n) 힙 기반 삭제 : O(log2n) 그럼 본격적으로 시작해 보겠다. 힙(Heap) 은 완전 이진 트리를 배열로 만든 자료구조이다. 이는..