데굴데굴 개발자의 기록

허프만 코딩 데이터 문자의 등장 빈도에 따라 다른 길이의 부호를 사용하여 데이터를 압축하는 알고리즘이다. 자주 등장하는 문자는 짧은 부호로, 드물게 등장하는 문자는 긴 부호로 표현하여 데이터의 크기를 줄이는 데 효과적이다.알고리즘에서 우선순위 큐가 사용되며, 이를 기반으로 빈도 기반의 허프만 부호화를 효율적으로 수행할 수 있다.Unix 파일압축 명령어에 사용, JPEG, MP3 압축하기 위한 서브루틴으로서도 활용된다.  허프만 코딩 : 과정  1. 입력압축할 데이터에 대해서 입력받는다.AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE 2. 문자 빈도 분석 압출할 데이터에서 각 문자의 등장 빈도를 분석한다.A : 15B : 7C : 6D : 6E : 5 3. 허프만 트리 생성우선 빈..

우선순위 큐 (Priority Queue)   우선순위 큐는 일반적인 큐와 다르게, 우선순위 큐는 각 요소마다 우선순위가 지정되어 있어서, 우선순위가 높은 요소가 일반적으로 먼저 처리되는 형태의 자료구조이다.요소들은 우선순위에 따라 정렬되어 있으며, 우선순위에 따라 삽입된 요소들이 정렬되어 있는 형태를 띈다. 스택과 큐 또한 일종의 삽입 순서에 따른 우선순위 큐의 종류라고 볼 수 있다.   힙(Heap) 힙은 대표적인 우선순위 큐의 종류이다. 주로 이진 힙으로 구현하며, 대표적인 종류로는 최소 힙과 최대 힙이 있다. 완전 이진 트리 : 힙은 완전 이진 트리의 구조를 가지고 노드가 왼쪽부터 차례로 채워진다. 최소 힙과 최대 힙: 최소 힙(Min Heap)의 경우 부모 노드의 값은 자식 노드의 값보다 항상 ..

AVL 트리   AVL 트리는 이진 탐색 트리(BST)의 한 종류로, 연산 수행 시 최악의 경우에도 시간 복잡도를 O(log n)으로 유지하기 위해 고안되었다. 이진 탐색 트리의 단점 중 하나는 트리가 한 쪽으로 치우쳐져 편향되는 현상이 발생할 수 있다는 것이 있다. 기존 이진 탐색 트리에서 트리가 최악으로 편향될 경우, 연산의 시간 복잡도가 O(N)으로 악화될 수 있다. AVL 트리는 이러한 문제를 해결하는 데에 초점을 맞추었다. 해당 트리는 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1을 유지하도록 한다. 따라서 트리가 편향되는 것을 방지하고, 모든 연산의 시간 복잡도를 O(log N)으로 유지할 수 있다. 이를 위해 아래 애니메이션처럼 삽입 및 삭제 시 트리의 균형을 조절하는 알고리즘을..

이진 탐색 트리(Binary Search Tree, BST)  앞의 포스팅에서는 이진 트리에 대해서 알아 보았었다. 그런데 이진 트리는 정렬되지 않은 형태이므로 탐색을 수행하기 적절하지 않았다.이를 위해서 이진 트리의 특수한 형태인 이진 탐색 트리가 있으며, 정렬된 형태의 이진 트리이고 이는 탐색을 위한 트리로서 사용될 수 있다. 다음 규칙들이 추가되었다고 생각하면 된다. 구조 : 각 노드의 왼쪽 서브 트리에 있는 모든 값은 해당 노드의 값보다 작거나 같다. 오른쪽 서브 트리에 있는 모든 값은 해당 노드의 값보다 크거나 같다.삽입 규칙: 새로운 값을 삽입할 때, 구조 규칙에 따라 트리를 탐색하며 적절한 위치를 찾는다.특정 값 삭제 : 해당 노드를 삭제하고, 트리 구조 규칙에 맞추기 위해 재배치하는 로직을..

