자료구조 & 알고리즘

728x90

큐(Queues)

- 자료의 입력과 출력이 각각 한쪽 끝에서 이루어지는 자료 구조 = 'FIFO(First-In-First-Out) 구조'

- 대표적인 선형 자료구조로, 삽입(insert)과 삭제(delete)를 수행

- 큐는 보통 배열(array)이나 연결 리스트(linked list)로 구현

- 큐에 데이터를 삽입하는 것을 '인큐(Enqueue)'

- 큐에서 데이터를 꺼내는 것을 '디큐(Dequeue)'

- 선입선출

* 스택은 후입선출

1) 큐의 연산
- Enqueue(item) : 큐의 끝(rear)에 item을 추가 O(1)

- Dequeue() : 큐의 첫(front) 항목을 반환(큐에서 제거 O) O(n)
- isEmpty() : 큐가 비어 있는지 검사 O(1)

- peek() : 큐의 첫(front) 항목을 반환(큐에서 제거 X) O(1)

- size(): 현재 큐에 들어 있는 데이터 원소의 수를 검사 O(1)

* 추가

- isFull(): 큐에 데이터가 꽉 채워져 있는지 검사

환형 큐(Circular Queues)

- 일반적인 큐와는 달리 마지막 항목 다음에 첫 번째 항목이 연결된 형태로 원형으로 구성된 큐

- 선형 구조의 문제점을 보완하고, 메모리 공간을 더 효율적으로 사용

- 대규모 데이터의 처리나, 시간 제약이 있는 작업에서 많이 사용

- 큐가 가득 차면 어떻게 되는지? => 더이상 원소를 넣을 수 없음(큐 길이 파악 필요)

- 데이터 제거는 Front, 데이터 추가는 Rear

우선순위 큐(Priority Queues)

- 데이터들이 우선순위를 가지고 있으며, 이러한 우선순위에 따라 큐에서 제거되는 자료구조

- 구현간의 방식

큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법 - 더 유리하다.
큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법

- 2가지의 구조

선형 배열 이용
연결 리스트 이용 - 더 유리하다

트리(Trees)

- 노드(node)와 노드 사이를 연결하는 간선(edge)으로 구성된 자료 구조

- 노드의 차수(Degree) = 자식(서브트리)의 수

ex) A:degree:3 / B:degree,2 / F:degree:2 / J, K:degree:0

- 루트(root node), 내부 노드(internal nodes), 리프 노드, 단말 노드(leaf nodes)

이진트리(Binary Tree)

- 모든 노드의 차수가 2 이하인 트리

- 즉, 모든 노드는 자식이 없거나, 하나가 있거나, 둘 있는 경우에만 해당

1) 이진트리 연산

- 삽입(Insertion): 새로운 노드를 트리에 추가
- 삭제(Deletion): 트리에서 노드를 삭제
- 검색(Search): 특정한 값을 가진 노드를 찾기
- 순회(Traversal): 트리의 모든 노드를 특정한 순서로 방문

2) 이진트리의 순회(Traversal)

- 깊이 우선 순회(depth first traversal)

* 중위 순회(in-order traversal)

순회 순서: Left -> Root -> Right

* 전위 순회(pre-order traversal)

순회 순서: Root -> Left -> Right

* 후위 순회(post-order traversal)

순회 순서: Left -> Right -> Root

- 넓이 우선 순회(breadth first traversal)

* 레벨이 낮은 노드를 우선으로 순회

* 같은 레벨의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문하고 왼쪽을 오른쪽보다 먼저 순회

포화 이진트리(Full Binary Tree)

- 모든 노드가 2개의 자식 노드를 가지며, 모든 리프 노드(차수가 0인 노드)들이 같은 레벨에 위치하는 이진트리를 의미

- 높이가 k이고 노드의 개수가 2^k-1인 이진트리

완전 이진트리(Complete Binary Tree)

- 모든 레벨에서 노드들이 왼쪽에서 오른쪽으로 순서대로 채워진 이진트리

- 즉, 마지막 레벨을 제외한 모든 노드들은 채워져 있고, 마지막 레벨에서는 노드들이 왼쪽에서 오른쪽으로 채워져 있다.

