JavaScript 코딩테스트 대비 정리 (레벨 4)

레벨 4에서는 심화된 알고리즘과 자료구조를 JavaScript로 다룰 수 있어야 합니다. 그래프와 트리 등 복잡한 구조의 탐색, 백트래킹, 동적 계획법, 그리고 언어의 한계를 뛰어넘는 최적화 기법 등이 요구됩니다.

그래프 탐색 (DFS/BFS 활용)

• 그래프 표현: 인접 리스트/행렬로 표현
• 방문 처리: 배열 또는 Set 사용
• 다중 컴포넌트 탐색 필요
• 가중치 그래프: 다익스트라(우선순위 큐 필요), 0-1 BFS, A* 알고리즘

트리 구조 및 조작

• 트리 순회: 전위, 중위, 후위 (DFS/BFS 활용)
• 트라이(Trie) 구현:

  class TrieNode {
  constructor() { this.children = {}; this.end = false; }
  }
  class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.end = true;
  }
  }

• 세그먼트 트리: 배열 기반, 1-based index 사용

정렬 커스터마이징

• 다중 기준 정렬:

  arr.sort((a, b) => {
  if (a.key1 !== b.key1) return a.key1 - b.key1;
  return b.key2 - a.key2;
  });

• 안정 정렬이 필요할 경우 인덱스 추가 또는 직접 stable sort 구현

우선순위 큐 (Heap)

• MaxHeap 예시:

  class MaxHeap {
  constructor() { this.heap = [null]; }
  push(value) {
    this.heap.push(value);
    let i = this.heap.length - 1;
    while (i > 1 && this.heap[Math.floor(i/2)] < this.heap[i]) {
      [this.heap[i], this.heap[Math.floor(i/2)]] = [this.heap[Math.floor(i/2)], this.heap[i]];
      i = Math.floor(i/2);
    }
  }
  pop() {
    if (this.heap.length === 1) return null;
    const top = this.heap[1];
    this.heap[1] = this.heap.pop();
    let i = 1;
    while (true) {
      let left = 2*i, right = 2*i+1, largest = i;
      if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
      if (right < this.heap.length && this.heap[right] > this.heap[largest]) largest = right;
      if (largest === i) break;
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      i = largest;
    }
    return top;
  }
  }

DFS + 백트래킹

const result = [];
const temp = [];
function backtrack(start) {
  result.push([...temp]);
  for (let i = start; i < arr.length; i++) {
    temp.push(arr[i]);
    backtrack(i + 1);
    temp.pop();
  }
}

• 활용 예시: 순열, 조합, N-Queen, 부분집합, 제약 충족 해 찾기 등

동적 계획법 (DP)

• 하향식 (memoization):

  const memo = {};
  function fib(x) {
  if (x < 2) return x;
  if (memo[x]) return memo[x];
  return memo[x] = fib(x-1) + fib(x-2);
  }

• 상향식 (tabulation):

  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
  dp[i] = dp[i-1] + dp[i-2];
  }

• 2차원 DP:

  const dp = Array.from({length: N}, () => Array(M).fill(0));

• 비트마스크 DP: dp[mask][i] 패턴

비트 연산 테크닉

• 부분집합 생성: for (let mask = 0; mask < (1 << n); mask++)
• 비트카운트: x.toString(2).split('0').join('').length
• XOR 활용: 스왑 또는 고유값 추출

JS 구현 시 주의사항

1. 대용량 처리: readFileSync + 정규식 분할
2. 메모리 관리: 큰 문자열은 Array.join, 큰 배열은 복사 자제
3. 정수 범위: BigInt 사용 필요시 구분
4. 깊은 비교: 직렬화 또는 고유 키 활용
5. Node.js 특성: 싱글스레드 환경

---

레벨 4는 JS로 알고리즘 문제를 풀면서 언어적 한계와 성능 최적화까지 고려하는 수준입니다. 위 기법들을 정확히 이해하고 활용하는 것이 중요합니다.