Skip to Content
WebJavaScriptJavaScript 코딩테스트21. 심화 모의고사

이 문서의 네 문제는 학습용으로 새로 구성한 문제입니다. 먼저 solution 함수만 직접 완성한 뒤 풀이를 확인하세요.

응시 방법

  • 각 문제의 매개변수와 반환값부터 확인합니다.
  • 제한사항을 근거로 목표 복잡도를 정합니다.
  • 예시와 직접 만든 경계 사례를 손으로 검산합니다.
  • 코드는 정답 값을 return하는 solution 함수로 작성합니다.

문제 1. 전체 서버 전파 시간

서버 수 n, [from,to,time] 연결 배열 edges, 시작 서버 start가 주어집니다. 모든 서버에 신호가 도착하는 최소 시간을 반환하고 도달할 수 없는 서버가 있으면 -1을 반환하세요.

함수 시그니처: solution(n, edges, start)

제한사항

  • 서버 번호는 1부터 n까지입니다.
  • 모든 time은 양의 정수입니다.

입출력 예

매개변수반환값
4, [[1,2,1],[1,3,4],[2,3,2],[3,4,1]], 14

풀이와 코드 보기

핵심 패턴: 최소 힙을 사용하는 다익스트라

class MinHeap {
  constructor() { this.values = []; }
  push(item) {
    this.values.push(item);
    let index = this.values.length - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.values[parent][0] <= item[0]) break;
      this.values[index] = this.values[parent];
      index = parent;
    }
    this.values[index] = item;
  }
  pop() {
    if (this.values.length === 1) return this.values.pop();
    const root = this.values[0];
    const last = this.values.pop();
    let index = 0;
    while (index * 2 + 1 < this.values.length) {
      let child = index * 2 + 1;
      const right = child + 1;
      if (right < this.values.length && this.values[right][0] < this.values[child][0]) child = right;
      if (this.values[child][0] >= last[0]) break;
      this.values[index] = this.values[child];
      index = child;
    }
    this.values[index] = last;
    return root;
  }
  get size() { return this.values.length; }
}
 
function solution(n, edges, start) {
  const graph = Array.from({ length: n + 1 }, () => []);
  for (const [from, to, time] of edges) graph[from].push([to, time]);
  const distance = Array(n + 1).fill(Infinity);
  distance[start] = 0;
  const heap = new MinHeap();
  heap.push([0, start]);
  while (heap.size) {
    const [cost, node] = heap.pop();
    if (cost !== distance[node]) continue;
    for (const [next, weight] of graph[node]) {
      const nextCost = cost + weight;
      if (nextCost >= distance[next]) continue;
      distance[next] = nextCost;
      heap.push([nextCost, next]);
    }
  }
  const answer = Math.max(...distance.slice(1));
  return Number.isFinite(answer) ? answer : -1;
}
  • 시간복잡도: O((V + E) log V)
  • 공간복잡도: O(V + E)
  • 경계 사례: 도달하지 못한 서버가 하나라도 있으면 -1

문제 2. 인접하지 않은 최대 보상

일렬로 놓인 보상 배열 rewards가 주어집니다. 서로 인접한 두 보상을 함께 선택하지 않을 때 얻을 수 있는 최대 합을 반환하세요.

함수 시그니처: solution(rewards)

제한사항

  • rewards의 길이는 1 이상 1,000,000 이하입니다.
  • 모든 보상은 0 이상의 정수입니다.

입출력 예

매개변수반환값
[2, 7, 9, 3, 1]12

풀이와 코드 보기

핵심 패턴: 현재 미선택과 선택 두 경우의 최댓값

function solution(rewards) {
  let twoBack = 0;
  let oneBack = 0;
  for (const reward of rewards) {
    const current = Math.max(oneBack, twoBack + reward);
    twoBack = oneBack;
    oneBack = current;
  }
  return oneBack;
}
  • 시간복잡도: O(n)
  • 공간복잡도: O(1)
  • 경계 사례: 원소가 하나면 그 보상 반환

문제 3. 사전순 배포 순서

작업 수 n과 [before,after] 선행 관계 dependencies가 주어집니다. 가능한 배포 순서 중 번호가 사전순으로 가장 작은 배열을 반환하고 사이클이면 빈 배열을 반환하세요.

함수 시그니처: solution(n, dependencies)

제한사항

  • 작업 번호는 1부터 n까지입니다.
  • n은 1 이상 100,000 이하입니다.

입출력 예

매개변수반환값
4, [[1,3],[2,3],[3,4]][1,2,3,4]

