[만나는 그 순간] 채점 화면에 Wrong Answer가 네 번 연속 떴다. 두 객체가 각자 방향과 속도로 움직이다가 최초로 같은 좌표에 놓이는 시각을 구하는 문제였고, 처음 봤을 땐 시뮬레이션이라기보다 산술 문제에 가까워 보였다. 명령어 인덱스를 따라 각 객체의 최종 좌표를 누적 합산하고, 그 값을 비교하는 코드 한 벌을 짜서 제출했다.
루프 범위와 조건문을 바꿔가며 세 번을 더 제출했지만 같은 답이 돌아왔다. 같은 문제에서 네 번 연속 오답을 받은 시점부터, 풀이 방식 자체가 틀렸다고 의심하기 시작했다.
코드트리 [만나는 그 순간] 채점 화면
이상한 일은, 4회차 글에서 북마크로 경계값 실수를 잡겠다고 다짐해 놓고 6회차에 들어 시뮬레이션 앞에서 같은 형태로 다시 어긋났다는 점이다. 깃허브 CHOOSLA/Algorithm의 SW Expert Academy/1954 폴더를 열어보면 한 문제 안에 answer.cpp와 main.cpp가 나란히 들어 있다. 달팽이 숫자 — 격자 회전 시뮬레이션 — 를 한 번에 통과하지 못해 정답 풀이를 따로 옮겨 적어두고, 같은 문제를 본인 코드로 다시 한 번 풀어 둔 흔적이다. 1206, 1247에도 같은 짝이 있다. 시뮬레이션 유형만 만나면 한 번에 통과하지 못해 따로 다시 풀어 두는 패턴이 옛 폴더부터 반복되고 있었다.
처음 시뮬레이션 유형을 배울 때의 정의는 단순했다. "문제에 적힌 규칙을 그대로 따라 구현하면 되는 유형" 정도로 이해하고 있었다. 그 정의로도 작은 문제들은 풀렸다. 그러나 트레일 2의 시뮬레이션 Ⅰ, Ⅱ 구간을 풀고 나서야 그 정의가 좁았다는 사실이 보였다. 시뮬레이션은 "문제를 따라 구현하는 유형"이 아니라, "시간의 흐름을 손실 없이 옮겨 적는 사고" 였다. 한 번에 결과로 점프하려는 직관을 경계하지 않으면, 어떤 자료구조를 골라도 같은 자리에서 실수한다.
문제는 한 회의 실수가 아니라, 시뮬레이션이라는 유형 자체에 대한 사고 습관의 구멍이었다. 6회차 미션이 "나만의 방식으로 알고리즘 개념을 설명하기"였기에, 이 글은 그 구멍을 메우기 위해 코드트리 트레일 2의 시뮬레이션 Ⅰ, Ⅱ를 끝까지 풀고 나서야 비로소 잡힌 하나의 골격 시간에 따른 시뮬레이션 을 정리한다.
"시뮬레이션"이라는 이름이 가린 진짜 문제
시뮬레이션이 어렵게 느껴지는 이유는 알고리즘이 까다로워서가 아니다. 자료구조도 단순하고, 시간복잡도도 대체로 여유롭다. 그런데도 매번 무너졌던 이유를 한 달 동안 트레일 2의 시뮬레이션 Ⅰ, Ⅱ 약 44문제를 풀고 나서야 알았다.
문제는 "한 번에 결과로 점프하려는 직관" 이었다.
"A가 10초 동안 총 10미터를 갔다, B가 10초 동안 -3미터에 있다, 그러면 둘은 만나지 않는다." 머리로는 이렇게 한 번에 계산하는 게 빠르다. 그러나 시뮬레이션 문제는 종종 그 10초 사이의 3초나 5초 시점에서 둘이 스쳤는지를 묻는다. 도착지만 비교하는 코드는 중간 경로 전체를 통째로 잃어버린다.
그 자리에서 깨달은 건 하나였다.
시뮬레이션은 결과를 빠르게 계산하는 문제가 아니다. 시간의 흐름을 손실 없이 그대로 옮겨 적는 문제다.
이 인식이 트레일 2의 모든 시뮬레이션 문제를 푸는 공통 골격이 된다.
패턴: 매 1초마다 상태를 한 줄씩 기록하는 골격
손에 익은 골격을 한 줄로 압축하면 이렇다.
상태(state) = 시뮬레이션이 추적해야 하는 모든 정보
시간(time) = 1초 (혹은 1 step) 단위로만 전진
기록(log) = 매 시간마다 상태를 그대로 남겨둔다
코드로 옮기면 항상 다음 두 종류 중 하나가 된다.
// 형태 A: 배열에 매 초의 상태를 적어 둔다 (사후 비교용)
int p[MAX_TIME + 1];
int t = 1;
for (각 명령) {
for (명령의 소요시간만큼) {
p[t] = p[t - 1] + delta; // 1초만큼 상태 갱신
t++;
}
}
// 형태 B: 매 초 상태를 갱신하되, 그 자리에서 종료 조건만 확인한다
state s = initial;
for (int t = 1; t <= T; ++t) {
s = step(s); // 1초만큼 상태 전진
if (조건(s)) { /* 처리 */ }
}
A는 나중에 다시 봐야 하는 시점이 생기는 문제에 쓰고, B는 결정이 그 시각에 즉시 끝나는 문제에 쓴다. 트레일 2의 시뮬레이션 Ⅰ·Ⅱ는 거의 전부 이 두 형태로 환원된다.
형태 A로 푼 결과는 항상 시간 인덱스를 행으로 갖는 표 한 장으로 정리된다. 예를 들어 A가 R 방향으로 3초, L 방향으로 2초 움직이고, B가 L 방향으로 2초, R 방향으로 3초 움직이는 경우 두 객체의 위치 배열은 다음과 같이 채워진다.
시각 t
1
2
3
4
5
p1 (A 위치)
+1
+2
+3
+2
+1
p2 (B 위치)
-1
-2
-1
0
+1
p1[t] == p2[t]
✗
✗
✗
✗
✓
매 시각의 위치를 한 줄씩 적어 두면, "두 객체가 같은 좌표에 놓이는 최초 시각"이라는 질문은 마지막 행을 왼쪽에서 오른쪽으로 훑는 한 줄로 끝난다. 한 번에 결과로 점프하던 사고가, 표를 옮겨 적는 사고로 바뀌는 지점이다. 이제 그 환원을 네 문제로 직접 따라가 본다.
적용 1 — 만나는 그 순간: 두 시간선을 나란히 적어 비교한다
[만나는 그 순간]의 핵심은 두 객체가 최초로 같은 좌표에 있는 시각이다. 결과로 한 번에 점프하면 중간이 사라진다. 그래서 A와 B의 위치를 매 1초 단위로 따로 적은 뒤, 같은 시각 인덱스끼리 비교해야 한다. 이게 형태 A다.
int p1[1000001], p2[1000001];
// 1. A의 1초당 위치 기록
int idx = 1;
for (int i = 0; i < n; ++i) {
for (int time = 0; time < t[i]; ++time) {
p1[idx] = p1[idx - 1] + (d[i] == 'L' ? -1 : 1);
idx++;
}
}
int total_time = idx - 1;
// 2. B의 1초당 위치 기록 (동일 방식)
idx = 1;
for (int i = 0; i < m; ++i) {
for (int time = 0; time < t2[i]; ++time) {
p2[idx] = p2[idx - 1] + (d2[i] == 'L' ? -1 : 1);
idx++;
}
}
// 3. 같은 시각 인덱스끼리 비교
int result = -1;
for (int i = 1; i <= total_time; ++i) {
if (p1[i] == p2[i]) { result = i; break; }
}
여기서 중요한 점은 두 가지다.
첫째, 명령어 단위가 아니라 시간 단위로 인덱스를 쌓는다. 명령어 인덱스로 루프를 돌리면 A의 3번째 명령과 B의 3번째 명령은 서로 다른 시각이라서 비교가 무의미해진다.
둘째, 시간 인덱스가 객체마다 동일한 의미를 가져야 한다. p1[5]와 p2[5]는 둘 다 시뮬레이션 시작 후 5초가 흐른 순간의 위치여야 한다. 이 동기화가 깨지면 결과가 어긋난다.
배열 크기 설정도 같은 맥락에서 사고가 필요하다. 명령어가 1000개이고 각 명령의 시간이 최대 1000이면, 누적 시간은 최대 1,000,000초까지 늘어난다. 습관적으로 int p[10000]처럼 작게 잡으면 런타임 오류가 난다. 시간 단위 배열의 크기는 명령 개수가 아니라 누적 시간의 상한이라는 점이 시뮬레이션의 첫 번째 함정이다.
[만나는 그 순간] Accepted 통과 화면 (시간 단위 풀이로 재제출 후)
적용 2 — 좌우로 움직이는 로봇: "만남 횟수"로 질문이 바뀌면, 한 줄을 더 본다
[좌우로 움직이는 로봇]은 만나는 그 순간과 골격이 같지만, 묻는 것이 다르다. 최초 시각이 아니라 두 로봇이 만나는 횟수다. 그리고 한 로봇이 멈춰도 다른 로봇이 계속 움직일 수 있다.
같은 형태 A를 쓰되, 비교 단계에서 두 가지를 추가한다.
int max_time = max(time_a, time_b);
int now_time = 1;
int result = 0;
while (now_time <= max_time) {
int now_a = min(now_time, time_a - 1);
int now_b = min(now_time, time_b - 1); // 멈춘 로봇은 마지막 위치 고정
int prev_a = min(now_time - 1, time_a - 1);
int prev_b = min(now_time - 1, time_b - 1);
if (pos1[now_a] == pos2[now_b]
&& pos1[prev_a] != pos2[prev_b]) { // 직전엔 달랐다가 지금 같아짐
result++;
}
now_time++;
}
여기서 새로 들어온 사고 둘.
첫째, 멈춤 처리. 명령이 끝난 객체는 마지막 위치에 그대로 머문다. 그래서 now_a를 time_a - 1로 클램프한다. 형태 A의 장점이 여기서 드러난다 — 매 초 상태를 다 적어뒀기 때문에, 멈춘 객체도 마지막 인덱스를 그냥 다시 읽으면 된다.
둘째, 만남의 정의를 시간 두 줄로 확장. "지금 같다"만으로는 같은 칸에 계속 머무는 동안 매 초 카운트가 누적된다. "직전엔 달랐고 지금은 같다"로 두 줄을 비교해야 만남이 한 번으로 카운트된다.
만나는 그 순간과 골격은 같은데 묻는 질문 하나가 바뀌었을 뿐인데, 비교 단계에 두 줄이 늘었다. 시뮬레이션 문제의 변형은 대부분 이런 식이다. 상태 기록부는 같고, 질문에 맞게 해석부만 갈린다.
적용 3 — 작은 구슬의 이동: 상태가 (y, x)가 되어도 골격은 그대로다
[작은 구슬의 이동]은 격자 위에서 한 칸씩 움직이다가 벽에 부딪히면 반대 방향으로 튕긴다. 형태 B를 쓰는 사례다.
int moving[4][2] = {{1,0}, {0,1}, {0,-1}, {-1,0}};
int y = r, x = c;
for (int time = 0; time < t; ++time) {
int ny = y + moving[dir][0];
int nx = x + moving[dir][1];
if (inRange(ny, nx)) { y = ny; x = nx; }
else { dir = 3 - dir; }
}
상태는 이제 1차원 정수가 아니라 (y, x, dir) 셋이다. 그러나 시간은 여전히 1초씩 전진하고, 매 시각마다 상태가 한 번씩만 갱신된다. 골격은 정확히 같다.
여기서 따로 정리해 둘 만한 디테일이 dir = 3 - dir 한 줄이다. 방향 배열을 {D, R, L, U} 순으로 잡으면 인덱스 0과 3이 서로 반대, 1과 2가 서로 반대다. 그래서 3 - dir이 곧 반대 방향이 된다. 매번 if-else로 방향을 뒤집을 필요가 없다. 방향 배열을 어떻게 배치하느냐가 반사 로직의 코드 길이를 결정한다 — 이건 트레일 2를 풀면서 가장 늦게 손에 익은 사고였다.
적용 4 — 거울에 레이저 쏘기 2: 형태 A와 B를 한 풀이 안에 묶고, 풀기 전 8케이스를 종이에 적어 두었다
[거울에 레이저 쏘기 2]는 트레일 2 시뮬레이션 Ⅱ의 "어려움" 난이도 문제다. n×n 격자 외곽 임의 지점에서 k번째 진입 방향으로 레이저를 쏘면, 격자 안의 /``\ 거울에 부딪힐 때마다 방향이 바뀐다. 레이저가 격자를 빠져나갈 때까지 이동한 칸 수를 구해야 한다.
이 문제는 풀이 자체에 앞서 종이를 먼저 꺼냈다. 거울 두 종류와 진입 방향 네 가지의 조합(총 8개 케이스) 가 회전 방향에 어떻게 매핑되는지를 표로 먼저 정리한 뒤에 코드로 옮겼다. 종이 위의 표가 정리되기 전엔 코드를 한 줄도 쓰지 못했다. 도입에서 [만나는 그 순간]을 네 번 틀린 뒤에야 연필을 잡았다고 적었는데, 골격이 손에 붙고 나니 어려운 시뮬레이션 문제는 처음부터 종이를 먼저 꺼내는 순서로 바뀌었다.
거울 두 종류( / , \ ) × 진입 방향 4가지 = 8케이스 회전 매핑을 종이에 정리한 표
골격의 관점에서 이 문제가 흥미로운 이유는, 형태 A와 B를 한 풀이 안에서 순서대로 사용해야 한다는 점이다.
int dirs[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}}; // 우·하·좌·상 (시계방향)
// 1단계 (형태 A): 외곽 4n 지점의 좌표와 진입 방향을 미리 다 기록해 둔다
int coord[4 * n][2] = {0};
int entry[4 * n] = {0};
int y = 0, x = 0, dir = 0;
coord[0][0] = y; coord[0][1] = x;
for (int i = 2; i <= 4 * n; ++i) {
int ny = y + dirs[dir][0];
int nx = x + dirs[dir][1];
if (ny >= 0 && ny < n && nx >= 0 && nx < n) { y = ny; x = nx; }
else { dir = (dir + 1) % 4; }
coord[i - 1][0] = y;
coord[i - 1][1] = x;
entry[i - 1] = (dir + 1) % 4; // 진입 방향은 격자 안쪽 90도 회전
}
// 2단계 (형태 B): k번째 진입 지점부터 1칸씩 진행하며 거울 반사 처리
int now_y = coord[k - 1][0];
int now_x = coord[k - 1][1];
int now_dir = entry[k - 1];
int count = 0;
while (now_y >= 0 && now_y < n && now_x >= 0 && now_x < n) {
if (grid[now_y][now_x] == '/') {
// 좌·우 진입(0, 2)이면 좌회전, 상·하 진입(1, 3)이면 우회전
now_dir = (now_dir == 0 || now_dir == 2) ? (now_dir + 3) % 4
: (now_dir + 1) % 4;
} else {
// '\' 거울은 반대 규칙
now_dir = (now_dir == 0 || now_dir == 2) ? (now_dir + 1) % 4
: (now_dir + 3) % 4;
}
now_y += dirs[now_dir][0];
now_x += dirs[now_dir][1];
count++;
}
1단계에서 외곽 진입 지점을 형태 A로 미리 다 기록해 두는 이유는, k라는 입력이 "k번째 외곽 칸"을 뜻하기 때문이다. 매번 외곽을 다시 도는 대신 한 번 기록해 두면 coord[k - 1]로 O(1)에 진입 지점을 꺼낼 수 있다. 형태 A의 본래 용도 — 나중에 다시 봐야 하는 시점이 생기는 문제 — 와 정확히 일치한다.
2단계는 형태 B다. 진입 지점에서 1칸씩 전진하면서 거울을 만날 때마다 방향만 바꾼다. 종료 조건은 좌표가 격자 바깥으로 나가는 시점.
이 풀이의 핵심 디테일은 회전 표현에 있다. 좌회전을 (dir - 1 + 4) % 4 대신 (dir + 3) % 4 로 쓰면 4를 따로 더해 음수 모듈로를 피할 필요가 없다. C++에서 (-1) % 4는 3이 아니라 -1이라, 좌회전을 일반적인 방식으로 쓰면 인덱스가 음수로 튀어 디버깅이 어렵다. 방향 배열을 시계방향으로 배치한 뒤 좌회전을 (dir + 3) % 4로 표현하는 한 줄이, 8케이스 표를 코드로 옮기는 과정 전체에서 가장 짧고 안전한 길이었다.
네 문제를 관통하는 한 줄
코드트리 트레일 2 시뮬레이션 Ⅰ, Ⅱ 진행도 화면
네 문제는 표면적으로 모두 다르다. 두 객체 만남, 만남 횟수, 격자 반사, 명령어 처리. 그러나 풀이의 골격은 동일하다.
문제
시간 단위
상태
기록 방식
종료 조건
만나는 그 순간
1초
위치 (정수)
두 객체 배열 (형태 A)
p1[i] == p2[i] 최초 시각
좌우 로봇
1초
위치 (정수)
두 객체 배열 (형태 A)
만남 횟수 누적
작은 구슬 이동
1초
(y, x, dir)
매 초 in-place (형태 B)
T초 후 위치
거울에 레이저 쏘기 2
외곽 칸 / 1칸
(y, x, dir)
외곽 4n 배열 (A) + 진행 in-place (B)
격자 밖 이탈 시각
공통 골격은 이렇다.
1. 상태가 무엇인지 명확히 정의한다 (정수? 좌표? 방향까지?)
2. 시간을 1단위로만 전진시킨다 (한 번에 점프 금지)
3. 매 시각마다 상태를 갱신하거나, 배열에 적어 둔다
4. 종료 조건은 질문에 맞춰 비교부에만 작성한다
그동안 시뮬레이션 문제를 풀 때마다 "이 문제는 어떻게 접근하지?"부터 시작했다. 그래서 매번 처음 보는 문제처럼 느껴졌다. 트레일 2의 시뮬레이션 Ⅰ·Ⅱ를 처음부터 끝까지 풀고 나서야 보였다 — 시뮬레이션 문제는 골격이 같고, 매번 바뀌는 것은 상태의 정의와 종료 조건뿐이다. 한 번에 점프하지 않고 매 시각을 1단위로만 적어 내려가는 사고가 손에 붙으면, 문제별 변형은 비교부의 한두 줄로 끝난다.
이 사실이 5월의 1차 갭체크에서 노란불이 켜졌던 시뮬레이션 Ⅰ과, 그 위의 시뮬레이션 Ⅱ를 한 달간 갈아 풀어내고 나서야 비로소 한 문장으로 잡힌 것이다. 6월의 2차 갭체크에서 시뮬레이션 Ⅰ이 약점 목록에서 빠진 것은 정답률이 올라서가 아니라 이 골격이 손에 붙어서였다.
옛 SWEA 1954 main.cpp가 보여준 같은 손버릇
한 달간 트레일 2를 풀고 나서 도입에서 언급한 SW Expert Academy/1954/main.cpp를 다시 열어봤다. 달팽이 숫자를 본인 코드로 다시 풀어 둔 그 파일이다.
int rotate(int num) {
num = num + 1;
if (num == 4) return 0;
return num;
}
옛 main.cpp는 방향 인덱스의 순환을 위해 rotate(num)이라는 별도 헬퍼 함수를 만들어 두었다. 그러나 같은 종류의 방향 회전은 트레일 2의 [작은 구슬의 이동]에서 dir = 3 - dir 한 줄로 끝났고, [거울에 레이저 쏘기 2]에서는 시계방향 배열 위에 좌회전을 (dir + 3) % 4, 우회전을 (dir + 1) % 4로 표현해 두 회전을 한 줄씩으로 압축했다. 방향 배열의 배치를 어떻게 잡느냐에 따라 코드 한 줄이 헬퍼 함수 여러 줄을 대체한다는 사고가 옛 풀이에는 없었다.
옛 폴더에 남은 시뮬레이션 풀이를 다시 훑어보면 비슷한 형태의 실수가 반복적으로 보인다.
명령어 단위로 루프를 돌렸다 (시간 단위가 아님)
도착지 좌표만 계산하고 중간 경로를 비교하지 않았다
배열 크기를 명령 개수 기준으로 잡아 시간 누적을 감당하지 못했다
방향 배열의 배치를 활용하지 않아 회전 로직이 불필요하게 길어졌다
같은 사람이 같은 종류의 실수를 다른 문제에서 반복하고 있었다는 사실이 옛 폴더에 그대로 남아 있었다. 한 번에 결과로 점프하려는 손버릇이, 시뮬레이션 유형 앞에서는 매번 비슷한 자리에서 어긋났다. 이번 6회차에 들어 [만나는 그 순간]에서 네 번 틀린 것도 우연한 실수가 아니라, 직관을 경계하는 사고가 아직 손끝까지는 내려오지 않았다는 신호였다.
이제 시뮬레이션 문제를 만나면 먼저 연필을 잡고 매 초의 상태를 적어 내려간다. 상태를 정의하고, 시간을 1단위로 쪼개고, 매 시각의 기록을 한 줄씩 남긴다. 골격이 손에 붙고 나면, 시뮬레이션은 직관에 기대지 않고 시간 흐름을 그대로 옮겨 적는 절차로 바뀐다.
마치며 — 다음 전선은 그래프와 동적 계획법이다
2차 갭체크 결과 — 시뮬레이션 Ⅰ이 약점 목록에서 빠진 화면
5회차 글에서 시뮬레이션 Ⅰ과 완전탐색이 갭체크 약점 목록에서 빠졌다고 적었다. 대신 DP Ⅰ과 BFS가 새 빨간불로 들어왔다. 이번 6회차에 시뮬레이션을 하나의 골격으로 정리하면서 깨달은 것은, 유형별 직관을 한 줄짜리 골격으로 압축할 수 있을 때 비로소 그 유형이 손에 붙는다는 점이었다.
다음 회차에는 BFS를 같은 방식으로 정리해볼 생각이다. 큐와 방문 배열, 그리고 "처음 방문한 시각이 최단 거리"라는 골격을 한 줄로 잡고 나면, 시뮬레이션이 그랬듯 변형 문제들이 비교부의 한두 줄로 정리될 거라고 본다.
시뮬레이션 문제 앞에서 매번 같은 자리에서 어긋나는 사람, 직관으로 한 번에 풀고 싶어지는 손버릇이 잡히지 않는 사람에게 이 골격이 짧은 지름길이 됐으면 한다. 트레일 2의 시뮬레이션 Ⅰ, Ⅱ를 전부 풀면서 손에 잡힌 한 줄짜리 골격이라, 같은 유형을 마주칠 때마다 처음부터 다시 설계하는 부담을 한 단계 줄여준다.
본 글에서 다룬 네 문제는 모두 트레일 2에서 직접 풀어보고 CHOOSLA/AlgorithmCodetree/trail2/에 올려둔 풀이다. 시간 단위 시뮬레이션의 골격을 직접 손으로 확인해보고 싶다면 아래에서 시작할 수 있다.
