Computer Science (21) 썸네일형 리스트형 허프만 코딩 2 - 문자열 압축과 추출 지난 포스팅(https://taeminator1.tistory.com/51)에서 허프만 코딩이 무엇인지 알아보았고, 허프만 코드를 생성하는 방법과 허프만 코드가 "더 짧은 심벌 트릭"에서 적절한 심벌이 될 수 있는 이유에 대해 알아보았다. 이번 시간에는 허프만 코드를 이용해 실제 압축과 추출을 구현하기 위한 전체 과정을 살펴보려고 한다. 크게 "압축"과 "추출" 두 가지 동작에 대해 설명할 것이다. (추가로 동작이 제대로 이루어졌는지 확인하기 위한 "검증"도 필요할 수 있다) 압축: 입력받은 문자열을 압축하여 새로운 문자열을 생성 추출: 입력받은 문자열에서 원래 문자열 추출 전체 과정을 살펴본 다음, 문자열이 주어졌을 때, 각각의 과정의 결과가 어떻게 되는지 설명하려고 한다. 먼저 전체 과정은 다음과 같.. 허프만 코딩 1 - 허프만 코드 구하기 허프만 코딩(Huffman Coding)은 이전 포스팅(https://taeminator1.tistory.com/49)에서 언급한 "더 짧은 심벌 트릭(shorter-symbol trick)"의 일종이다. 더 짧은 심벌 트릭은 압축하려는 문자열에서 자주 사용되는 문자일수록 짧은 심벌을 부여하여 압축하는 방법이다. 허프만 코딩은 이러한 심벌을 허프만 코드를 이용해서 압축하는 방법이다. 허프만 코딩의 핵심은 아무래도 허프만 코드를 구하는 것이다. 허프만 코드를 구하는 방법을 살펴보기 전에, "더 짧은 심벌 트릭"에서 "심벌"이 되기 위한 조건을 살펴보자. 다음과 같은 두 가지 조건이 있다. 빈도수가 많을수록 심벌의 자릿수가 적어야 한다 임의의 심벌이 다른 심벌의 첫 부분이 아니어야 한다 먼저 첫 번째 조건은.. 데이터 압축 압축은 기존의 데이터를 변형하여 더 적은 용량을 갖는 데이터로 만드는 데에 그 목적이 있다. 물론 압축 결과로 생기는 부가 데이터 등으로 인해 데이터의 용량이 늘어나는 경우도 있지만 기본 목적은 데이터 용량을 줄이는 것이다. 이러한 압축은 데이터의 손실 여부에 따라 두 가지로 나눌 수 있다. 압축 후 추출하는 과정에서 데이터 손실이 발생했다면 손실 압축, 그렇지 않다면 무손실 압축이다. 백업 파일을 저장할 때, 때때로 압축 프로그램을 쓴다. 일반적으로 데이터의 용량이 줄어들고 하나의 파일로 묶을 수 있어 데이터 관리나 전송을 용이하게 한다. 이렇게 압축된 데이터를 풀면 압축하기 전 그대로의 데이터를 얻을 수 있다. 무손실 압축이 적용된 것이다. 또 다른 예로 인터넷 사이트에서 동영상을 다운로드할 때, 화.. [Swift] Heap을 이용한 Priority Queue 구현 우선순위 큐(Priority Queue)는 이름에서 알 수 있듯이 큐(Queue)의 일종이다. 큐는 지난 포스팅에서 설명한 것과 같이, 먼저 입력된 데이터가 먼저 출력되는 자료구조이다. 이에 반해 우선순위 큐는 출력될 데이터가 입력된 순서에 따라 결정되는 것이 아니라, 우선순위에 따라 이루어진다는 차이가 있다. 우선순위 큐도 다양한 방법으로 구현할 수 있지만, 힙으로 구현하는 것이 적절해 보인다. 배열(Array)이나 연결 리스트(Linked List)로 구현할 경우, 삽입 또는 삭제 연산 시에 데이터의 정렬을 위해 모든 데이터를 순회해야 하기 때문에 시간 복잡도가 O(n)이 소요된다. 하지만 힙의 경우 삽입 또는 삭제 시에 반정렬 상태만 유지하면 되는 완전 이진 트리이기 때문에 시간 복잡도가 O(lb(.. [Swift] Array를 이용한 Heap 구현 3 - 함수형 프로그래밍 힙에 대한 배경 지식 및 구현은 아래 포스팅들을 참고하면 된다. https://taeminator1.tistory.com/43 https://taeminator1.tistory.com/44 길고 긴 여정이었지만, 이제 힙에 대한 구현은 마지막 포스팅이 될 것 같다. 이번 포스팅의 주제는 "다양한 힙 구현하기"이다. 지난 포스팅에서는 "최대 힙"을 구현했지만, 때로는 다른 종류의 힙을 원할 수도 있다. 먼저 최소 힙을 구현하는 방법에 대해 생각해 보자. 간단히 설명하자면, 최소 힙(Min Heap)은 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 말한다. 이러한 힙을 구현하기 위해서는 아래와 같이 이전에 구현한 Heap 클래스에서 몇 개의 부등호의 방향만 변경해 주면 된다. func insert(.. [Swift] Array를 이용한 Heap 구현 2 - 최대 힙 지난 포스팅(https://taeminator1.tistory.com/43)에 이어 이번 시간에는 Swift를 이용해 힙을 실제로 구현해 보겠다. 먼저 힙을 구성하는 노드(연결 리스트에서 사용한 노드와 구별하기 위해 Heap Node라고 이름을 지었다)를 구현해 주겠다. 연결 리스트에서 구현해 준 노드 클래스와 마찬가지로 제네릭을 이용해 다양한 타입에 대응되게 만들었다. 다만 연결 리스트의 노드와 달리 힙 노드는 노드 간에 값을 비교해야 하기 때문에 Comparable 프로토콜을 준수하여 구현하였다. class HeapNode: Comparable { var data: T init(_ data: T) { self.data = data } func getData() -> T { return data } f.. [Swift] Array를 이용한 Heap 구현 1 - 개요 해당 포스팅에 앞서 트리에 대한 전반적인 정리는 이전 포스팅(https://taeminator1.tistory.com/42)을 참고하면 된다. 힙은 단말 노드가 아닌 각각의 노드에 대해 노드의 값이 자식 노드의 값과 비교해 일정한 규칙을 갖는 완전 이진 트리이다. (노드의 값(키)은 중복이 가능하다) 힙은 대표적으로 최대 힙과 최소 힙이 있는데, 자식 노드의 값이 부모 노드의 값 보다 크지 않은 힙을 최대 힙(Max Heap), 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 최소 힙(Min Heap)이라고 한다. 이번 포스팅에서는 특별한 언급이 없다면 최대 힙(각각의 부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우)으로 가정하고 힙에 대한 설명을 이어 나가겠다. 힙의 가장 큰 특징은 반정.. 트리 나무는 뿌리에서 시작하여 줄기를 타고 여러 개의 가지로 뻗는다. 각각의 가지는 다시 여러 개의 가지로 뻗고, 이 과정을 몇 번 반복한다. 그리고 가지의 끝에는 나뭇잎이나 열매가 맺히게 된다. 이러한 나무의 구조와 유사한 형태의 자료구조를 트리라고 한다. 트리도 앞서 설명한 나무의 구조와 마찬가지로 뿌리(root node)를 시작으로 여러 노드로 분기한다. 각각의 노드는 다시 여러 노드로 분기하며 이러한 과정을 반복하게 된다. 그리고 더 이상 노드로 분기하지 않는 노드를 단말 노드(terminal node 또는 leaf node)라고 한다. 앞서 가지에 끝에 달린 나뭇잎이나 열매와 같은 개념이다. 이러한 트리는 계층을 갖는데, 이는 큐나 리스트와 같은 선형 자료 구조와 구별되는 특징이다. 이러한 특징을 이.. 이전 1 2 3 다음
