데브코스/Week 2

Week 2 - 3

out_of_anjoong 2024. 3. 27. 17:02

Queue

특징

  • FIFO(First In First Out) ※스택은 LIFO(Last In First Out)

주요 개념

  • size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
  • isEmpty(): 현재 큐가 비어 있는지를 판단
  • enqueue(x): 데이터 원소 x를 큐에 추가
  • dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거하며 원소 값 반환
  • front(), peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환

활용

  • 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
  • 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
  • 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

 

Circular Queue(환형 큐)

특징

  • 정해진 개수의 저장 공간을 빙 돌려가며 이용
  • 배열로 큐를 구현했을 때 맨 앞 원소를 제거하면 나머지 원소들을 앞으로 댕겨야 하는 복잡함을 해결하기 위해 사용

주요 개념

  • size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
  • isEmpty(): 현재 큐가 비어 있는지를 판단
  • isFull() : 큐에 데이터 원소가 꽉 차있는지를 판단
  • enqueue(x): 데이터 원소 x를 큐에 추가
  • dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거하며 원소 값 반환
  • front(), peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환

 

Priority Queue(우선순위 큐)

특징

  • 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
  • Enqueue 할 때 우선순위 순서를 유지하도록 or Dequeue 할 때 우선순위 높은 것을 선택 하는 방식으로 구현
  • 배열 보다는 연결 리스트가 시간적으로는 유리함.

활용

  • 운영체제의 CPU 스케쥴러

 

Trees(트리)

특징

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

주요 개념

  • root(뿌리) 노드 : 부모 노드가 없는 노드
  • leaf(잎) 노드 : 자식 노드가 없는 노드
  • Internal(내부) 노드 : 그 나머지 노드들은 
  • sibling(형제) : 같은 부모 노드를 공유하는 노드들
  • ancestor(조상) : 부모 노드의 부모 노드
  • decendant(후손) 노드 : 자식 노드의 자식 노드
  • height(높이) 최대 수준(level) + 1
  • 서브트리 : 어느 노드부터 후손 노드들까지의 트리
  • degree(차수) : 어떤 노드의 자식(서브트리)의 수

Binary Tree(이진 트리)

특징

  • 모든 노드의 차수가 2 이하인 트리
  • Full Binary Tree(포화 이진 트리) : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리(height = k, 노드의 개수 = 2^k - 1)
  • Complete Binary Tree(완전 이진 트리) : 높이가 k일 때, k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진트리, k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진트리

주요 개념

  • size() : 현재 트리에 포함되어 있는 노드의 수를 구함
  • depth() : 현재 트리의 깊이(height)를 구함
  • traversal(순회)
    • Depth First traverSal(깊이 우선 순회) - DFS
      • in-order traversal(중위 순회) : left subtree -> 자기 자신 -> right subtree
      • pre-order traversal(전위 순회) : 자기 자신 -> left subtree -> right subtree
      • post-order traversal(후위 순회) : left subtree -> right subtree -> 자기 자신
    • Breadth First traverSal(넓이 우선 순회) - BFS
      • 수준(level)이 낮은 노드를 우선으로 방문
      • 같은 수준의 노드들 사이에서는
        - 부모 노드의 방문 순서에 따라 방문
        - 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
      • queue(큐)를 이용.

 

Binary Search Tree(이진 탐색 트리)

특징

  • 모든 노드에 대해서 아래 두가지 성질을 만족하는 이진 트리
    • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작음
    • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큼
  • 데이터 원소의 추가, 삭제가 용이
  • 공간 소요가 큼

주요 개념

  • insert(key, data) : 트리에 주어진 데이터 원소를 추가
  • remove(key) : 특정 원소를 트리로부터 삭제
    • 키(key)를 이용해서 노드를 찾는다.
      • 해당 키의 노드가 없으면, 삭제할 것도 없음
      • 찾은 노드의 부모 노드도 알고 있어야 함.
    • 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조 정리 필요.
  • lookup(key) : 특정 원소를 검색
  • inrorder() : 키의 순서대로 데이터 원소를 나열
  • min(), max() : 최소, 최대 키를 가지는 원소를 탐색

Heap(힙)

특징

  • 이진 트리의 한 종류 (이진 힙 - binary heap)
  • 루트 노드가 언제나 최댓값(max heap) 또는 최솟값(min heap)을 가짐
  • 완전 이진 트리여야 함
  • 힙은 배열을 이용하는게 편함

주요 개념

  • 노드 번호 m 을 기준
    • 왼쪽 자식 노드의 번호 : 2 * m
    • 오른쪽 자식 노드의 번호 : 2 * m + 1
    • 부모 노드의 번호 : m // 2
  • 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서
  • 원소 삽입 O(logn)
    1. 비어있는 가장 마지막 배열에 원소 삽입
    2. 부모 노드와 키 값을 비교하며 부모 노드의 키 값 보다 작을 때 까지 교환
  • 원소 삭제
    1. 루트 노드의 제거 : 원소들 중 최댓값
    2. 트리 마지막 자리 노드을 임시로 루트 노드의 자리에 배치
    3. 자식 노드와 값을 비교하여 가장 큰 키 값 찾을 때 까지 비교하며 내려감.

응용

  • 우선 순위 큐
    • Enqueue 할 때 "느슨한 정렬"을 이루고 있도록 함 : O(logn)
    • Dequeue 할 때 최댓값을 순서대로 추출 : O(logn)
    • 양방향 연결 리스트로 구현한 것 보다 효율적
  • Heap Sort(힙 정렬)
    • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logn)
    • 삽입이 끝나면 힙이 비게 될 때 까지 하나씩 삭제 : O(logn)
    • 원소들이 삭제된 순서가 원소들의 정렬 순서
    • 알고리즘의 복잡도 : O(nlogn)

활용 문제