풀이와 코드 보기

핵심 패턴: 진입차수와 최소 힙을 결합한 위상 정렬

class NumberHeap {
  constructor() { this.values = []; }
  push(value) {
    this.values.push(value);
    let index = this.values.length - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.values[parent] <= value) break;
      this.values[index] = this.values[parent];
      index = parent;
    }
    this.values[index] = value;
  }
  pop() {
    if (this.values.length === 1) return this.values.pop();
    const root = this.values[0];
    const last = this.values.pop();
    let index = 0;
    while (index * 2 + 1 < this.values.length) {
      let child = index * 2 + 1;
      if (child + 1 < this.values.length && this.values[child + 1] < this.values[child]) child += 1;
      if (this.values[child] >= last) break;
      this.values[index] = this.values[child];
      index = child;
    }
    this.values[index] = last;
    return root;
  }
  get size() { return this.values.length; }
}
 
function solution(n, dependencies) {
  const graph = Array.from({ length: n + 1 }, () => []);
  const indegree = Array(n + 1).fill(0);
  for (const [before, after] of dependencies) {
    graph[before].push(after);
    indegree[after] += 1;
  }
  const heap = new NumberHeap();
  for (let node = 1; node <= n; node += 1) {
    if (indegree[node] === 0) heap.push(node);
  }
  const order = [];
  while (heap.size) {
    const node = heap.pop();
    order.push(node);
    for (const next of graph[node]) {
      indegree[next] -= 1;
      if (indegree[next] === 0) heap.push(next);
    }
  }
  return order.length === n ? order : [];
}
  • 시간복잡도: O((V + E) log V)
  • 공간복잡도: O(V + E)
  • 경계 사례: 처리한 작업 수가 n보다 작으면 사이클

문제 4. 연결 그룹 수

정점 수 n과 연결 쌍 links가 주어집니다. 서로 이어진 정점들을 한 그룹으로 볼 때 전체 그룹 수를 반환하세요.

함수 시그니처: solution(n, links)

제한사항

  • 정점 번호는 0부터 n - 1까지입니다.
  • 같은 연결이 반복될 수 있습니다.

입출력 예

매개변수반환값
5, [[0,1],[1,2],[3,4]]2

풀이와 코드 보기

핵심 패턴: 서로 다른 대표를 합칠 때마다 그룹 수 감소

function solution(n, links) {
  const parent = Array.from({ length: n }, (_, index) => index);
  const find = (node) => {
    if (parent[node] !== node) parent[node] = find(parent[node]);
    return parent[node];
  };
  let groups = n;
  for (const [a, b] of links) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) continue;
    parent[rootB] = rootA;
    groups -= 1;
  }
  return groups;
}
  • 시간복잡도: O((V + E) α(V))
  • 공간복잡도: O(V)
  • 경계 사례: 연결이 없으면 n 반환

심화 모의고사 점검표

  • 문제를 읽자마자 자료구조를 정하지 않고 제한사항부터 확인했는가
  • 풀이의 정당성을 한두 문장으로 설명할 수 있는가
  • 빈 결과, 한 원소, 중복, 도달 불가 같은 경계를 확인했는가
  • 시간복잡도와 공간복잡도를 직접 계산했는가

확인 문제

문제 14지선다
전체 서버 전파 시간의 핵심 풀이 패턴은?
문제 24지선다
전체 서버 전파 시간 풀이의 시간복잡도는?
문제 34지선다
전체 서버 전파 시간에서 확인할 경계 사례는?
문제 44지선다
인접하지 않은 최대 보상의 핵심 풀이 패턴은?
문제 54지선다
인접하지 않은 최대 보상 풀이의 시간복잡도는?
문제 64지선다
인접하지 않은 최대 보상에서 확인할 경계 사례는?
문제 74지선다
사전순 배포 순서의 핵심 풀이 패턴은?
문제 84지선다
사전순 배포 순서 풀이의 시간복잡도는?
문제 94지선다
사전순 배포 순서에서 확인할 경계 사례는?
문제 104지선다
연결 그룹 수의 핵심 풀이 패턴은?
문제 114지선다
연결 그룹 수 풀이의 시간복잡도는?
문제 124지선다
연결 그룹 수에서 확인할 경계 사례는?
문제 134지선다
제한사항을 먼저 읽는 가장 중요한 이유는?
문제 144지선다
정렬이 필요하지만 원본 배열도 이후 사용한다면?
문제 154지선다
채점기가 확인하는 최종 결과는?

참고 자료

Last updated on
20. 중급 모의고사