javascript 코테를 위한 도구들

1. Heap: 빠르게 찾고, 정렬하는 마법의 자료구조

Heap은 최소값이나 최대값을 빠르게 찾을 수 있는 트리 기반의 자료구조입니다. Min Heap에서는 가장 작은 값이, Max Heap에서는 가장 큰 값이 루트에 위치하게 됩니다.

핵심 메서드

• insert: 새 값을 삽입하고, 부모 노드와 비교하여 필요한 경우 위로 이동합니다 (bubble-up).
• extractMin (혹은 extractMax): 루트 값을 삭제하고 맨 마지막 값을 루트로 올린 후, 자식 노드와 비교하여 아래로 내려갑니다 (bubble-down).

JavaScript 예시

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[parentIdx] <= this.heap[idx]) break;
      [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
      idx = parentIdx;
    }
  }

  extractMin() {
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return min;
  }

  bubbleDown() {
    let idx = 0;
    while (true) {
      let left = 2 * idx + 1;
      let right = 2 * idx + 2;
      let smallest = idx;
      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === idx) break;
      [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
      idx = smallest;
    }
  }
}

---

2. Combination: 가능한 모든 조합 찾기

조합(Combination)은 주어진 리스트에서 특정 길이의 부분집합을 구하는 방법입니다. 예를 들어 [1, 2, 3]에서 길이 2의 조합을 구하면 [1,2], [1,3], [2,3]과 같이 됩니다.

핵심 메서드

• getCombinations: 재귀적으로 배열을 순회하면서 고정된 요소와 나머지 요소의 조합을 반복하여 구합니다.

JavaScript 예시

function getCombinations(arr, length) {
  if (length === 1) return arr.map(el => [el]);
  let combinations = [];
  arr.forEach((fixed, idx, self) => {
    const rest = self.slice(idx + 1);
    const restComb = getCombinations(rest, length - 1);
    const attached = restComb.map(comb => [fixed, ...comb]);
    combinations.push(...attached);
  });
  return combinations;
}

---

3. Linked List: 간단하지만 유연한 리스트

Linked List는 배열과 달리 요소들이 포인터로 연결된 리스트입니다. 삽입과 삭제가 쉽고, 배열의 순차 접근보다 효율적일 수 있습니다.

핵심 메서드

• append: 리스트 끝에 요소를 추가합니다.
• find: 원하는 값을 탐색합니다.

JavaScript 예시

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) this.head = newNode;
    else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = newNode;
    }
  }
}

---

4. Graph: 관계를 시각화하는 자료구조

Graph는 여러 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 각 노드가 다른 노드와 연결됩니다. 이를 통해 다양한 관계나 연결을 표현할 수 있습니다.

핵심 메서드

• addVertex: 노드를 추가합니다.
• addEdge: 두 노드 간의 간선을 추가합니다.

JavaScript 예시

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(vertex) {
    this.adjList.set(vertex, []);
  }

  addEdge(vertex, edge) {
    this.adjList.get(vertex).push(edge);
    this.adjList.get(edge).push(vertex);
  }
}

---

5. Trie: 검색 최적화를 위한 트리 구조

Trie(트라이)는 문자열 검색에 특화된 트리 자료구조입니다. 각각의 노드는 문자열의 문자 하나를 나타내며, 이를 통해 빠른 검색이 가능합니다.

핵심 메서드

• insert: 문자열을 노드에 따라 추가합니다.
• search: 문자열이 Trie에 있는지 확인합니다.

JavaScript 예시

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) node.children[char] = new TrieNode();
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

---

6. DFS & BFS: 깊이 우선, 너비 우선 탐색

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프를 탐색하는 방법으로, DFS는 한 경로를 끝까지 탐색한 후 돌아오고, BFS는 한 레벨씩 탐색합니다.

DFS (재귀)

function dfs(graph, start, visited = new Set()) {
  if (!visited.has(start)) {
    console.log(start);
    visited.add(start);
    for (let neighbor of graph[start]) {
      dfs(graph, neighbor, visited);
    }
  }
}

BFS (큐 사용)

function bfs(graph, start) {
  let queue = [start];
  let visited = new Set(queue);
  while (queue.length) {
    let vertex = queue.shift();
    console.log(vertex);
    for (let neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

---