728x90
스택
스택은 삽입과 삭제 연산이 후입 선출 LIFO로 이뤄지는 자료구조이다. 후입 선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이 있다.
스택 용어
위치
- top : 삽입과 삭제가 일어나는 위치를 뜻한다.
연산
- push : top 위치에 새로운 데이터를 삽입하는 연산
- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
- peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산
스택의 중요성
스택은 깊이우선탐색, 백트래킹 종류의 알고리즘에 사용되므로 반드시 알아 두어야 한다.
후입 선출은 개념 자체가 재귀 함수 알고리즘 원리와 같다.
큐
큐는 삽입과 삭제 연산이 선입선출 FIFO로 이뤄지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.
큐 용어
- rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
- add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
- poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- peek : 큐의 맨 앞에 있는 데이터를 확인할 때 사용하는 연산이다.
큐는 너비 우선 탐색에서 자주 사용하므로 중요한 자료구조입니다.
우선순위 큐
우선순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.
큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙을 이용해 구현하는데 힙은 트리 종류 중 하나이다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다.
최대 힙(Max Heap)이란?
- 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 값이 큰 완전 이진트리를 의미한다.
- 최대 힙의 루트 노드는 전체 트리에서 가장 큰 값을 가지는 특징이 있다.
- 항상 전체 크리가 최대 힙 구조를 유지하도록 자료구조를 설계해야 한다.
- 최대 힙도 큐를 기반으로 동작하기 때문에 push, pop이라는 함수가 있다.
우선순위 큐와 큐의 차이점
- 일반적인 큐: 선형적인 형태를 가지고 있다.
- 우선순위 큐: 트리(Tree) 구조로 보는 것이 합리적이다.
시간 복잡도
- 우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도이다.
- 우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도이다.
728x90