분류 전체보기
정렬 정렬 알고리즘에 대한 연구는 컴퓨터 과학자들 사이에서 오래 전 부터 이루어져 왔다.그 과정에서 많은 정렬 알고리즘들이 탄생했는데, 그 중 잘 알려진 정렬 알고리즘 몇몇개를 살펴 보려고 한다. 살펴볼 것은 아래와 같다. 시간 복잡도가 O(n^2)인 정렬 : 버블 정렬, 삽입 정렬, 선택 정렬시간 복잡도가 O(nlog(n))인 정렬 : 병합 정렬(항상), 퀵 정렬(일반적으로) 참고로 자바에서 내장되어 있는 Arrays.sort() 메서드는 다음 정렬 알고리즘을 사용한다.퀵 정렬: 퀵정렬 중 이중 피벗 퀵정렬을 사용한다.병합 정렬: JDK 6까지 주로 사용되었으며, 아직 남아있는 부분이 있다. 여담으로 현재 가장 많이 사용되고 있는 정렬 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 정도가 있다. 그렇다..
해시 테이블 (Hash Table) 해시 테이블(Hash Table)은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조이다.데이터를 키-값 쌍으로 매핑한 후, 이를 배열에 저장하는데, 각 키에 대해서 해시 함수를 적용하여 해시 값을 계산하여 이를 배열의 인덱스로 사용한다. 따라서 특정 키에 대한 검색이 빠르게 이루어질 수 있다. 버킷(Bucket): 해시 테이블의 각 슬롯을 가리키는 용어이다. 데이터 삽입 과정해시 함수 적용: 데이터의 키를 해시 함수에 넣어 해시 값을 계산한다.해시 값의 인덱스 결정: 해시 값을 기반으로 배열에서 저장될 위치인 인덱스를 결정한다.데이터 저장: 결정된 인덱스에 데이터를 저장한다. 만약 해당 인덱스에 이미 데이터가 저장되어 있다면 충돌이 발생한 것이다.충돌 해결: 충..
허프만 코딩 데이터 문자의 등장 빈도에 따라 다른 길이의 부호를 사용하여 데이터를 압축하는 알고리즘이다. 자주 등장하는 문자는 짧은 부호로, 드물게 등장하는 문자는 긴 부호로 표현하여 데이터의 크기를 줄이는 데 효과적이다.알고리즘에서 우선순위 큐가 사용되며, 이를 기반으로 빈도 기반의 허프만 부호화를 효율적으로 수행할 수 있다.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에 접근할 수 있다.제네릭 지원:..
