해시란?데이터를 저장할 인덱스를 간단한 연산을 통해 구하여 데이터의 추가, 검색, 삭제 등이 효율적으로 이루어질 수 있도록 하는 자료구조이다. 예를 들어, [1, 14, 5, 23, 25] 와 같은 데이터와 크기가 7인 해시테이블이 있을 때 다음과 같이 표현할 수 있다.이 때, 해시값은 키를 해시테이블의 크기(7)로 나눈 나머지이다.키11452325해시값10524이런 식으로 key mod 7을 연산하여 해시값을 구할 수 있고, 이렇게 도출된 해시값을 인덱스로 활용하여 해시테이블에 저장할 수 있다. (인덱스는 왼쪽에서부터 순서대로 0, 1, 2, 3, 4, 5, 6)14123 255 해시 충돌(collision)에 대하여그러나 특정 키들에 대한 해시 값이 겹치는 상황이 생길 수 있다.위의 예시에서 8이라..
Binary Search Tree (BST)의 특징 BST의 성능은 트리 높이에 의해서 결정된다. 입력되는 값의 순서에 따라 트리가 균형을 이룰 수도 있지만, 균형이 깨질 수도 있다. 삽입/삭제 과정에서 최적의 경우에는 O(log n)의 시간 복잡도를 가지지만, 최악의 경우에는 O(n)의 시간 복잡도를 가진다. AVL Tree (Adelson-Velsky and Landis Tree) 스스로 균형을 유지하는 트리를 AVL Tree라고 한다. 모든 노드에 대하여 각각의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하이다. C언어로 AVL Tree 구조체를 구현하면 다음과 같다. typedef struct AVLNode { int data; struct AVLNode* left; struct AVLN..
![]()
배열 fixed-size: 배열의 크기는 고정되어 있다. homogeneous: 한 배열에는 고정된 한 타입이 있다. (int, float, struct, pointer, ...) stored in a contiguous memory location: 메모리 상 연속적인 공간에 있다. 하나의 index와 하나의 value가 서로 짝을 이루고 있다. int arr[5] = {1, 2, 3, 4, 5}; 다차원 배열 // 2차원 배열 [행][열] int arr2[3][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; printf("%d", arr2[1][3])// 8 출력 // 3차원 배열 int arr3[2][3][2] = { { {1, 2}, {3, 4}, ..
