LIT(Learn I Today) 내가 오늘 배운 것들에 대한 정리
큐(Queues)
큐(Queues)란 선형 구조란 점에서는 앞서 정리한 배열, 리스트, 스택 들과 비슷하다.
하지만 후입선출(LIFO, Last-in First-out)인 스택과 달리 큐는 스택과 반대로 선입선출(FIFO, First-in First-out)이라는 점이 다르다.
환형 큐(Circular Queues)
- 만약 큐에 담을 수 있는 원소의 개수의 상한을 미리 정하고 이를 지킬 수 있다면, 선형 배열을 이용해서 큐를 효과적으로 구현할 수 있다.
- 선형 배열의 한쪽 끝과 다른 쪽 끝이 서로 맞닿아 있는 모습 ("원형" 또는 "환형") 으로 생각하고, 큐의 맨 앞과 맨 뒤를 가리키는 (즉, 원소를 넣을 쪽의 배열 인덱스와 꺼낼 쪽의 배열 인덱스를) 기억해 두면, 데이터 원소가 빠져 나간 쪽의 저장소를 재활용하면서 큐를 관리할 수 있다.
우선순위 큐(Priority Queues)
- 큐의 원칙인 선입선출을 지키기보다는 원소들 사이의 우선순위 (priority) 관계에 따른 순서로 원소들이 꺼내어지는 응용.
- 대표적인 응용 예를 들자면, 운영체제에서 CPU 스케줄러를 구현할 때, 현재 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘 구현하는 방법은 아래와 같이 두가지로 생각해 볼 수 있다.
1. 큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법
2. 큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법
트리(Trees)
트리(Trees)란 순환하는 길이 없는 그래프 (graph).
이진 트리 (Binary Trees)
- 트리에 포함되는 모든 노드의 차수가 2 이하인 트리
- 즉, 모든 노드는 자식이 없거나 (리프 노드의 경우), 하나만 있거나, 아니면 둘 있는 세 경우 중 하나에 해당합니다.
- 이진 트리를 추상적 자료 구조로 구현 하기 위해서 아래와 같은 연산
1.size()- 현재 트리에 포함되어 있는 노드의 수를 구함
2.depth()- 현재 트리의 깊이 (또는 높이) 를 구함 - 트리는 정의 자체가 재귀적이기 때문에 연산 또한 재귀적으로 구현한다. 트리를 순회하는 방식은 아래와 같은 방법들이 있다.
1. 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
2. 전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
3. 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문
힙 (Heaps)
힙 (Heaps)이란, 이진 트리의 한 종류입니다. 이진 힙 (binary heap) 이라고도 부른다. 힙은 데이터 원소들의 순서를 교묘하게 표현한 트리. 따라서 데이터의 정렬에도 이용할 수 있는데, 힙을 이용하여 데이터를 정렬하는 알고리즘을 힙 정렬 (heap sort) 이라고 부른다.
- 힙에는 최대 힙 (max heap) 과 최소 힙 (min heap) 이 있다.
- 데이터 원소의 순서기준이 내림차순이냐 오름차순 이냐만 달라지고 완전한 대칭이다.
힙의 성질
- 루트 노드가 항상 최댓값을 가진다.
- 완전 이진 트리이다.
- 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.
힙의 장점
- 완전 이진 트리 여야 한다는 제약 때문에 최대 힙의 높이(깊이)는 log(n) + 1 로 정해진다.
따라서 삽입, 삭제, 정렬 실행시간은 언제나 O(log(n))
꾸준히 학습하고 기록하기 위한 log