1) 번호 규칙

노드 번호 m을 기준으로

- 왼쪽 자식의 번호: 2 * m

- 오른쪽 자식의 번호: 2 * m + 1

- 부모 노드의 번호: m//2

이진 탐색 트리(Binary Search Trees)

- 탐색을 빠르게 수행하기 위해 만들어진 자료구조

- 왼쪽 서브트리에 있는 모든 노드들의 값은 루트 노드의 값보다 작다.
- 오른쪽 서브트리에 있는 모든 노드들의 값은 루트 노드의 값보다 크다.

1) 이진 탐색 트리가 효율적이지 못한 경우는?

- 입력 순서에 따라 트리가 한쪽으로 치우쳐져서 깊이가 매우 깊어진 경우

- 일정한 패턴을 가지는 입력으로 인해 트리가 완전히 균형을 잃어버린 경우

- 이러한 경우 탐색, 삽입, 삭제 등의 연산에서 최악의 경우 시간 복잡도가 O(n)이 될 수 있다.

개선하기 위한 트리종류)

- AVL 트리, 레드-블랙 트리 등의 균형 잡힌 트리(Balanced Tree)를 사용

- 노드를 삽입, 삭제할 때마다 트리를 재조정하여 효율적인 탐색, 삽입, 삭제 연산을 보장한다.

2) 노드들의 관계 정리

- Root 노드 (루트 노드): 이진 탐색 트리의 가장 상위에 있는 노드로, 트리의 시작점
루트 노드는 부모 노드가 없다.

- Parent 노드 (부모 노드): 트리에서 다른 노드와 연결된 노드
각 노드는 최대 하나의 부모 노드를 가질 수 있다.

- Child 노드 (자식 노드): 부모 노드와 연결된 노드
각 노드는 최대 두 개의 자식 노드를 가질 수 있다. (왼쪽 자식 노드와 오른쪽 자식 노드).

- Left Child 노드 (왼쪽 자식 노드): 부모 노드보다 작은 키 값을 가진 노드
각 노드는 최대 하나의 왼쪽 자식 노드를 가질 수 있다.

- Right Child 노드 (오른쪽 자식 노드): 부모 노드보다 큰 키 값을 가진 노드
각 노드는 최대 하나의 오른쪽 자식 노드를 가질 수 있다.

힙(Heap)

- 완전 이진트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간의 대소 관계가 항상 일정한 규칙을 가지는 자료구조

- 보통 최대 힙(max heap)과 최소 힙(min heap) 두 가지 종류가 있다.

1) 이진 탐색 트리와 비교

구분	원소들은 완전히 크기 순 정렬인지?	특정 키 값을 가지는 원소를 빠르게 검색되는지?	부가의 제약 조건은?
이진 탐색 트리	O	O	X
힙	느슨하게 정렬	힘듬	완전 이진 트리여야만 함

2) 종류 분석

- 일반적으로 최댓값 또는 최솟값을 빠르게 찾기 위한 자료구조로 사용된다.

- 최댓값을 빠르게 찾기 위한 경우에는 최대 힙(max heap)

- 최솟값을 빠르게 찾기 위한 경우에는 최소 힙(min heap)

- 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리(Complete Binary Tree)

- 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 완전 이진트리

- 힙은 대개 배열(Array)을 기반으로 구현되며, 이진 힙(binary heap)이 가장 일반적인 형태

3) 연산

- 삽입: 제일 마지막의 노드 뒤에 삽입 후 부모와 대소 관계를 비교해서 위치를 변경한다.

- 삭제: 제일 마지막의 노드와 루트 노드와 위치를 변경 후 마지막 노드를 삭제 후 자식과 대소 관계를 비교해서 위치를 변경한다.

4) 응용

- 우선 순위 큐

Enqueue 할 때 "느슨한 정렬"을 이루고 있도록 한다: O(logn)

Dequeue 할 때 최댓값을 순서대로 추출: O(logn)

- 힙 정렬

정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: O(logn)

삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제: O(logn)

어려웠던 점

- 이진 탐색 트리에서 노드들의 관계

- 환형 큐의 데이터 제거