Lowest Common Ancestor 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘으로, 일반적으로 이진 트리나 이진 탐색 트리에서 사용됩니다. 재귀적인 방법과 반복문을 사용한 방법으로 구현할 수 있는데 이 포스팅에서는 재귀를 바탕으로 설명하겠습니다. 동작 순서 루트(root)부터 시작하여 두 대상 노드의 값을 비교합니다. 현재 노드의 값이 두 대상 노드의 값보다 크면, LCA는 현재 노드의 왼쪽 서브트리에 있을 것입니다. 따라서 왼쪽 자식 노드로 재귀 호출합니다. 현재 노드의 값이 두 대상 노드의 값보다 작으면, LCA는 현재 노드의 오른쪽 서브트리에 있을 것입니다. 따라서 오른쪽 자식 노드로 재귀 호출합니다. 두 대상 노드의 값이 현재 노드의 값과 같거나, 현재 노드의 값이 ..
Morris Traversal for Preorder 트리를 순회하는 데 사용되는 다양한 알고리즘이 있습니다. 그 중에서 Morris Traversal 알고리즘은 공간 복잡도를 O(1)로 유지하면서 순회할 수 있는 효율적인 방법으로 스택을 사용하지 않고도 Preorder Traversal를 수행할 수 있습니다. 따라서 메모리 사용에 제약이 있는 환경이거나 공간 복잡도를 최소화해야 하는 상황에서 유용하게 사용될 수 있습니다. 또한 추가 데이터 구조 없이 순회해야 하는 경우에도 유용하게 사용할 수 있습니다. 동작 순서 현재 노드를 기준으로, 왼쪽 서브트리를 순회합니다. 왼쪽 서브트리에서 현재 노드의 바로 이전 노드를 찾습니다. 이전 노드의 오른쪽 자식을 현재 노드로 설정합니다. 현재 노드를 방문합니다. 현재..
기수 정렬 (Radix Sort) 낮은 자릿수부터 정렬하는 방식 시간 복잡도 : O(dn) → d: 최대 자릿수 장점 각 원소 간의 비교 연산을 하지 않아 빠르다. 문자열, 정수 정렬 가능 단점 자릿수가 없는 것은 정렬할 수 없다. (ex. 부동 소숫점) 기수 테이블을 위한 메모리가 필요하다. 계수 정렬 (Counting Sort) 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식 카운팅을 위한 메모리 필요 시간 복잡도 : O(n + k) → k: 정렬 대상 데이터 중 최댓값
힙 정렬 (Heap Sort) 힙 자료구조를 기반으로 하는 정렬 알고리즘 시간복잡도 : O(nlogn) 공간복잡도 : O(n) 장점 : 효율적이며 추가적인 메모리 공간이 불필요하다. 단점 불안정한 정렬이다. 힙 자료구조를 구성하고 유지하기 위해 추가적인 구현이 필요하다. 루트 노드에서 최댓값 또는 최솟값을 추출하고 배열의 마지막 요소와 교환하는 과정을 반복하기 때문에 요소들의 이동 횟수가 많을 수 있다. 힙 정렬 프로세스 배열을 힙으로 만들기 (Max Heap 또는 Min Heap 구성) Bottom-up 방식으로 시작 주어진 배열을 이진 트리로 간주하고, 가장 마지막 레벨의 부모 노드부터 시작하여 루트 노드까지 차례대로 아래로 내려가며 힙의 특성을 만족하도록 조정 (Heapify 과정) 최대 힙 또는 ..
병합 정렬 (Merge Sort) = 합병 정렬 분할 정복(Divide and Conquer) 방식을 사용하여 정렬을 수행하는 알고리 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 크기를 비교하여 정렬하면서 합병하는 방식 시간복잡도 : O(nlogn) 공간복잡도 : O(n) 병합 정렬 기본 프로세스 분할(Divide) : 정렬할 배열을 반으로 나눈다. 이를 위해 배열의 중간 지점을 찾고, 중간을 기준으로 왼쪽과 오른쪽 부분 배열로 나눈다. O(logn) 정복(Conquer) : 나누어진 부분 배열에 대해 재귀적으로 정렬을 수행한다. 이 단계에서는 분할된 부분 배열이 단일 원소로 이루어질 때까지 계속해서 재귀 호출을 수행한다. 병합(Merge) : 정렬된 부분 배열을 병합하여 전체 배열..
퀵 정렬 (Quick Sort) 분할 정복(Divide and Conquer) 방식을 사용하여 정렬을 수행하는 알고리즘 임의의 값(pivot)을 선택하고 피벗을 기준으로 배열을 분할한다. 분할된 부분 배열은 피벗을 기준으로 작은 값들과 큰 값들로 구분되며 각 부분 배열에 대해 동일한 과정을 반복하여 재귀적으로 정렬을 수행한다. 왼쪽/오른쪽/중앙을 고른다. 최솟값 또는 최댓값을 기준 값으로 정하지 않기 위해서 3개의 값을 임의로 정해서 그 중 중앙값을 고른다. 시간복잡도 : 기준 값이 최솟값 또는 최댓값으로 지정되는 경우는 O(n^2) 이지만 평균적으로는 O(nlogn) 이다. 공간복잡도 : O(nlogn) 장점 속도가 빠르다. 평균적으로 O(nlogn)의 시간 복잡도를 가지며, 다른 일반적인 정렬 알고리..
삽입 정렬 (Insertion Sort) 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식 시간복잡도 : (n-1) + (n-2) + (n-3) + ... + 2 + 1 -> n(n-1)/2 즉, O(n^2) 하지만, 모두 정렬되어 있는 경우 한 번씩 밖에 비교를 안하므로 O(n)의 시간복잡도를 가진다. 공간복잡도 : O(n) 장점 구현이 간단하고 이해하기 쉽다. 원소를 적절한 위치에 삽입하는 과정을 반복하는 간단한 알고리즘으로 구현하기가 비교적 간단하고, 알고리즘의 동작 방식도 직관적이다. 작은 규모의 배열에서 효율적이다. 삽입 정렬은 이미 정렬된 부분 배열에 새로운 원소를 삽입하는 방식으로 정렬을 수행한다. 따라서 입력 배열이 거의 정렬되어 있는 경우, 다른 알고리즘보다 효율적일 수 있다...
선택 정렬 (Selection Sort) 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤와 교환하며 정렬하는 방식 시간복잡도 : (n-1) + (n-2) + ... + 2 + 1 -> n(n-1)/2 즉, O(n^2) 공간복잡도 : O(n) 장점 구현이 간단하고 이해하기 쉽다. 기본적인 비교와 교환 과정으로 이루어져 있어서 이해하기 쉽고 구현하기도 간단하다. 추가적인 메모리 공간을 사용하지 않는다. 버블 정렬과 동일하게 주어진 배열 안에서 비교와 교환을 수행하므로, 정렬을위한 추가적인 메모리 공간이 필요하지 않다. 단점 성능이 비효율적이다. 비교와 교환을 인접한 두 원소에 대해 반복적으로 수행하기 때문에 성능이 비효율적이다. 배열의 킉가 커질수록 비교과 교환의 횟수가 증가하여 실행 시간이 길어진다. 불안정..
버블 정렬 (Bubble Sort) 인접한 데이터를 비교하며 필요한 경우 자리를 바꾸는 정렬 방식 시간복잡도 : (n-1) + (n-2) + (n-3) + ... + 2 + 1 -> n(n-1)/2 즉, O(n^2) 공간복잡도 : O(n) 장점 구현이 간단하고 이해하기 쉽다. 기본적인 비교와 교환 과정으로 이루어져 있어 구현하기가 간단하다. 알고리즘의 동작 방식도 직관적이어서 이해하기 쉽다. 추가적인 메모리 공간이 필요하지 않다. 주어진 배열 안에서 비교와 교환을 수행하므로, 정렬을 위한 추가적인 메모리 공간이 필요하지 않다. 안정적인 정렬 알고리즘이다. (Stable Sort) 동일한 값에 대해서는 상대적인 순서가 변하지 않는다. 단점 성능이 비효율적이다. 시간 복잡도가 O(n^2)으로 배열의 크기가 ..
