직접 구현한 Queue vs shift()

• shift의 시간복잡도는 O(N)이지만 N의 수가 적은 경우 JS엔진에서 최적화를 시켜주기 때문에 큐에 들어갈 데이터가 적은 경우 사용해도 좋음(N이 적은 경우직접 구현한 Queue보다 빠르게 동작할 수도 있음)
• 요소가 많아질 경우 직접 구현한 Queue가 shift 함수보다 빠르게 동작함

트리

• 방향 그래프의 일종으로 노드을 가리키는 간선이 하나 밖에 없는 구조를 가짐

특징

• 루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가짐
• 노드가 N개인 트리의 간선의 개수 = N - 1
• 루트에서 특정 노드로 가는 경로는 유일함

이진 트리

• 각 노드가 최대 2개의 자식 노드를 가지는 트리
• 완전 이진 트리: 마지막 레벨을 제외하고 모든 노드가 채워진 상태
• 포화 이진 트리: 모든 정점이 채워진 상태
• 편향 트리: 한 방향으로만 노드가 이어진 상태
• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등에 사용함

이진 트리의 특징

• 노드가 N개일 때 이진 트리는 최약의 경우 높이가 N이 될 수 있음
• 노드가 N개인 포화 또는 완전 이진트리의 높이는 logN
• 높이가 h인 포화 이진트리는 (2^h) - 1개의 노드을 가짐

트리의 구현 방법

• 인접 행렬, 인접 리스트 방식, 연결 리스트 방식으로 구현할 수 있다.
• JS로 이진 트리 구현

  // 0번 indx는 편의를 위해 사용하지 않음
  // left = index * 2
  // right = index * 2 + 1
  // parent = floor(index / 2)
  const binaryTree = [
    undefined,
    9,
    1, 2,
    3, 4, undefined, 5,
    undefined, undefined, undefined, 6,
  ]

힙(Heap)

• 이전 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소 삽입, 삭제 시 바로 정렬됨
• 힙은 우선 순위 큐를 구현할 때 가장 적합한 방법이다.
  • 우선 순위 큐: 일반적인 큐와 다르게 우선 순위가 높은 요소가 먼저 나가는 큐 ⇒ 자료구조가 아닌 개념

힙의 특징

• 우선 순위가 높은 요소를 루트 노드로 배치함
• 루트가 가장 큰 값 = Max Heap, 루트가 가장 작은 값 = Min Heap

힙 요소 추가 알고리즘

1. 추가할 요소를 트리의 가장 마지막 노드로 위치
2. 추가 후 부모 노드보다 우선 순위가 높다면 부모 노드와 순서를 바꿈
3. 위의 과정을 반복하여 루트 노드에 우선 순위가 높은 노드가 위치하도록 함
4. 완전 이진 트리의 높이는 logN 이므로 힙의 요소 추가 알고리즘은 O(logN)의 시간복잡도를 가짐

힙 요소 제거 알고리즘

1. 루트 노드에서 요소를 제거
2. 루트 노드가 제거된 후 가장 마지막 노드가 루트에 위치
3. 루트 노드의 두 자식 노드 중 더 우선순위가 높은 노드와 바꿈
4. 두 자식 노드가 우선순위가 더 낮을 때 까지 반복
5. 힙 요소 추가 알고리즘과 동일하게 O(logN)의 시간복잡도를 가짐

힙의 구현 방법

// Max Heap으로 구현
class Heap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    this.heap.push(value);
    let curIdx = this.heap.length - 1;
    let parentIdx = Math.floor(curIdx / 2);

    while (parentIdx !== 0 && this.heap[parentIdx] < value) {
      const temp = this.heap[parentIdx];
      this.heap[parentIdx] = value;
      this.heap[curIdx] = temp;

      curIdx = parentIdx;
      parentIdx = Math.floor(curIdx / 2);
    }
  }

  pop() {
    const returnVal = this.heap[1];
    this.heap[1] = this.heap.pop();

    let curIdx = 1;
    let leftIdx = 2;
    let rightIdx = 3;
    while (
      this.heap[curIdx] < this.heap[leftIdx] ||
      this.heap[curIdx] < this.heap[rightIdx]
    ) {
      const temp = this.heap[curIdx];
      if (this.heap[leftIdx] < this.heap[rightIdx]) {
        this.heap[curIdx] = this.heap[rightIdx];
        this.heap[rightIdx] = temp;
        curIdx = rightIdx;
      } else {
        this.heap[curIdx] = this.heap[leftIdx];
        this.heap[leftIdx] = temp;
        curIdx = leftIdx;
      }
      leftIdx = curIdx * 2;
      rightIdx = curIdx * 2 + 1;
    }
    return returnVal;
  }
}

트라이

• 문자열을 효율적으로 저장하고 탐색하기 위한 트리 형태의 자료구조
• 검색어 자동완성, 사전 찾기 등에 응용 가능
• 문자열 탐색에 단순 비교보다 효율적임
• 문자열을 길이를 L이라고 할때 탐색, 삽입이 O(L)만큼 걸림
• 각 노드에 자식에 대한 링크를 전부 가지고 있기에 많은 저장 공간을 사용

트라이 구조

• 루트는 공백
• 각 간선(링크)은 추가될 문자를 키로 가짐
• 각 노드는 이전 노드의 값 + 간선의 키를 값으로 가짐
• 해시 테이블과 연결 리스트를 이용하여 구현

트라이 구현

[JS] Trie 자료구조 구현

정렬 알고리즘

• 정렬은 크게 비교식 정렬과 분산식 정렬로 나눌 수 있음
• 정렬 알고리즘 비교 사이트 => Sorting Algorithms Animations
  

비교식 정렬

• 다른 요소와 비교를 통해 정렬하는 방식
• 버블, 선택, 삽입 정렬이 있다.

분산식 정렬

• 요소를 분산하여 정렬하는 방식
• 분할 정복: 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리 후 합치는 전략
• 합병, 퀵 정렬이 있다.

[JS] 정렬 알고리즘 정리 및 구현

JS의 sort()

const arr = [5, 9, 3, 10, 1, 2];

// JS의 sort는 default로 ASCII 문자 순서로 정렬하기 때문에 주의
arr.sort()
console.log(arr); // [ 1, 10, 2, 3, 5, 9 ]
// ASCII 문자 순서로 정렬하기 때문에 10이 앞에 위치하게 됨

// 오름차순 정렬
arr.sort((a, b) => a - b);
console.log(arr); // [ 1, 2, 3, 5, 9, 10 ]

// 내림차순 정렬
arr.sort((a, b) => b - a);
console.log(arr); // [ 10, 9, 5, 3, 2, 1 ]

이진 탐색

• 정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
• 시간복잡도는 O(log n)

이진 탐색 특징

• 반드시 정렬 상태에서 사용해야함
• 배열 또는 이진 트리를 이용하여 구현

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 생성됨 ⇒ 순차 탐색과 동일한 시간복잡도를 가짐
• 위의 문제를 해결하기 위해 AVL 트리, 레드-블랙 트리를 사용할 수 있다.