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

레벨 5는 알고리즘 문제 풀이에서 가장 높은 난이도를 가진 단계입니다. 복잡한 자료구조와 고급 최적화 기법을 자바스크립트로 구현할 수 있어야 하며, 성능과 메모리 효율을 고려한 코드 작성 능력이 요구됩니다.

🧠 핵심 주제

1. 메모이제이션 (Memoization)

중복 계산을 피하기 위한 값 저장 기법입니다.

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

DFS + DP 유형에서도 자주 사용됩니다. 키로 (node, step) 형태의 값을 Map에 저장해 중복 탐색을 방지합니다.

---

2. 캐싱

입력이 동일한 연산 결과를 저장합니다. 메모이제이션과 유사하나 범용적입니다.

const cache = new Map();
function expensiveFn(x) {
  if (cache.has(x)) return cache.get(x);
  const result = complexCalculation(x);
  cache.set(x, result);
  return result;
}

---

3. 동적 프로그래밍 최적화

- 1차원 배열로 메모리 절약

// 0/1 배낭 문제 1D DP
const dp = Array(W + 1).fill(0);
for (let i = 0; i < N; i++) {
  for (let w = W; w >= weights[i]; w--) {
    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
  }
}

- 비트 마스크 + DP

2^N 상태에 대해 메모이제이션 + DFS를 조합한 방식입니다.

---

🏗️ 고급 자료구조

Trie

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

Union-Find (Disjoint Set)

const parent = Array(n+1).fill().map((_, i) => i);
function find(x) {
  if (parent[x] === x) return x;
  return parent[x] = find(parent[x]);
}
function union(a, b) {
  const rootA = find(a), rootB = find(b);
  if (rootA !== rootB) parent[rootB] = rootA;
}

세그먼트 트리 (Segment Tree)

function build(arr, node, start, end) {
  if (start === end) {
    tree[node] = arr[start];
  } else {
    const mid = Math.floor((start + end) / 2);
    build(arr, 2*node, start, mid);
    build(arr, 2*node+1, mid+1, end);
    tree[node] = tree[2*node] + tree[2*node+1];
  }
}

깊은 재귀에 주의. 입력 10^5 이상이면 JS에서 성능 저하 발생 가능.

---

🔁 함수형 스타일 활용

const newArr = arr.map(x => x * 2).filter(x => x % 3 === 0);

함수형 스타일은 불변성을 유지하고, 부작용을 최소화하지만, 메모리와 성능에 영향이 있을 수 있습니다.

---

⚙️ 알고리즘 성능 최적화

• Big-O 줄이기: O(N^2) → O(N log N) 또는 O(N)
• 정렬 + 투 포인터, Map 활용
• 사전 계산 (에라토스테네스의 체 등)

const isPrime = Array(1000001).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= 1000000; i++) {
  if (isPrime[i]) {
    for (let j = i * i; j <= 1000000; j += i) {
      isPrime[j] = false;
    }
  }
}

---

🧪 테스트 & 디버깅

• console.time() / console.timeEnd()으로 시간 측정
• 작은 테스트 케이스로 검증 반복
• 경계 조건 확인 (배열 범위, DP 초기값 등)

---

✅ 최종 팁 요약

• 재귀 깊이, 객체 참조 등 JS 한계 인식
• 불필요한 루프 안 연산 제거
• 캐시, Map 적극 활용
• 정렬 + 이분탐색, 슬라이딩 윈도우, 해시 맵 등의 기법 숙지
• 최종 제출 전 입력 크기 기준 시간복잡도 반드시 계산

---

JavaScript는 자료구조 라이브러리가 부족하지만, 다양한 구현력과 최적화 전략으로 고난이도 문제도 충분히 해결할 수 있습니다. 꾸준한 연습과 사고력 확장을 통해 실전 코딩테스트를 정복합시다 💪