자료구조

[해싱(Hashing)]해싱(Hashing)은 데이터를 저장하고 검색하는 빠른 방법 중 하나입니다.이는 해시 함수를 사용하여 데이터를 해시 값으로 변환한 후, 이 값을 사용하여 데이터를 저장하고 검색합니다.해싱은 주로 사전(딕셔너리)과 같은 추상 자료형을 구현하는 데 사용됩니다.  [맵(Map)]사전(dictionary), 맵(map), 테이블(table) :: 셋 다 같은 이름입니다. 균형이진트리의 일종인 레드-블랙 트리로 구현되어 있습니다.키-값으로 저장하고 키로 검색하여 값을 찾고, 이진 탐색을 사용하므로 검색이 빠른 편입니다. 삽입, 삭제 시 균형트리이기 때문에 균형을 유지하는데에 오버헤드가 생깁니다.맵에 삽입하는 경우 이미 있는 key라면 값을 삽입하지 않고 이미 키가 있는 해당 노드의 키/값을..

[2-3 트리]2-3 트리는 모든 내부 노드가 두 개 또는 세 개의 자식을 가지며, 모든 리프 노드가 동일한 깊이에 있는 균형 트리입니다.이는 데이터베이스나 파일 시스템에서 사용되는 B-트리의 기본 형식입니다.2-3 트리는 삽입, 삭제, 탐색 연산이 항상 균형 잡힌 상태에서 이루어지므로 시간 복잡도가 O(logn)입니다.    2-3 트리 작동 원리삽입:새로운 키를 삽입할 때, 현재 노드가 두 개의 키를 가지고 있지 않으면 키를 추가합니다.노드가 두 개의 키를 가지고 있을 때 키를 추가하면 노드가 분할됩니다.분할된 키 중 하나는 부모 노드로 올라가고, 나머지는 두 개의 자식 노드로 분할됩니다.삭제:리프 노드에서 키를 삭제할 때, 노드에 키가 하나만 있으면 병합 또는 차용이 필요합니다.내부 노드에서 키를 ..

트리에는 균현 트리와 경사 트리가 있습니다.경사 트리가 될수록 순차 탐색과 같은 탐색 시간을 가지게 되기 때문에 균형을 유지하는 것이 매우 중요합니다.  [AVL 트리]AVL 트리는 높이 균형 이진 탐색 트리의 한 종류로, 각각의 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다.이 균형을 유지하기 위해 삽입 및 삭제 연산이 발생할 때 트리를 회전시켜 균형을 맞춥니다. AVL 트리는 높이가 log(n)에 비례하도록 유지되므로, 탐색, 삽입, 삭제 연산의 시간 복잡도가 log(n)입니다.   AVL 트리 작동 원리삽입:새로운 노드를 삽입한 후, 트리의 균형을 맞추기 위해 필요한 경우 회전을 수행합니다.삭제:노드를 삭제한 후, 트리의 균형을 맞추기 위해 필요한 경우 회전을 ..

[보간 탐색 (Interpolation Search)]보간 탐색은 이진 탐색과 유사하지만, 탐색할 값을 예상 위치로 바로 접근하여 탐색 속도를 향상시키는 알고리즘입니다.보간 탐색은 데이터가 균등하게 분포되어 있는 경우 특히 효과적입니다. 보간 탐색 작동 원리배열의 시작 인덱스와 끝 인덱스를 설정합니다.현재 탐색 범위 내에서 찾고자 하는 값이 있을 것으로 예상되는 위치를 계산합니다.계산된 위치의 값과 찾고자 하는 값을 비교하여 찾고자 하는 값이 현재 위치보다 작으면 왼쪽 부분을, 크면 오른쪽 부분을 탐색합니다.값을 찾을 때까지 또는 탐색 범위가 없을 때까지 이 과정을 반복합니다.   보간 탐색 의사 코드함수 interpolationSearch(arr, n, key): low = 0 high = ..