트리(Tree) 계층적인 구조를 표현하는 데 사용되는 비선형 자료 구조. 트리는 노드(node)들의 집합이며, 각 노드는 부모(parent)와 자식(children) 관계로 연결된다.  중요한 특징으로는 순환이 없다는 점이다. 어떤 경로를 따라 이동하더라도 한 노드를 두 번 이상 방문하지 않는다는 뜻이다. 따라서 트리는 계층적인 데이터를 효과적으로 표현할 수 있다. 트리는 데이터베이스에서는 인덱스 구조, 운영 체제의 파일 시스템을 구현하는 등 여러 분야에서 활용된다. 알고리즘에서는 이진 검색 트리(Binary Search Tree), 힙(Heap), AVL 트리, 레드-블랙 트리 등 다양한 종류의 트리로 응용된다.   트리의 구성 요소 Root(루트) : 트리 최상위 노드Child(자식) : 노드 하위 ..

연결 리스트란?  동적 메모리 할당을 이용하여 구현되는 리스트 형태의 자료구조이다. 리스트는 순서가 있는 요소들의 컬렉션이며, 인덱스로 접근 가능하다 연결 리스트의 구성은 노드로 이루어져어 있으며 각 노드는 데이터를 저장하는 데이터 필드와 다른 노드를 가리키는 참조(포인터) 필드로 구성된다. 이에 따라서 연결 리스트의 특정 인덱스의 원소를 탐색하는 알고리즘으로 순차적 탐색을 사용하게 된다.(배열을 사용하지 않기 때문에 인덱스로 접근 불가능) 연결 리스트의 대표적인 종류로는 단순 연결 리스트, 이중 연결 리스트, 환형 연결 리스트가 있다.해당 포스팅에서는 위의 세 가지 연결 리스트를 직접 구현해보고, Java Collection에서 제공하는 LinkedList 클래스와 시간 복잡도에 대해서 다룬다. 단순 ..

배열과 동적 배열   배열 : 미리 정해진 크기의 메모리 공간을 할당 받은 뒤 사용한다. 따라서 메모리 공간을 초과하면 오버플로우가 발생한다. 동적 배열 : 동적인 크기의 배열을 사용하기 위해서 유동적으로 배열의 크기를 조절하는 아이디어. 배열에 Overflow가 발생하면 배열 크기를 2배로 확장한다, 배열의 3/4가 비어 있다면 배열 크기를 1/2로 축소한다. Java에서 제공하는 대표적인 클래스로 ArrayList가 있다. https://en.wikipedia.org/wiki/Dynamic_array ArrayList의 특징 동적 크기 조정: Element의 추가나 삭제에 따라 크기가 자동으로 조정된다.인덱스 기반 접근: 배열과 유사하게 인덱스를 사용하여 Element에 접근할 수 있다.제네릭 지원:..

스택(Stack)  한 쪽 끝에서만 Item을 삭제하거나 새로운 Item을 저장하는 자료구조이다.후입선출(Last In First Out, LIFO)의 원리를 따른다. 즉, 가장 최근에 추가된 요소가 가장 먼저 제거되는 구조이다. 스택은 이름에서 알 수 있듯 데이터를 쌓아 올리는 형태로 관리되며, 새로운 요소가 추가되거나 제거될 때는 맨 위에 위치한 요소에 대해서 이루어진다.함수 호출의 실행 컨텍스트를 관리하거나 DFS를 비롯한 되추적(Traceback) 알고리즘 혹은, 재귀적인 알고리즘 등에서 호출을 추적할 때 사용할 수 있다.  스택 구현 : 동적 배열   class MyStack{ private T elements[]; private int top; public MyStack(){ ..

재귀와 반복(Recursion, Iteration) 재귀 자신을 호출함으로써 문제를 해결하는 방식.문제를 부분 문제로 나누고.,부분 문제에 대해 동일한 알고리즘을 사용하여 해결하는 분할 정복법의 일종종료 조건을 만족할 때까지 자신을 호출한다.함수 호출 스택에 추가 비용이 들어가기 때문에 과도한 재귀 호출은 스택 오버플로우를 유발할 수 있다.Top-down 방식은 주로 재귀적인 접근 방식을 사용하며, 문제를 작은 문제로 쪼개고 결합하여 전체 문제의 해를 구한다. 반복 반복문을 사용하여 문제를 해결하는 방법코드가 좀 더 복잡할 수 있으나, 스택 오버플로우 문제에 상대적으로 자유롭다.Bottom-up 방식은 주로 반복적인 방식을 사용하고, 먼저 작은 문제를 해결하고 이를 이용해서 더 큰 부분 문제들을 점진적으..