공부하는 스누피

이진 탐색 트리가 편향 트리이면 최악의 경우 O(h)의 시간복잡도를 가진다. 항상 O(logh)의 시간복잡도를 유지하려면 트리의 균형을 맞추어야 한다. AVL 트리는 균형 잡힌 트리 중 하나이다. AVL 트리에서는 균형의 정도를 표현하기 위해 균형 인수를 사용한다. 균형 인수는 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이다. 균형을 잡기 위해 트리를 재조정할 때, 균형 인수의 절댓값이 크면 클수록 트리의 균형이 무너진 상태이다. 균형 인수의 절대값이 1 이하여야 균형 잡힌 트리라고 할 수 있다. 트리의 균형을 잡는 방법은 Rebalancing, Refactoring 등으로 부른다. 재조정이 필요한 상태는 크게 4가지이다. 1) Left Left 상태 루트 노드의 균형 인수가 +2인 경우. 왼쪽 서브..

퀵 정렬이란? Quick sort는 Divide and Conquer 알고리즘으로, 평균적으로 매우 빠른 수행 속도를 보여준다. 시간복잡도가 O(NlogN)으로 Merge sort와 동일하지만, 배열을 균등하지 않게 분할하고 추가적인 메모리 공간을 필요로 하지 않는다. 빠르고 메모리도 덜 차지하지만 pivot을 잘못 설정했을 경우, 최악의 경우에는 시간복잡도가 O(N^2)으로 다른 비효율적인 정렬 알고리즘보다 나은 것이 없다. 그래서 pivot의 위치에 큰 영향을 받지 않는 배열에 적합하다. pivot은 배열을 분할하는 기준점으로, pivot으로 나눠진 두 배열의 원소를 순서대로 꺼내 비교하면서 정렬한다. 원리 배열을 정렬하려면 먼저 3가지 변수를 설정해 두어야 한다. left: 배열 맨 왼쪽 인덱스. ..

합병 정렬이란? 합병 정렬(Merge sort)는 정렬 알고리즘으로, 주어진 배열을 두 개의 배열로 계속 분할한 뒤, 분할한 배열을 합치면서 정렬한다. 배열을 분할하는 과정에서 시간 복잡도 O(logN), 합치는 과정에서 O(N)을 가지므로 총 O(NlogN)의 시간 복잡도를 가진다. Quick sort, Heap sort처럼 시간 복잡도가 O(NlogN)이지만, 정렬을 위한 배열을 하나 더 생성하기 때문에 메모리를 더 많이 차지한다는 단점이 있다. 원리 배열 [4, 3, 2, 1]이 있고, 오름 차순으로 정렬한다고 해 보자. Merge sort는 분할을 먼저 수행하는데, 더 이상 나눠지지 않을 때까지 배열을 나눈다. 0: [4, 3, 2, 1] 1: [4, 3] [2, 1] 2: [4] [3] [2] ..

해시는 키(key)와 값(value)이 한 쌍을 이루는 자료구조입니다. 원리가 간단하기 때문에 복잡한 알고리즘 없이도 탐색이 가능하다는 장점이 있고, 자료구조에서 중요하게 다루는 부분은 아니라 정확한 의미를 모르고 지나가기 쉽습니다. 사전은 해시와 원리가 비슷해 예시로 많이 쓰이고 있습니다. 사전은 단어와 뜻으로 이루어져 있습니다. 사용자는 단어의 뜻을 알기 위해 단어가 어디에 위치했는지 찾아봅니다. 각 단어의 뜻은 단어 바로 옆에 적혀 있기 때문이죠. 여기서 단어는 뜻을 찾기 위한 '주소'라고 보면 되겠습니다. 같은 단어가 여러개 있다면, 거기에다 흩어져 있다면 뜻을 찾기 힘들어 사전의 의미가 없어집니다. 물론 실제 사전은 알파벳순으로 정렬되어 중복된 단어가 있어도 크게 불편하지 않지만, 해시는 그렇지..