'🍀 Knowledge/자료구조' 카테고리의 글 목록

[자료구조] 효율적인 데이터 정렬을 위한 비교 정렬 알고리즘 분석

2023.06.14

정렬 알고리즘이란 n개의 숫자가 주어졌을 때, 이를 사용자가 지정한 기준에 따라 정렬하는 알고리즘을 뜻한다. 지금부터 어떤 알고리즘이 있는지 살펴보도록 하자. 비교 정렬(comparison sort) 비교 정렬은 배열의 원소 쌍 간의 비교를 기반으로 정렬하는 알고리즘이다. 가장 쉽게 생각할 수 있는 알고리즘이자 O(nlogn)이라는 시간 한계를 넘어서지 못한다. 이러한 비교 정렬의 종류로써 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort)이 있다. 선택 정렬 제일 먼저 선택 정렬이란? 배열에서 아직 정렬되지 않은 부분에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하..

🍀 Knowledge/자료구조

[자료구조] 이진 탐색 트리(Binary Search Tree) : 균형과 성능의 조화

2023.06.09

이진 탐색 트리를 공부하기 앞서, 탐색 트리란 무엇인가? 이는 저장된 데이터에 대해 접근, 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조를 말한다. 탐색 트리의 종류는 굉장히 다양하지만, 제일 기본이고 선행되어 학습되어야 하는 부분이 바로 이진 탐색 트리이다. (그 외에 AVL트리, 2-3 트리, 2-3-4 트리, B-트리, RB-트리 등은 다른 포스팅을 참고하자) 이진 탐색 트리 이진 탐색 트리(Binary Search Tree)란, 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조를 말한다. 🤔 그렇다면 이진 탐색이란? 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법이다. 다시말해 이진 탐색 트리란, 트리 형태의 구조..

🍀 Knowledge/자료구조

[자료구조] AVL 트리 - 회전 연산을 통해 균형을 유지하다

2023.06.07

AVL 트리 AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지한다는 특징이 있다. 즉, 삽입이나 삭제 시에 균형이 어긋나게 되면 스스로 회전 연산을 통해 균형을 유지하는, 자체 힐링이 가능한 트리이다. 이러한 AVL 트리(a.k.a 균형 트리)를 사용하는 이유는 탐색, 삽입, 삭제 연산 시에 균일한 수행 시간 O(logN)을 보장하기 때문인데, 이는 AVL 트리의 높이와 관계가 있다. n개의 노드를 가진 AVL 트리의 높이는 O(logN)이다. AVL 트리의 정확한 정의를 알아보자. AVL 트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리이다. AVL 트리의 회전 연산 회전 연산의 경우 AVL트리는 회전 ..

🍀 Knowledge/자료구조

[자료구조] 우선순위 큐(Priority Queue), 그리고 힙(Heap)

2023.06.07

우선순위 큐(Priority Queue) : 가장 높은 우선순위를 가진 항목에 접근과 삭제, 임의의 우선순위를 가진 항목 삽입을 지원하는 자료구조이다. 큐(Queue)라고 함은 먼저 들어오는 데이터가 먼저 나가는 자료구조인데, 앞에 우선순위가 붙어서 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저나가는 구조인것이다. 힙(Heap)이란 우선순위 큐를 위해서 고안된 완전이진트리 형태의 자료구조이다. 또한 부모의 우선순위가 자식의 우선순위 보다 크다는 특징을 가지고 있어 우선 순위 큐를 구현하는데 힙을 주로 사용한다. 힙의 종류는 두가지가 있다. 최소 힙(Minimum Heap) : 키가 작을수록 높은 우선순위 Key(부모노드) < Key(자식 노드) 최대 힙(Maximum Heap) : 키가 클 ..

🍀 Knowledge/자료구조

[자료구조] 해시 테이블, 해싱, 충돌 해결 방법은?

2023.06.01

해시 테이블 트리 자료구조를 사용하여 삽입과 삭제 연산 시 수행 시간은 최소 O(logn)이 나오는데,(이 경우는 AVL 트리) 이보다 빠른 연산 속도를 위해 제시된 방법이 바로 해시 테이블이다. 해시 테이블은 키와 1차원 배열의 인덱스의 관계를 이용해 키(항목)을 지정한다. 키를 배열의 인덱스로 그냥 사용하면 되지 않냐고 할 수 있지만, 아래 예시처럼 키는 숫자가 아닌 일련의 문자열일 수 있다. 그렇기에 메모리 낭비를 줄이기 위해 우리는 해시 테이블을 사용한다. 해싱 : 키를 해시 함수를 사용해 변환한 해시 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 말한다. 용어 정리를 한번 해보자면, 해시 함수는 키들을 테이블의 인덱스로 변환하는 함수인데, 이때 가장 이상적인 해시 함수는 키들을 균등하게 인..

🍀 Knowledge/자료구조

[자료구조] 탐색 트리 : 2-3 트리, B 트리에 관하여

2023.06.01

2-3 트리 2-3 트리 정의 2-3 트리는 내부 노드의 차수가 2 또는 3인 균형 탐색 트리 차수가 2인 노드는 2-노드라고 부르고, 차수가 3인 노드는 3-노드라고 부른다. 2-노드는 1개의 키를 가지며, 3-노드는 2개의 키를 가진다. 2-3 트리는 루트로부터 각 이파리까지 경로의 길이가 같고, 모든 이파리가 같은 층에 있는 완전 균형 트리이다. 2-3 트리가 2-노드들로만 구성되면 포화 이진 트리와 동일한 형태를 가진다. 2-3 트리에서 중위 순회를 수행하면 키들이 정렬된다. 2-3 트리의 연산 탐색 연산 루트에서 시작하여 방문한 노드의 키들과 탐색하는 키를 비교하며 다음 레벨의 노드를 탐색한다. 삽입 연산 먼저, 탐색과 같은 과정을 거쳐 새로운 키가 삽입될 이파리를 찾아야 한다. 이파리를 찾았다..

티스토리툴바