재구성 출제 고지: 이 편의 문제 4개는 실제 온라인 저지의 기출 문제를 옮긴 것이 아니라, 10·13·14편에서 다룬 DFS/BFS·DP·그리디 유형을 새로운 상황으로 재구성한 문제입니다. · 형식: 백준처럼 표준입력을 읽어 표준출력으로 답을 내는 방식이고, 채점 가능한 순수 함수와 node --test 테스트를 함께 작성합니다.
이 편에서 만드는 파일
coding-test/
└── 18-mock-test-2/
├── 01-robot-shortest-path/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 02-friend-groups/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-max-score-path/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── 04-room-booking/
├── solution.js (+)
└── solution.test.js (+)각 파일은 채점 가능한 순수 함수 solution을 export하고, 파일 맨 아래에 표준입력을 읽어 solution을 호출하는 코드를 따로 둡니다. 이렇게 나누면 node --test로는 solution만 검증하고, 실제 표준입출력 동작은 node 파일이름.js < 입력파일처럼 따로 실행해 확인할 수 있습니다.
문제
문제 1. 청소 로봇 최단 이동 (난이도: 하)
N × M 격자가 주어집니다. 0은 이동 가능한 칸, 1은 벽입니다. 로봇은 (0, 0)에서 시작해 (N-1, M-1)까지 상하좌우로 한 칸씩만 이동할 수 있습니다. 최소 이동 횟수를 구하되, 도착할 수 없으면 -1을 반환하는 solution(grid) 함수를 작성하세요(grid는 숫자 2차원 배열입니다).
입력 예시(표준입력 형식)
3 3
0 0 0
1 1 0
0 0 0출력: 4문제 2. 친구 네트워크 그룹 수 (난이도: 중)
1번부터 n번까지 번호가 매겨진 사람들과 친구 관계 목록 edges(각 원소는 [a, b])가 주어집니다. 서로 직접·간접으로 연결된 사람들을 한 그룹으로 볼 때, 전체 그룹 수를 구하는 solution(n, edges) 함수를 작성하세요.
입력: n = 5, edges = [[1, 2], [2, 3], [4, 5]]
출력: 2문제 3. 드론 착륙 패드 점수 최적화 (난이도: 중상)
패드가 일렬로 n개 있고 각 패드의 점수가 배열 scores(모든 값은 1 이상의 정수)로 주어집니다. 드론은 첫 패드 앞에서 출발해 한 번에 1칸 또는 2칸씩 앞으로 이동하며 착지한 패드의 점수를 모두 얻습니다. 단 3개 연속 패드를 전부 밟을 수는 없고, 반드시 마지막 패드는 밟아야 합니다. 얻을 수 있는 최대 점수를 구하는 solution(scores) 함수를 작성하세요.
입력: scores = [3, 5, 4, 7, 2]
출력: 17문제 4. 스터디룸 예약 최대 승인 개수 (난이도: 상)
스터디룸 하나에 대한 예약 요청이 [시작시간, 종료시간] 쌍의 배열 reservations로 주어집니다. 같은 시간대에는 하나의 예약만 진행할 수 있고, 한 예약의 종료시간에 바로 이어서 다음 예약이 시작할 수 있습니다. 승인할 수 있는 예약의 최대 개수를 구하는 solution(reservations) 함수를 작성하세요.
입력: [[1, 3], [2, 4], [3, 6], [5, 7], [8, 9]]
출력: 3풀이
문제 1 풀이 — 청소 로봇 최단 이동
접근
가중치가 모두 같은 격자에서 최단 거리를 구하는 문제라 BFS를 씁니다. 시작 칸에서 출발해 방문하지 않은 인접 칸을 큐에 넣고, 도착 칸을 꺼내는 순간의 이동 횟수가 답입니다.
복잡도
시간 복잡도는 O(N * M)입니다. 모든 칸을 최대 한 번씩만 큐에 넣고 꺼냅니다.
코드
// coding-test/18-mock-test-2/01-robot-shortest-path/solution.js
// 시간복잡도: O(N * M) — 모든 칸을 최대 한 번씩만 큐에 넣고 꺼낸다
// 공간복잡도: O(N * M) — 방문 배열과 큐를 사용한다
import { readFileSync } from 'node:fs';
export function solution(grid) {
const rowCount = grid.length;
const colCount = grid[0].length;
const visited = Array.from({ length: rowCount }, () => new Array(colCount).fill(false));
const directions = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
const queue = [[0, 0, 0]]; // [행, 열, 이동 횟수]
visited[0][0] = true;
let head = 0;
while (head < queue.length) {
const [row, col, distance] = queue[head];
head += 1;
if (row === rowCount - 1 && col === colCount - 1) {
return distance;
}
for (const [rowDelta, colDelta] of directions) {
const nextRow = row + rowDelta;
const nextCol = col + colDelta;
const inBounds = nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount;
if (!inBounds || visited[nextRow][nextCol] || grid[nextRow][nextCol] === 1) continue;
visited[nextRow][nextCol] = true;
queue.push([nextRow, nextCol, distance + 1]);
}
}
return -1;
}
if (import.meta.url === `file://${process.argv[1]}`) {
const lines = readFileSync(0, 'utf-8').trim().split('\n');
const [rowCount] = lines[0].split(' ').map(Number);
const grid = [];
for (let i = 1; i <= rowCount; i += 1) {
grid.push(lines[i].trim().split(' ').map(Number));
}
console.log(solution(grid));
}테스트
// coding-test/18-mock-test-2/01-robot-shortest-path/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('벽을 피해 최단 이동 횟수를 구한다', () => {
const grid = [
[0, 0, 0],
[1, 1, 0],
[0, 0, 0],
];
assert.strictEqual(solution(grid), 4);
});
test('도착할 수 없으면 -1을 반환한다', () => {
const grid = [
[0, 1],
[1, 0],
];
assert.strictEqual(solution(grid), -1);
});
test('격자가 한 칸이면 이동 없이 0을 반환한다', () => {
assert.strictEqual(solution([[0]]), 0);
});함정
큐에서 앞 원소를 꺼낼 때 queue.shift()를 쓰면 남은 원소를 전부 한 칸씩 당겨야 해 매번 O(n)이 걸리고, 전체로는 O(n²)까지 느려집니다. 이 코드처럼 head 인덱스로 꺼낼 위치만 옮기면 꺼내기가 O(1)로 유지됩니다.
문제 2 풀이 — 친구 네트워크 그룹 수
접근
인접 리스트를 만들고, 방문하지 않은 사람을 시작점으로 DFS를 돌려 연결된 사람을 모두 방문 처리합니다. DFS를 새로 시작한 횟수가 곧 그룹 수입니다.
복잡도
시간 복잡도는 O(n + e)입니다(n은 사람 수, e는 친구 관계 수).
코드
// coding-test/18-mock-test-2/02-friend-groups/solution.js
// 시간복잡도: O(n + e) — 정점과 간선을 각각 한 번씩 방문한다
// 공간복잡도: O(n + e) — 인접 리스트와 방문 배열을 사용한다
import { readFileSync } from 'node:fs';
export function solution(n, edges) {
const adjacencyList = Array.from({ length: n + 1 }, () => []);
for (const [a, b] of edges) {
adjacencyList[a].push(b);
adjacencyList[b].push(a);
}
const visited = new Array(n + 1).fill(false);
let groupCount = 0;
for (let start = 1; start <= n; start += 1) {
if (visited[start]) continue;
groupCount += 1;
const stack = [start];
visited[start] = true;
while (stack.length > 0) {
const current = stack.pop();
for (const neighbor of adjacencyList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
}
return groupCount;
}
if (import.meta.url === `file://${process.argv[1]}`) {
const lines = readFileSync(0, 'utf-8').trim().split('\n');
const [n, edgeCount] = lines[0].split(' ').map(Number);
const edges = [];
for (let i = 1; i <= edgeCount; i += 1) {
edges.push(lines[i].trim().split(' ').map(Number));
}
console.log(solution(n, edges));
}테스트
// coding-test/18-mock-test-2/02-friend-groups/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('연결된 사람들을 하나의 그룹으로 센다', () => {
assert.strictEqual(solution(5, [[1, 2], [2, 3], [4, 5]]), 2);
});
test('친구 관계가 없으면 모두 각자 그룹이다', () => {
assert.strictEqual(solution(3, []), 3);
});
test('전원이 하나로 연결되면 그룹은 1이다', () => {
assert.strictEqual(solution(4, [[1, 2], [2, 3], [3, 4]]), 1);
});함정
재귀 호출로 DFS를 짜면 사람 수가 아주 많을 때 호출 스택이 깊어져 실행 중 오류가 날 수 있습니다. 위 코드처럼 배열을 스택처럼 쓰는 반복문 방식으로 바꾸면 입력 크기가 커져도 안전합니다.
문제 3 풀이 — 드론 착륙 패드 점수 최적화
접근
i번째 패드까지의 최대 점수를 dp[i]라 하면, 마지막에 1칸만 이동해 i번 패드에 착지했거나(이전 착지점은 i-2번), 2칸을 이동해 i-1, i번 패드를 연속으로 밟았을 때(이전 착지점은 i-3번)만 가능합니다. 두 경우 중 큰 값을 취합니다.
복잡도
시간·공간 복잡도 모두 O(n)입니다.
코드
// coding-test/18-mock-test-2/03-max-score-path/solution.js
// 시간복잡도: O(n) — dp 배열을 앞에서부터 한 번씩 채운다
// 공간복잡도: O(n) — dp 배열을 저장한다
import { readFileSync } from 'node:fs';
export function solution(scores) {
const n = scores.length;
if (n === 1) return scores[0];
// dp[i]는 1-indexed i번째 패드까지 밟았을 때의 최대 점수입니다.
const dp = new Array(n + 1).fill(0);
dp[1] = scores[0];
dp[2] = scores[0] + scores[1];
for (let i = 3; i <= n; i += 1) {
const landLastOnly = dp[i - 2] + scores[i - 1];
const landLastTwo = dp[i - 3] + scores[i - 2] + scores[i - 1];
dp[i] = Math.max(landLastOnly, landLastTwo);
}
return dp[n];
}
if (import.meta.url === `file://${process.argv[1]}`) {
const lines = readFileSync(0, 'utf-8').trim().split('\n');
const n = Number(lines[0]);
const scores = [];
for (let i = 1; i <= n; i += 1) {
scores.push(Number(lines[i]));
}
console.log(solution(scores));
}테스트
// coding-test/18-mock-test-2/03-max-score-path/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('연속 3칸 제한을 지키면서 최대 점수를 구한다', () => {
assert.strictEqual(solution([3, 5, 4, 7, 2]), 17);
});
test('패드가 하나면 그 점수를 그대로 반환한다', () => {
assert.strictEqual(solution([9]), 9);
});
test('패드가 둘이면 둘을 합한 점수를 반환한다', () => {
assert.strictEqual(solution([4, 6]), 10);
});함정
dp 배열을 1-indexed로 쓰면서 scores 배열 접근은 0-indexed 그대로 써야 해서, scores[i-1]과 scores[i-2] 중 어느 것을 써야 하는지 헷갈리기 쉽습니다. 각 변수가 몇 번째 패드를 가리키는지 주석으로 명시해두면 오프바이원 실수를 줄일 수 있습니다.
문제 4 풀이 — 스터디룸 예약 최대 승인 개수
접근
종료 시간이 빠른 예약부터 확인하면서, 마지막으로 승인한 예약의 종료 시간 이후에 시작하는 예약만 새로 승인하는 그리디 방법을 씁니다.
복잡도
정렬에 O(n log n), 이후 한 번 훑는 데 O(n)이 걸려 전체 O(n log n)입니다.
코드
// coding-test/18-mock-test-2/04-room-booking/solution.js
// 시간복잡도: O(n log n) — 종료 시각 기준 정렬 후 한 번 순회한다
// 공간복잡도: O(n) — 정렬된 복사본 배열을 만든다
import { readFileSync } from 'node:fs';
export function solution(reservations) {
const sortedByEndTime = [...reservations].sort((a, b) => a[1] - b[1]);
let approvedCount = 0;
let lastEndTime = -Infinity;
for (const [start, end] of sortedByEndTime) {
if (start >= lastEndTime) {
approvedCount += 1;
lastEndTime = end;
}
}
return approvedCount;
}
if (import.meta.url === `file://${process.argv[1]}`) {
const lines = readFileSync(0, 'utf-8').trim().split('\n');
const n = Number(lines[0]);
const reservations = [];
for (let i = 1; i <= n; i += 1) {
reservations.push(lines[i].trim().split(' ').map(Number));
}
console.log(solution(reservations));
}테스트
// coding-test/18-mock-test-2/04-room-booking/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('종료 시간 기준으로 최대 개수를 승인한다', () => {
const reservations = [[1, 3], [2, 4], [3, 6], [5, 7], [8, 9]];
assert.strictEqual(solution(reservations), 3);
});
test('겹치는 예약이 없으면 전부 승인한다', () => {
const reservations = [[1, 2], [2, 3], [3, 4]];
assert.strictEqual(solution(reservations), 3);
});
test('예약이 없으면 0을 반환한다', () => {
assert.strictEqual(solution([]), 0);
});함정
시작 시간 기준으로 정렬해서 그리디를 돌리면 틀립니다. 예를 들어 [1, 100]처럼 아주 긴 예약이 시작 시간이 빨라 먼저 뽑히면, 이후의 짧은 예약들을 모두 막아버려 최적해를 놓칩니다. 반드시 종료 시간 기준으로 정렬해야 합니다.
직접 해보기
- 문제 1을 8방향 이동(대각선 포함)이 가능하도록
directions배열만 수정해 다시 풀어보세요. - 문제 4에서 승인한 예약 개수뿐 아니라 실제로 승인된 예약 목록도 함께 반환하도록
solution을 바꿔보세요.
정답 보기(1번)
// coding-test/18-mock-test-2/01-robot-shortest-path/solution.js (directions만 발췌)
const directions = [
[-1, 0], [1, 0], [0, -1], [0, 1],
[-1, -1], [-1, 1], [1, -1], [1, 1],
];자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
| BFS 결과가 실제 최단 거리보다 크게 나옴 | visited 표시를 큐에 넣을 때가 아니라 꺼낼 때 함 | 큐에 넣는 즉시 visited를 true로 표시 |
| DFS/BFS로 그룹을 세는데 그룹 수가 실제보다 많게 나옴 | 양방향 간선인데 한쪽 방향만 인접 리스트에 추가함 | adjacencyList[a].push(b)와 adjacencyList[b].push(a)를 함께 추가 |
| DP 배열 인덱스가 하나씩 어긋남 | 1-indexed와 0-indexed를 섞어 씀 | 배열마다 어떤 인덱스 방식인지 주석으로 고정 |
| 그리디로 짠 정렬 기준이 시작 시간이라 답이 틀림 | 문제를 배열 순서가 아니라 종료 시간 기준으로 정렬해야 함을 놓침 | 구간 선택 문제는 종료 시간 정렬을 기본으로 검토 |