[JS] 코딩테스트 치팅 시트

0. 판단 기준의 뼈대: N 크기 → 허용 시간복잡도

문제를 보면 가장 먼저 입력 크기 N을 확인한다. 채점 서버는 보통 1초에 약 1억(10^8)번 연산을 처리한다고 가정한다. (JS는 다른 언어보다 느려서 보수적으로 5천만~1억 정도로 생각하는 게 안전하다.)

N 크기 허용 복잡도 대표 알고리즘

N ≤ 11	O(N!)	순열 완전탐색, 브루트포스
N ≤ 20~22	O(2^N)	비트마스킹, 부분집합, TSP
N ≤ 100	O(N^3)	플로이드-워셜, 3중 반복 DP
N ≤ 2,000	O(N^2)	2중 반복, 일반 DP
N ≤ 100,000 (10^5)	O(N log N)	정렬, 다익스트라, 이분탐색
N ≤ 1,000,000 (10^6)	O(N) 또는 O(N log N)	투 포인터, 누적합, BFS/DFS
N ≤ 10^8	O(N) 아슬아슬	단순 순회 (보통은 이 크기면 O(log N)/O(1) 요구)

핵심 판단 로직

• N이 10^8 근처인데 O(N^2)면 → 10^16, 절대 안 됨 → 반드시 O(N) 또는 O(N log N)으로 줄여야 함 (누적합, 투 포인터, 이분탐색)
• N이 20 근처면 지수/팩토리얼을 노리라는 신호 → 비트마스킹, 백트래킹
• "최단 거리/최소 횟수" 키워드 → BFS 또는 다익스트라
• "최대/최소/경우의 수" + 선택이 반복 → DP
• "모든 경로/조합을 다 봐야 함" → DFS/백트래킹

각 알고리즘에서 **판단 기준(사이클 여부 + N 크기)**을 계속 언급하겠다.

---

1. DFS (깊이 우선 탐색)

판단 기준

• 그래프/트리를 완전 탐색해야 할 때 (연결 요소 개수, 사이클 존재 여부, 모든 경로 탐색)
• 최단 거리가 목적이 아닐 때 (최단 거리면 BFS)
• 사이클이 있어도 visited 배열로 처리 가능
• N 크기: 정점 V, 간선 E에 대해 O(V + E). 재귀 깊이가 깊으면(V ≥ 10^5 이상) 재귀 스택 오버플로 위험 → 반복문(스택) DFS 고려

왜 이 기준인가

DFS는 한 방향으로 끝까지 파고든 뒤 되돌아온다(재귀=콜스택). 그래서 경로 자체를 쌓아가는 문제나 연결성 판단에 적합하다. 대신 처음 도달한 경로가 최단이라는 보장이 없어서 최단거리엔 부적합하다.

프로토타입 코드

// 인접 리스트 그래프 DFS (재귀)
const graph = [[1, 2], [0, 3], [0], [1]]; // graph[i] = i와 연결된 노드들
const visited = new Array(graph.length).fill(false);

function dfs(node) {
  visited[node] = true;
  // 방문 처리 로직
  for (const next of graph[node]) {
    if (!visited[next]) dfs(next);
  }
}
dfs(0);

// 2D 그리드 DFS (섬 개수 세기 등)
const grid = [[1,1,0],[0,1,0],[0,0,1]];
const R = grid.length, C = grid[0].length;
const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1]; // 상하좌우

function gridDfs(r, c) {
  if (r < 0 || r >= R || c < 0 || c >= C) return;
  if (grid[r][c] !== 1) return; // 물이거나 방문함
  grid[r][c] = 0; // 방문 처리 (덮어쓰기)
  for (let d = 0; d < 4; d++) gridDfs(r + dr[d], c + dc[d]);
}

---

2. BFS (너비 우선 탐색)

판단 기준

• 가중치가 없는(또는 모든 간선 비용이 1인) 그래프에서 최단 거리 / 최소 횟수
• "최소 몇 번 만에", "최단 거리" 키워드
• 사이클 있어도 visited로 처리
• N 크기: O(V + E). 10^5~10^6 정점까지 무난 (재귀 안 쓰므로 스택 오버플로 없음)

왜 이 기준인가

BFS는 시작점에서 가까운 노드부터 레벨 단위로 방문한다(큐 FIFO). 그래서 어떤 노드에 처음 도달한 순간이 곧 최단 거리가 된다. 이게 BFS가 최단거리를 보장하는 핵심 이유다.

