[TIL] JavaScript 주요 문법(5)

송인재·2023년 6월 10일

데브코스

목록 보기
5/8
post-thumbnail

Tree(트리)

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다.

트리의 특징

  • 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
  • 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
  • 루트에서 특정 정점으로 가는 경로는 유일하다.

이진 트리

  • 이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.

이진 트리의 특징

  • 정점 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다.
  • 정점이 N개인 포화 또는 완전 이진 트리의 높이는 log N이다.
  • 높이가 h인 포화 이진트리는 2h2^h-1개의 정점을 가진다.
  • 일반적인 이진 트리를 사용하는 경우는 많지 않다. (이진 탐색 트리, 힙, AVL트리, 레드 블랙 트리)
이진 트리의 구현 방법
- 배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있다.

이진 트리(Array)

// 0번 인덱스는 편의를 위해 비워둔다.
// Left = Index * 2
// Right = Index * 2 + 1
// Parent = floor(Index / 2)
const tree = [
  undefined,
  9,
  3, 8,
  2, 5, undefined, 7
  undefined, undefined, undefined, 4

이진 트리 (Linked List)

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor(node) {
    this.root = node;
  }
  
  display() {
    const queue = new Queue();
    queue.enqueue(this.root);
    while (queue.size) {
      const currentNode = queue.dequeue();
      if (currentNode.left) queue.enqueue(currentNode.left);
      if (currentNode.right) queue.enqueue(currentNode.right);
    }
  }
}

Heap(힙)

우선순위 큐 : FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐

힙
- 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징을 가지고 있다.

힙의 특징

  • 우선순위가 높은 요소가 먼저 나가는 특징을 가진다.
  • 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min-Heap)이 있다.

힙 요소 추가 알고리즘

  • 요소가 추가될 때는 트리의 가장 마지막에 정점에 위치한다.
  • 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
  • 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
  • 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가진다.

힙 요소 제거 알고리즘

  • 요소 제거는 루트 정점만 가능하다.
  • 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
  • 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
  • 두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.
  • 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(log N) 시간 복잡도를 가진다.

힙 요소 추가

class MaxHeap {
  constructor() {
    this.heap = [null];
  }
  
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
    
    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;
      
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }
  pop() {
    const returnValue = this.heap[1];
    const.heap[1] = this.heap.pop();
    
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    
    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.haep[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    
    return returnValue;
  }
}

Tries(트라이)

- 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

트라이의 특징

  • 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
  • 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
  • L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
  • 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

트라이 구조

  • 루트는 비어있다.
  • 각 간선(링크)은 추가될 문자를 키로 가진다.
  • 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
  • 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.
class Node {
  constructor(value = "") {
    this.value = value;
    this.children = new Map();
  }
}

class Tree {
  constructor() {
    this.root = new Map();
  }
  
  insert(string) {
    let currentNode = this.root;
    
    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(
          char, new Node(currentNode.value + char);
          )
      }
      currentNode = currentNode.children.get(char);
      }
    }
  
  has(string) {
    let currentNode = this.root;
    
    for (const chcar of string) {
      if (!currentNode.children.has(char)) {
        return false;
      }
      currentNode = currentNode.children.get(char);
    }
    return true;
  }
}

정렬

요소들을 일정한 순서대로 열거하는 알고리즘

정렬의 특징

  • 정렬 기준은 사용자가 정할 수 있다.
  • 크게 비교식과 분산식 정렬로 나눌 수 있다.
  • 대부분의 언어가 빌트인으로 제공해준다.
  • 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다.

비교식 정렬

버블 정렬

  • 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
  • O(n2)O(n^2) 시간 복잡도를 가진다.

선택 정렬

  • 선택한 요소와 가장 우선순위가 높은 요소를 교호나하는 정렬 알고리즘
  • O(n2)O(n^2) 시간 복잡도를 가진다.

삽입 정렬

  • 선택한 요소를 삽일할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘
  • O(n2)O(n^2) 시간 복잡도를 가진다.

분산식 정렬

합병 정렬

  • 최선과 최악이 같은 안정적인 정렬 알고리즘
  • O(nlogn) 시간 복잡도를 가진다.

퀵 정렬

  • 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬
  • O(nlogn) 시간 복잡도를 가진다.
const array = [5, 9, 10, 3, 8, 3, 2];
// 다음과 같이 그냥 정렬하면 ASCII 문자 순서로 정렬되어 우리가 원하는 숫자 크기대로 정렬되지 않는다.
array.sort();
console.log(array); // 10, 2, 3, 4, 8, 9

array.sort((a, b) => a - b) // 오름차순 정렬
console.log(array); // 2, 3, 3, 4, 8, 9, 10

array.sort((a, b) => b - a); // 내림차순 정렬
console.log(array); // 10, 9, 8, 4, 3, 3, 2

이진 탐색

- 정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘
- O(logn)만큼 시간복잡도가 걸린다.

이진 탐색의 특징

  • 반드시 정렬이 되어있어야 사용할 수 있다.
  • 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
  • O(logn) 시간복잡도인만큼 상당히 빠르다.

이진 탐색 트리

  • 이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진 탐색 트리의 문제점

  • 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
  • 그런 경우 순차 탐색과 동일한 시간복잡도를 가진다.
  • 이를 해결하기 위해 AVL트리나 레드-블랙 트리가 이용될 수 있다.

Array

const array = [1, 1, 5, 124, 400, 599, 1004, 2876, 8712];

function binarySearch(array, findValue) {
  let left = 0;
  let right = array.length - 1;
  let mid = Math.floor((left + right) / 2);
  while (left < right) {
    if (array[mid] === findValue) {
      return mid;
    }
    
    if (array[mid] < findValue) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
    
    mid = Math.floor((left + right) / 2);
  }
  
  return -1;
}

Binary Search Tree

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    
    let currentNode = this.root;
    while (currentNode !== null) {
      if (currentNode.value < value) {
        if (currentNode.right === null) {
          currentNode.right = newNode;
          break;
        }
        currentNode = currentNode.right;
        } else {
          if (currentNode.left === null) {
              currentNode.left = newNode;
              break;
            }
            currentNode = currentNode.left;
        }
    }
  }
  
  has(value) {
    let currentNode = this.root;
    while (currentNode !== null) {
      if (currentNode.value ===value) {
        return true;
      }
      
      if (currentNode.value < value) {
        currentNode = currentNode.right;
      } else {
        currentNode = currentNode.left;
      }
    }
    return false;
  }
}
profile
송인재
꿈을 꾸고 도전하기🌟
이전 포스트

[TIL] JavaScript 주요 문법(4)

다음 포스트

[TIL] JavaScript 주요 문법(6)

0개의 댓글