전체글149 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) 힙 정렬은 기본적으로 힙 자료구조를 사용한다. 따라서 힙 자료구조를 먼저 학습하면 좋다. 간단하게, 힙 자료구조는 최소값 또는 최대값을 빠르게 찾아내기 위해 완전 이진 트리 형태로 만들어진 자료구조이다. 그리고 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하는데 기반이 된다. 힙 정렬 구현하기 가장 먼저 초기 상태의 배열을 별도의 배열 선언 없이 최대 힙(Max-Heap) 또는 최소 힙(Min-Heap)으로 만든다. 가장 작은 서브 트리부터 최대 힙을 만족하도록 순차적으로 진행하면 최대 힙을 만들 수 있다. (최소 힙도 마찬가지이며, 이와 같이 힙을 만드는 과정을 heapify라고 한다.) 최대 힙을 사용하면 오름차순으로, 최소 힙을 사용하면 내림차순으로 정.. 2024. 2. 14. 우선순위 큐(Priority Queue) 우선순위 큐 우선순위 큐 개념 우선순위 큐(Priority Queue)는 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 큐 방식으로 순서에 의해 처리된다. 우선순위 큐가 힙입라는 것은 널리 알려진 오류이다. 우선순위 큐는 리스트나 맵과 같이 추상적인 개념이다. 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다. 우선순위 큐는 큐와 유사하지만 우선순위가 높은 원소가 먼저 처리된다. 위에서 설명했듯이 우선순위 큐는 추상적인 개념이고, 우선순위 큐의 기능을 사용할 수 있.. 2024. 2. 9. 삽입정렬 (Insertion Sort) 삽입정렬 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성시키는 알고리즘이다. 삽입정렬 과정 처음 초기 상태이다. 처음 루프인 i는 1부터 시작하고, i번째 원소를 저장하기 위한 tmp를 선언한다. 두번째 루프인 j는 i-1부터 시작해서 0이상 일 때까지 반복한다. 이 j 루프를 돌면서 i번째 원소를 저장한 tmp를 적절한 위치에 삽입하는 방식이다. 여기서는 원소 5를 적절한 위치에 삽입한다. 1, 2번 과정을 거쳐서 원소 22는 적절한 위치를 삽입하는데 그대로 있다. 원소 11은 적절한 위치에 삽입한다. 원소 2를 적절한 위치에 삽입한다. 설명이 많이 부실한데 코드를 보면 바로 이해할 수 있을 것이다. 삽입정렬 코드 i.. 2024. 2. 7. 선택정렬(Selection Sort) 선택정렬 (Selection Sort) 선택정렬은 루프를 돌면서 가장 작은 값부터 앞으로 차곡차곡 옮기는 것을 말한다. 선택정렬 과정 위 배열이 있을 때 루프를 돌면서 가장 작은 값을 찾는다. 그리고 변수 idx에는 처음에 i값으로 초기화하고, 루프를 돌면서 가장 작은 값의 인덱스를 저장한다. 루프가 끝나서 가장 작은 값을 찾으면 i번째인 첫 번째 위치한 8 과 가장 작은 값 2를 서로 swap한다. swap하게 되면 첫번째 원소는 정렬이 된 것이다. (초록색 부분) 1과 2번의 과정을 반복한다. 역시 루프를 돌면서 가장 작은 값을 찾고 idx에는 가장 작은 값의 인덱스를 저장한다. 저장이 완료되면 i번째인 5와 가장 작은 값 5를 swap한다. 물론 이 결과는 그대로 있다. 위 과정을 계속 반복하게 되.. 2024. 2. 7. B Tree B Tree 이진 탐색 트리(BST)의 특징 중 하나는 자식 노드는 최대 2개까지 갖는 형태를 말한다. 그렇다면 자식 노드를 최대 2개에서 더 늘릴 방법이 없는걸까? B Tree 개념 B 트리는 트리 자료구조의 일종으로 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 2개 이상 갖는 트리 구조이다. B Tree 특징 자식 노드의 최대 개수를 늘리기 위해 부모 노드에 Key를 하나 이상 저장한다. 부모 노드의 Key들을 오름차순 정렬한다. 정렬된 순서에 따라 자식 노드들의 Key 값의 범위가 결정된다. 모든 leaf 노드들은 같은 레벨에 있다는 특징을 가지고 있다. 검색 성능해서 최악의 경우에도 Red-Black 트리와 동일하게 최악의 경우에도 O(log N)의 시간복잡도를 같는다 B T.. 2024. 2. 6. Red-Black 트리 Red-Black 트리 Red-Black 트리 개념 이진 탐색 트리(BST)의 한 종류 이진 트리는 모든 노드가 가지는 자식 노드를 최대 2개 가지는 형태다. 이진 탐색 트리는 이진 트리의 모든 노드가 왼쪽 서브 트리는 자기보다 작은 값이, 오른쪽 서브 트리에는 큰 값이 배치되는 특징이 있다. 스스로 균형(balancing)을 잡는 트리 스스로 균형을 잡음으로서 이진 탐색 트리의 worst case의 단점을 개선할 수 있다. 이진 탐색 트리는 시간복잡도가 O(log N)이지만 worst case인 경우에는 O(N)의 시간이 걸린다. 즉, Red-Black 트리는 worst case인 경우에도 O(log N)의 시간복잡도를 갖는다. 모든 노드는 Red 혹은 Black을 갖는다. Red-Black 트리 속성.. 2024. 2. 5. 이전 1 ··· 3 4 5 6 7 8 9 ··· 25 다음