프로토타입 코드

function bfs(graph, start) {
  const dist = new Array(graph.length).fill(-1); // -1 = 미방문
  dist[start] = 0;
  const queue = [start];
  let head = 0; // ⚠️ shift()는 O(N)! 인덱스 포인터로 O(1) 처리

  while (head < queue.length) {
    const node = queue[head++];
    for (const next of graph[node]) {
      if (dist[next] === -1) {       // 처음 방문 = 최단
        dist[next] = dist[node] + 1;
        queue.push(next);
      }
    }
  }
  return dist;
}

주의: JS의 array.shift()는 O(N)이라 큐로 쓰면 전체가 O(N^2)로 느려진다. 위처럼 head 인덱스를 올리는 방식으로 O(1) 큐를 구현한다.

---

3. DP (동적 계획법)

판단 기준

• 최적 부분 구조 (큰 문제의 답이 작은 문제의 답으로 구성됨) + 중복 부분 문제 (같은 계산 반복)
• "최대/최소/경우의 수" + 선택이 연속적으로 반복
• 완전탐색하면 지수적인데 상태가 겹칠 때
• N 크기: 상태 개수 × 전이 비용이 시간복잡도. 예를 들어 dp[N]이면 O(N), dp[N][M]이면 O(N·M)

왜 이 기준인가

같은 부분 문제를 여러 번 푸는 낭비를 **메모이제이션(저장)**으로 제거한다. 완전탐색 O(2^N)이 상태 공간 O(N) 또는 O(N^2)로 줄어들기 때문에, N이 커도 상태가 다항식이면 풀린다.

설계 방식 (점화식 4단계)

1. 상태 정의: dp[i]가 정확히 무엇을 의미하는지 한 문장으로 (예: "i번째까지 고려했을 때 최댓값")
2. 점화식: dp[i]를 이전 상태들로 표현 (예: dp[i] = max(dp[i-1], dp[i-2] + a[i]))
3. 초기값(base case): dp[0], dp[1] 등 시작점
4. 계산 순서: 작은 것 → 큰 것 (bottom-up) 또는 재귀+메모 (top-down)

프로토타입 코드

// [1D] 계단 오르기 / 도둑질 유형
// dp[i] = i번째까지의 최대 이익
function rob(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); // 점화식
  }
  return dp[n - 1];
}

// [2D] 0-1 배낭 (knapsack)
// dp[i][w] = i번째 물건까지 고려, 무게한도 w일 때 최대 가치
function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({length: n + 1}, () => new Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w]; // 안 담는 경우
      if (weights[i - 1] <= w) { // 담을 수 있으면
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      }
    }
  }
  return dp[n][W];
}

---

4. 비트마스킹

판단 기준

• N ≤ 20~22 (2^20 ≈ 100만, 2^22 ≈ 400만까지 감당 / 2^25 넘으면 위험)
• 부분집합/방문 상태를 하나의 정수로 압축해야 할 때 (외판원 TSP, 집합 커버)
• "모든 부분집합", "방문한 도시 집합" 같은 상태 표현

왜 이 기준인가

정수의 각 비트를 원소의 포함 여부(0/1)로 쓰면, N개 원소의 부분집합 2^N개를 정수 하나로 표현·비교할 수 있다. N이 20 근처여야 2^N이 계산 가능한 크기라서 이 임계값이 나온다.

프로토타입 코드

// 기본 비트 연산
const state = 0b0000;
const i = 2;
const setBit    = state | (1 << i);       // i번째 켜기
const clearBit  = state & ~(1 << i);      // i번째 끄기
const toggleBit = state ^ (1 << i);       // i번째 토글
const isSet     = (state & (1 << i)) !== 0; // i번째 켜졌나?
const count     = (n) => { let c = 0; while (n) { c += n & 1; n >>= 1; } return c; }; // 켜진 비트 수

// N개 원소의 모든 부분집합 순회
const N = 3;
for (let mask = 0; mask < (1 << N); mask++) {
  const subset = [];
  for (let i = 0; i < N; i++) {
    if (mask & (1 << i)) subset.push(i);
  }
  // subset 처리
}

---

5. 다익스트라 (우선순위 큐)

판단 기준

• 가중치가 있는 그래프의 최단 경로 + 음수 간선 없음
• (음수 간선 있으면 벨만-포드, 모든 쌍이면 플로이드-워셜)
• N 크기: 우선순위 큐로 O(E log V). V가 10^5, E가 수십만이어도 무난
• ⚠️ JS엔 내장 우선순위 큐가 없어서 MinHeap을 직접 구현해야 함

