728x90
Stack, Queue에 대해서 설명해주세요.
Stack
- LIFO(Last In First Out, 후입선출)
- push(), pop()
- 활용 예시
- 웹 브라우저 방문 기록
- 역순 문자열 만들기
- 실행 취소
- 후위 표기법
- 수식의 괄호 검사 등
Queue
- FIFO(First In First Out, 선입선출)
- offer(), poll()
- 활용 예시
- 우선순위가 같은 작업 예약(프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리 등
Heap, Priority Queue에 대해서 설명해주세요.
Heap
- 완전 이진 트리(Complete Binary Tree)로 구성된 자료구조
- 모든 노드에 저장된 값들은 자식 노드들의 것보다 크거나 같다.
- 부모는 자식보다 항상 우선순위가 높다
- 그렇기 때문에 루트 노드가 항상 우선 순위가 가장 높은 노드임
Priority Queue
- Heap을 이용해서 우선 순위 큐를 구현함 !
Tree, Binary Tree, BST, AVL Tree에 대해서 설명해주세요.
Tree
- 나무(tree)를 뒤집어 놓은 것 같다고 해서 이름이 붙여진 자료 구조
- 노드와 엣지로 구성되어 있음
Binary Tree
- 이진 트리
- 자식 노드가 최대 두 개인 노드들로 구성된 트리
BST(Binary Search Tree)
- 이원 탐색 트리
- 이진 트리의 구조를 가지고 있으며, 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료 구조
- 특징
- 모든 원소는 상이한 키를 갖는다.
- 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
- 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
- 왼쪽 서브트리와 오른쪽 서브트리도 모두 이원 탐색 트리이다.
AVL Tree
- 이진 탐색 트리는 데이터 삽입 순서에 따라서 한쪽으로 노드가 쏠릴 수가 있다. 그렇게 되면 데이터를 검색하는데에 O(N)의 시간 복잡도가 요구되어 성능이 매우 나빠지게 된다.
- AVL Tree는 BST의 이런 단점을 보완하고자 만들어졌다.
- 특징
- 이진 탐색 트리의 속성을 가진다.
- 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
- 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
- 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수)
728x90