큐(Queue)

  • 배열로 구현한 큐
  • 양방향 연결리스트로 구현한 큐


큐 활용

  1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우

(ex. Producer 에서 자료를 생성하여 큐에 쌓아놓고, Consumer들이 하나씩 꺼내서 사용함)


  1. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우


환형 큐(Circular Queue)

정해진 개수의 저장 공간을 빙 돌려가며 이용

(큐를 배열로 구현한 경우, 큐의 길이에 비례해서 데이터를 추출하는데 시간이 오래 걸리는 점을 개선한 형태)


우선순위 큐(Priority Queue)

FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

(ex. 운영체제의 CPU 스케쥴러)


두가지 방식 존재

  • Enqueue 시 우선순위 순서 유지
  • Dequeue 시 우선순위 높은 것을 선택


두가지 재료 유형

  • 선형 배열을 이용한 우선순위 큐
  • 연결 리스트를 이용한 우선순위 큐

=> 연결 리스트를 이용한 것이 더 유리하다. 우선순위에 따라 줄을 세워서 중간에 삽입하는 경우가 많기 때문에 연결 리스트 특성을 이용할 때 이점이 있기 때문.

메모리 측면에서는 선형 배열이 더 유리하기 때문에 무조건 유리한 것은 아니다.


트리(Trees)

정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조

  • 루트(Root) 노드
  • 리프(Leaf) 노드
  • 내부(Internal) 노드

로 구성되어 있다.


특징

  • 2차원 자료 구조
  • 부모, 자식 관계가 존재


차수(Degree) ( *헷갈리기 쉽다.)

⇒ 해당 노드가 가진 자식 노드의 수 ( Leaf 노드의 경우 Degree는 모두 0 )


이진트리

빈 트리(Empty Trees) 이거나 자식 노드 수가 2개 이하인 트리 (재귀 호출 시 비어있는 서브 트리를 만나기 때문)


포화 이진 트리(Full Binary Tree)

모든 레벨에서 노드들이 모두 채워져 있는 이진 트리 (높이가 k이고 노드의 개수가 2^k-1인 이진트리


완전 이진 트리(Complete Binary Tree)

높이가 k인 완전 이진 트리

레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리

레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리 (레벨 k-2(끝에서 두번째 레벨)까지는 포화 이진 트리 형태이고,

마지막 레벨에서만 왼쪽부터 채워져 있으면 된다)


이진 트리의 추상적 자료 구조

연산의 정의

  • size() - 현재 트리에 포함되어 있는 노드의 수를 구함
  • depth() - 현재 트리의 깊이(또는 높이)를 구함
  • 순회(traversal)


Node

  • Data
  • Left Child
  • Right Child


이진 트리의 순회(traversal)

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

    ⇒ 재귀(Recursion) 이용

kinds_of_order
(출처 : https://yahma.tistory.com/20)


in-order
(출처 : https://kingpodo.tistory.com/28)


pre-order
(출처 : https://kingpodo.tistory.com/28)


post-order
(출처 : https://kingpodo.tistory.com/28)


  • 넓이 우선 순회 (breast first traversal)

    ⇒ 부모 노드를 방문한 후, 방문해야 할 자식 노드들을 기록하기 적합한 자료 구조인 큐(Queue)를 사용한다.

    • 수준(level)이 낮은 노드 우선 방문 (root 노드부터 시작)

    • 같은 수준에서는 부모 노드의 방문 순서에 따라 방문하고,

      왼쪽 자식 노드를 우선으로 방문


이진 탐색 트리(binary search trees)

⇒ 모든 노드에 대해

왼쪽 서브트리의 데이터는 모두 현재 노드의 값보다 작고

오른쪽 서브트리의 데이터는 모두 현재 노드의 값보다 크다.

이를 만족하는 이진 트리를 말한다.

(중복되는 데이터 원소는 없는 것으로 가정)

데이터 검색에 용이하다.


정렬된 배열을 이용한 이진 탐색을 비교한다면?

good : 데이터 원소의 추가 및 삭제가 용이하다.

bad : 공간 소요가 크다.

두 경우 모두 대략 시간복잡도는 O(logn)에 비례함. (이진 탐색 트리는 항상 그런건 아니다)


메서드 정의

  • insert(key, data)
  • remove(key)
  • lookup(key) : 원소 검색
  • inorder() : 키를 기준으로 데이터 나열
  • min(), max()


*효율적이지 못 한 경우

=> 한쪽으로 치우치는 경우는 선형 탐색과 같은 시간복잡도를 가질 수 있다.

=> 높이의 균형을 유지한다면, O(logn)의 탐색 복잡도를 보장한다.

(ex. AVL tree, Red-black tree 등의 경우, 삽입, 삭제 연산이 보다 복잡하다)


힙(Heap)

⇒ 루트 노드가 항상 최댓값 혹은 최솟값을 가진다. ( 최대 힙(max heap), 최소 힙(min heap))

완전 이진 트리이다.


힙은 이진 탐색 트리에 비해..

  • 완전 이진 트리여야 하는 제약 존재
  • 힙은 노드의 키 값을 고려하지만, 느슨해서 검색에는 적합하지 않다.


메서드 정의

  • __init()__
  • insert(item)
  • remove() : 최대 혹은 최소값(root node) 반환하고 삭제


배열을 이용하여 이진 트리 구현

완전 이진 트리 형태이므로 각 노드에 번호를 부여하여 사용할 수 있다.

번호를 BFS 순서로 매긴다면,

<이진 트리의="" 표현="" 이미지=""> 완전 이진 트리라는 특성 때문에 트리에서 노드의 추가/삭제는 마지막 노드에서 일어나는데, 그렇기 때문에 배열을 이용하여 구현하는 것이 괜찮다고 할 수 있는 것이다.
**최대 힙의 원소 삽입 프로세스** 1. 트리의 끝에 노드 추가 2. 부모 노드 보다 크다면 교체 (조건 만족하지 않을 때까지 반복) ⇒ 시간 복잡도는 O(log\*2n) (최악의 경우에도 log_2n) \*\*\*[장점]\_\*\*
**최대 힙의 원소 삭제 프로세스** 1. Root 노드(최대값)와 마지막 노드를 교체 2. 마지막 노드 삭제 3. 최대 힙 규칙에 맞게 노드 순서 재구성 1. 왼쪽 자식, 자신, 오른쪽 자식 중 최대값을 구함 2. 최대값이 자신이 아니라면, 최대값 노드와 교체 3. 재귀 호출
**최대/최소 힙을 응용한 알고리즘과 자료 구조** - 우선 순위 큐 (priority queue) - Enqueue 시 느슨한 정렬을 이루고 있는 점 - Dequeue 시 최댓값부터 추출한다는 점 - 힙 정렬(heap sort) - 힙에 삽입 (O(log_2n))+(O(log_2n)) 힙에서 삭제 ⇒ n개 삽입 후 n개 삭제니까 총 시간 복잡도는 O(nlog_2n) 이진>