[색인 순차 탐색 (Indexed Sequential Search)]색인 순차 탐색은 순차 탐색과 색인을 결합한 탐색 알고리즘으로, 데이터가 정렬되어 있는 경우 색인을 사용해 탐색 범위를 좁혀 탐색 시간을 단축할 수 있습니다.큰 데이터셋을 작은 블록으로 나누고, 각 블록의 시작 지점에 대한 색인을 만들어서 탐색 성능을 향상시킵니다.  색인 순차 탐색 작동 원리색인 생성: 데이터를 일정한 크기의 블록으로 나누고, 각 블록의 첫 번째 요소를 색인 테이블에 저장합니다.색인 탐색: 색인 테이블을 순차 탐색하여 찾고자 하는 값이 속할 가능성이 있는 블록을 찾습니다.블록 탐색: 해당 블록 내에서 순차 탐색을 수행하여 값을 찾습니다.  색인 순차 탐색 의사 코드함수 indexedSequentialSearch(arr,..

[이진 탐색]이진 탐색(Binary Search)은 정렬된 배열에서 매우 효율적으로 원하는 값을 찾을 수 있는 탐색 알고리즘입니다.배열을 반으로 나누어 탐색 범위를 좁혀가며 원하는 값을 찾기 때문에, 큰 데이터셋에서도 빠르게 작동합니다.  이진 탐색의 작동원리배열의 중간 요소를 선택하여 찾고자 하는 값과 비교합니다.찾고자 하는 값이 중간 요소보다 작으면, 배열의 왼쪽 반을 탐색합니다.찾고자 하는 값이 중간 요소보다 크면, 배열의 오른쪽 반을 탐색합니다.위 과정을 찾고자 하는 값을 발견하거나 탐색 범위가 없을 때까지 반복합니다. 이진 탐색은 순환 방식과 반복 방식 모두 사용이 가능합니다.순환 방식에 대해서 먼저 알아보겠습니다.  이진 탐색(순환) 의사 코드함수 binarySearch(arr, low, hi..

[순차 탐색(Sequential Search)]순차 탐색(Sequential Search)은 가장 기본적인 탐색 알고리즘 중 하나로, 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색하여 원하는 값을 찾는 방법입니다.리스트가 정렬되어 있지 않은 경우에도 사용할 수 있으며, 구현이 매우 간단합니다.  순차 탐색 작동 원리리스트의 첫 번째 요소부터 시작하여 하나씩 확인합니다.현재 요소가 찾고자 하는 값과 일치하면, 해당 요소의 인덱스를 반환합니다.끝까지 탐색했는데도 찾고자 하는 값을 발견하지 못하면, 값이 리스트에 없다는 뜻이므로 -1을 반환합니다. 순차 탐색 의사 코드 함수 sequentialSearch(arr, key): for i = 0부터 arr의 길이까지: if arr[i..

이때까지 알아본 정렬 알고리즘의 성능을 비교해보겠습니다.

[기수 정렬(Radix Sort)]기수 정렬(Radix Sort)은 비교 기반의 정렬 알고리즘이 아닌 자릿수를 기준으로 정렬하는 알고리즘입니다. 리스트의 모든 요소를 자릿수 별로 비교하여 정렬합니다.일반적으로 10진수의 경우 각 자릿수(1의 자리, 10의 자리, 100의 자리, ...)를 기준으로 정렬합니다.기수 정렬은 정수형 데이터에 대해 특히 효과적이며, 시간 복잡도는 O(d⋅(n+k)) 입니다.여기서 ddd는 가장 큰 수의 자릿수, nnn은 리스트의 길이, kkk는 기수(보통 10)입니다.  기수 정렬 과정리스트의 가장 작은 자릿수(1의 자리)부터 가장 큰 자릿수까지 반복하여 정렬합니다.각 자릿수 별로 리스트를 정렬하기 위해 안정적인 정렬 알고리즘(보통은 계수 정렬)을 사용합니다. 기수 정렬 의사 ..

[퀵 정렬(Quick Sort)]퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘의 하나로, 평균적으로 가장 빠른 정렬 알고리즘 중 하나입니다.리스트를 분할하고 정복하며, 재귀적으로 정렬을 수행합니다.퀵 정렬은 피벗(pivot)을 선택하여 리스트를 분할하고, 분할된 부분 리스트를 정렬합니다. 시간 복잡도는 평균적으로 O(nlogn) 이지만, 최악의 경우 O(n^2) 입니다.    퀵 정렬 과정리스트에서 피벗을 선택합니다. 보통 리스트의 중간 요소를 선택합니다.피벗을 기준으로 작은 요소는 피벗의 왼쪽으로, 큰 요소는 피벗의 오른쪽으로 분할합니다.분할된 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다.재귀적인 호출이 끝나면 모든 부분 리스트가 정렬되었으므로 리스트를 ..