왜 이 기준인가

"현재까지 가장 가까운 정점"을 매번 꺼내 그 이웃을 갱신한다. 가장 가까운 것부터 확정하면 그 값은 다시 바뀌지 않는데(음수 간선이 없어야 성립), 이 "가장 가까운 것 꺼내기"를 힙으로 O(log V)에 해서 전체가 O(E log V)가 된다.

프로토타입 코드

// 최소 힙 (원소: [거리, 노드])
class MinHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  push(v) { this.h.push(v); this.#up(this.h.length - 1); }
  pop() {
    const top = this.h[0], last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this.#down(0); }
    return top;
  }
  #up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p][0] <= this.h[i][0]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  #down(i) {
    const n = this.h.length;
    while (true) {
      let s = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.h[l][0] < this.h[s][0]) s = l;
      if (r < n && this.h[r][0] < this.h[s][0]) s = r;
      if (s === i) break;
      [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
      i = s;
    }
  }
}

function dijkstra(graph, start, n) {
  // graph[u] = [[v, w], ...]  (v로 가는 비용 w)
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  const pq = new MinHeap();
  pq.push([0, start]);

  while (pq.size()) {
    const [d, u] = pq.pop();
    if (d > dist[u]) continue; // 이미 더 짧은 경로로 확정됨
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

최소 힙 → 최대 힙으로 바꾸는 법

두 가지 방법 모두 자주 쓴다.

방법 1: 비교 부호만 반전 (#up, #down의 부등호를 뒤집기)

// #up:   if (this.h[p][0] >= this.h[i][0]) break;
// #down: if (l < n && this.h[l][0] > this.h[s][0]) s = l;
//        if (r < n && this.h[r][0] > this.h[s][0]) s = r;

방법 2: MinHeap 그대로 쓰고 값에 음수 부호 (코드 수정 없이 가장 간편)

const maxPQ = new MinHeap();
maxPQ.push([-value, node]); // 넣을 때 음수로
const [negV, node] = maxPQ.pop();
const value = -negV;        // 꺼낼 때 다시 부호 반전

---

6. DFS + 백트래킹

판단 기준

• 순열/조합/부분집합을 완전탐색하되, 조건에 안 맞으면 **가지치기(pruning)**로 잘라낼 때
• N-Queens, 스도쿠, 조건 만족하는 조합 찾기
• N이 작음 (팩토리얼/지수 규모, N ≤ 11~20)

왜 이 기준인가

완전탐색은 O(N!)/O(2^N)이라 원래 못 푸는데, "이 경로는 답이 될 수 없다"고 판단되는 순간 그 아래 전체를 안 탐색(백트래킹)하면 실제 탐색량이 크게 줄어든다. 그래서 이론상 지수지만 실전에서 통과된다.

프로토타입 코드

// 1~N 중 M개를 고르는 순열 (중복 없이, 가지치기 포함)
function permutations(N, M) {
  const result = [];
  const path = [];
  const used = new Array(N + 1).fill(false);

  function backtrack() {
    if (path.length === M) {         // 목표 도달 → 정답 수집
      result.push([...path]);
      return;
    }
    for (let i = 1; i <= N; i++) {
      if (used[i]) continue;         // ← 가지치기: 이미 쓴 숫자 배제
      // if (!isPromising(i)) continue; // 문제별 추가 가지치기 조건
      used[i] = true;
      path.push(i);
      backtrack();                   // 다음 자리로 진행
      path.pop();                    // ← 백트래킹: 상태 원복
      used[i] = false;
    }
  }
  backtrack();
  return result;
}

핵심 패턴은 선택 → 재귀 → 원복(pop / used=false) 3단 구조. 원복이 없으면 백트래킹이 아니다.

---

7. 누적합 (Prefix Sum)

판단 기준

• 구간 합을 여러 번(Q번) 질의하는데, 배열이 안 바뀔 때
• 매 질의를 O(N)으로 하면 O(N·Q)라 느림 → 전처리 O(N) 후 질의를 O(1)로
• N 크기: N, Q가 각각 10^5~10^6이어도 통과

왜 이 기준인가

누적합 배열을 한 번 만들어두면(O(N)), 임의 구간 합을 **뺄셈 한 번(O(1))**으로 구할 수 있다. 질의가 많을수록 이득이 커진다.

1차원 배열

const arr = [3, 1, 4, 1, 5, 9];
// prefix[i] = arr[0..i-1]의 합, prefix[0] = 0
const prefix = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
  prefix[i + 1] = prefix[i] + arr[i];
}
// 구간 [l, r]의 합 (0-indexed, 양끝 포함)
const rangeSum = (l, r) => prefix[r + 1] - prefix[l];
// 예: [1,3] 합 = prefix[4] - prefix[1] = (3+1+4+1) - (3) = 6

2차원 배열 (여기가 헷갈리는 부분! 그림으로)

목표: 좌상단 (r1,c1)부터 우하단 (r2,c2)까지 직사각형 영역의 합을 O(1)에 구하기.

핵심 아이디어: P[i][j] = "(0,0)부터 (i-1,j-1)까지의 직사각형 전체 합". 즉 원점에서 시작하는 큰 직사각형 합만 미리 저장한다.

(1) 누적합 테이블 만들 때 — 포함배제

P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + arr[i-1][j-1]

그림으로 보면:

  ┌─────────┬───┐
  │    A    │ B │   P[i-1][j]   = A + B   (위쪽 직사각형)
  ├─────────┼───┤   P[i][j-1]   = A + C   (왼쪽 직사각형)
  │    C    │ x │   P[i-1][j-1] = A       (겹치는 왼위)
  └─────────┴───┘   arr[i-1][j-1] = x     (새로 추가되는 칸)

A+B와 A+C를 더하면 A가 두 번 들어가므로, A(=P[i-1][j-1])를 한 번 빼주고, 마지막으로 새 칸 x를 더한다. → P = (A+B) + (A+C) - A + x

(2) 구간 합 구할 때 — 역시 포함배제

sum(r1,c1 ~ r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

그림으로 보면 (구하려는 영역 = 큰 것 - 위 - 왼 + 겹친것):

  ┌───────┬──────────┐
  │   A   │    B     │
  ├───────┼──────────┤
  │   C   │  구하려는 │
  │       │   영역 D  │
  └───────┴──────────┘
  P[r2+1][c2+1] = A+B+C+D   (전체 큰 직사각형)
  P[r1][c2+1]   = A+B       (위쪽 빼기)
  P[r2+1][c1]   = A+C       (왼쪽 빼기)
  P[r1][c1]     = A         (두 번 뺀 A를 다시 더하기)
  → D = 전체 - 위 - 왼 + A

전체 코드

const grid = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
const R = grid.length, C = grid[0].length;
// P는 (R+1) x (C+1), 0번 행/열은 0으로 패딩 → 경계 처리가 깔끔해짐
const P = Array.from({length: R + 1}, () => new Array(C + 1).fill(0));

for (let i = 1; i <= R; i++) {
  for (let j = 1; j <= C; j++) {
    P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1];
  }
}

// (r1,c1) ~ (r2,c2) 영역 합 (0-indexed, 양끝 포함)
function regionSum(r1, c1, r2, c2) {
  return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];
}
// 예: 전체 (0,0)~(2,2) = 45, 중앙 (1,1)~(1,1) = 5

**패딩(0번 행·열을 0으로 두는 것)**이 2D 누적합의 실수 방지 포인트. 인덱스가 i-1, j-1로 밀리는 이유가 이 패딩 때문이다.

---

8. 투 포인터

판단 기준

• 정렬된 배열에서 두 수의 합/조건을 찾거나, 연속 부분 배열의 합/길이 조건을 찾을 때
• O(N^2) 완전탐색을 O(N)으로 줄여야 할 때 (N이 10^5~10^6)
• 슬라이딩 윈도우도 투 포인터의 한 형태

왜 이 기준인가

두 포인터(left, right)가 각각 한 방향으로만 최대 N번 이동하므로 전체가 O(N)이다. 중첩 반복으로 모든 쌍을 보는 O(N^2)와 달리, 조건에 따라 포인터를 "한쪽만" 움직여 불필요한 탐색을 건너뛴다.

프로토타입 코드

// [유형 1] 정렬 배열에서 합이 target인 두 수 찾기 (양끝 포인터)
function twoSum(sorted, target) {
  let l = 0, r = sorted.length - 1;
  while (l < r) {
    const sum = sorted[l] + sorted[r];
    if (sum === target) return [l, r];
    if (sum < target) l++;   // 합이 작으면 왼쪽을 키움
    else r--;                // 합이 크면 오른쪽을 줄임
  }
  return null;
}

// [유형 2] 합이 target 이상인 최소 길이 연속 부분배열 (슬라이딩 윈도우)
function minSubArrayLen(arr, target) {
  let left = 0, sum = 0, minLen = Infinity;
  for (let right = 0; right < arr.length; right++) {
    sum += arr[right];               // 오른쪽 확장
    while (sum >= target) {          // 조건 만족하면 왼쪽 수축
      minLen = Math.min(minLen, right - left + 1);
      sum -= arr[left++];
    }
  }
  return minLen === Infinity ? 0 : minLen;
}

---

9. JS만의 특징 (시간/공간 복잡도)

코딩 테스트에서 JS를 쓸 때 알아야 할 함정과 특성.

배열 메서드

메서드 시간복잡도 공간복잡도 비고

map	O(N)	O(N)	새 배열 생성
filter	O(N)	O(N)	새 배열 생성
reduce	O(N)	O(1)~O(N)	누적값 하나면 O(1)
forEach	O(N)	O(1)	⚠️ break 불가, return은 continue 효과
sort	O(N log N)	O(N)	⚠️ 기본은 문자열 정렬
includes / indexOf	O(N)	O(1)	배열에선 느림 → Set 고려
push / pop	O(1)	-	뒤쪽은 빠름
shift / unshift	O(N)	-	⚠️ 앞쪽 조작은 느림! 큐로 쓰면 O(N^2)
slice	O(N)	O(N)	복사
splice	O(N)	-	중간 삽입/삭제
concat / [...spread]	O(N)	O(N)	복사

반복문

// for...of : 값 순회, break/continue 가능 (코테에서 가장 안전)
for (const x of arr) { if (x < 0) break; }

// for...in : ⚠️ 키(인덱스) 순회, 배열엔 비권장 (프로토타입 키까지 돌 수 있음)

// forEach : break 불가, 콜백 오버헤드 있음 → 성능 민감하면 일반 for 사용

정렬 함정 (가장 흔한 실수)

[10, 2, 1].sort();              // ["1","10","2"] ← 문자열로 정렬됨!
[10, 2, 1].sort((a, b) => a - b); // [1, 2, 10] ← 반드시 비교함수 지정
// 내림차순: (a, b) => b - a

객체 관련

메서드 시간복잡도 비고

Object.keys/values/entries	O(N)	새 배열 생성 (O(N) 공간)
객체 프로퍼티 접근 obj[key]	O(1)	평균
Map.get/set/has	O(1)	삽입 순서 유지, 키에 객체 가능
Set.has/add	O(1)	중복 제거, includes(O(N)) 대체용

// 조회가 많으면 배열 대신 Set/Map: O(N) → O(1)
const seen = new Set(arr);
if (seen.has(x)) { ... }   // O(1)

문자열

연산 시간복잡도 비고

split / join	O(N)
replaceAll	O(N)	모든 매치 치환 (replace는 첫 번째만)
문자열 += 반복	O(N^2) 위험	문자열은 불변 → 배열에 모아 join이 안전
charAt / [i]	O(1)

// ❌ 느림: 매번 새 문자열 생성
let s = ""; for (...) s += ch;
// ✅ 빠름: 배열에 모았다가 한 번에
const parts = []; for (...) parts.push(ch); const s = parts.join("");

숫자 정밀도

0.1 + 0.2 === 0.3;        // false (부동소수점)
2 ** 53 + 1 === 2 ** 53;  // true  → 큰 정수는 BigInt 사용
const big = 9007199254740993n; // BigInt 리터럴
Math.floor(7 / 2);        // 3 (JS 나눗셈은 실수라 몫은 floor 필요)

입력 처리 (백준 등 표준입력)

// Node.js 환경
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);

---

빠른 판단 요약표

문제 키워드 / 조건 선택 알고리즘

최단 거리 + 간선 비용 1	BFS
최단 거리 + 가중치 있음 (음수 X)	다익스트라
모든 경로 / 연결 요소 / 사이클	DFS
조건 만족 조합 + 가지치기	백트래킹
최대/최소/경우의 수 + 반복 선택	DP
N ≤ 20, 부분집합/방문상태	비트마스킹
구간 합 질의 여러 번	누적합
정렬 배열 두 수 / 연속 구간	투 포인터

 

 

다들 화이팅이에요! 특히 시간 복잡도 먼저 계산하고 알고리즘 구현하니까 확실히 문제 푸는 속도가 빨라지네요!

 

+ 추가할 것들

- 이분 탐색, 삼중반복문 알고리즘 이름(기억 안나요)