13주차
Simulation / Implementation은 문제에서 주어진 조건과 절차를 코드로 정확하게 옮기는 유형입니다.
복잡한 알고리즘을 새로 떠올리는 것보다, 문제에서 설명한 규칙을 빠뜨리지 않고 순서대로 구현하는 것이 중요합니다.
예를 들어 캐릭터가 이동한다, 명령어를 순서대로 처리한다, 시간이 흐르면서 상태가 바뀐다, 배열 안의 값이 조건에 따라 변한다 같은 문제는 시뮬레이션 또는 구현 문제로 볼 수 있습니다.
구현 문제에서는 보통 다음과 같은 요소들이 자주 등장합니다.
| 요소 | 의미 |
|---|---|
| 상태 | 현재 위치, 현재 값, 현재 방향, 남은 시간 |
| 명령 | 이동, 회전, 추가, 삭제, 변경 |
| 조건 | 범위 확인, 장애물 확인, 예외 처리 |
| 반복 | 명령어 개수만큼 반복, 시간만큼 반복 |
| 결과 | 최종 위치, 최종 상태, 조건을 만족한 횟수 |
즉, Simulation / Implementation 문제는 문제를 읽고 상태가 어떻게 변하는지 코드로 재현하는 문제입니다.
특히 코딩 테스트에서는 “문제는 쉬워 보이지만 조건이 많아서 틀리는 문제”가 구현 유형에서 자주 나옵니다.
문제 설명을 대충 읽고 바로 코드부터 작성하면, 범위 조건이나 예외 상황을 놓쳐서 오답이 발생하기 쉽습니다.
따라서 구현 문제를 풀 때는 먼저 다음을 정리하는 것이 좋습니다.
- 무엇을 상태로 관리할 것인지 정합니다.
- 입력으로 들어오는 명령이나 조건을 어떻게 처리할지 정합니다.
- 상태가 바뀌는 순서를 확인합니다.
- 예외 조건이 발생했을 때 상태를 유지할지 변경할지 확인합니다.
- 최종적으로 어떤 값을 반환해야 하는지 확인합니다.
예를 들어 격자에서 캐릭터를 움직이는 문제라면 현재 위치를 상태로 보고, 이동 명령을 하나씩 처리하면서 범위를 벗어나거나 장애물을 만나면 이동하지 않도록 구현해야 합니다.
Simulation / Implementation 문제는 특정 알고리즘 이름이 직접 드러나지 않는 경우가 많습니다.
대신 문제 설명에 적힌 조건을 그대로 따라가며 상태 변화를 구현해야 합니다.
문제에서 주어진 규칙을 순서대로 코드로 옮기는 유형입니다.
- 주어진 명령어를 순서대로 실행한다.
- 특정 조건을 만족하면 값을 증가시킨다.
- 조건에 따라 다른 동작을 수행한다.
- 규칙에 맞게 문자열이나 배열을 변환한다.
문제 설명에 있는 조건을 하나씩 분리해서 코드로 작성해야 합니다.
이때 조건의 우선순서가 중요합니다.
예를 들어 “범위를 벗어나면 무시한다”, “장애물을 만나면 이동하지 않는다”, “정상적인 경우에만 위치를 변경한다” 같은 규칙이 있다면, 실제 위치를 바꾸기 전에 먼저 이동 가능한지 검사해야 합니다.
입력으로 여러 개의 명령이 주어지고, 각 명령을 순서대로 처리하는 유형입니다.
-
N 3,E 2처럼 방향과 거리가 주어진다. -
push,pop,delete,move같은 명령어가 주어진다. - 명령어에 따라 배열, 문자열, 좌표, 자료구조 상태가 바뀐다.
명령어를 먼저 파싱한 뒤, 명령의 종류에 따라 분기 처리합니다.
명령어가 문자열로 주어지는 경우에는 split을 사용해서 명령과 값을 분리하는 경우가 많습니다.
2차원 배열에서 상하좌우 또는 대각선 방향으로 이동하는 유형입니다.
- 지도에서 캐릭터 이동하기
- 미로에서 위치 변경하기
- 게임 맵에서 방향에 따라 움직이기
- 로봇 청소기, 주사위 굴리기, 뱀 게임 같은 시뮬레이션
현재 위치를 (row, col) 형태로 저장하고, 방향에 따라 이동량을 더합니다.
보통 방향 배열을 만들어두면 코드가 간결해집니다.
N: (-1, 0)
S: (1, 0)
W: (0, -1)
E: (0, 1)
이동하기 전에는 반드시 배열 범위를 벗어나는지 확인해야 합니다.
장애물이 있는 문제라면 이동 경로 중간에 장애물이 있는지도 확인해야 합니다.
시간이 1초씩 흐르거나, 턴이 진행되면서 상태가 변하는 유형입니다.
- 매초마다 위치가 바뀐다.
- 일정 시간이 지나면 방향이 바뀐다.
- 특정 시간에 이벤트가 발생한다.
- 턴마다 공격, 회복, 이동이 일어난다.
시간 또는 턴을 반복문의 기준으로 두고, 매 반복마다 상태를 갱신합니다.
이때 한 번의 시간 단위 안에서 어떤 동작이 먼저 일어나는지 순서를 정확히 지켜야 합니다.
배열이나 리스트의 값이 조건에 따라 계속 바뀌는 유형입니다.
- 배열 회전
- 행렬 이동
- 값 갱신
- 특정 칸 방문 처리
- 주변 칸 값 변경
원본 배열을 바로 수정해도 되는지, 아니면 임시 배열을 만들어야 하는지 먼저 판단해야 합니다.
동시에 값이 바뀌는 문제에서는 원본 배열을 바로 수정하면 다음 계산에 영향을 줄 수 있으므로 임시 배열을 사용하는 경우가 많습니다.
프로그래머스 - 공원 산책
https://school.programmers.co.kr/learn/courses/30/lessons/172928
이 문제는 공원 지도가 주어지고, 시작 위치에서 여러 이동 명령을 순서대로 처리한 뒤 최종 위치를 구하는 문제입니다.
공원은 문자열 배열로 주어집니다.
"S" : 시작 위치
"O" : 이동 가능한 길
"X" : 장애물
명령어는 다음과 같은 형태로 주어집니다.
"E 2"
"S 3"
"W 1"
각 명령어는 방향과 이동 칸 수를 의미합니다.
예를 들어 E 2는 동쪽으로 2칸 이동하라는 뜻입니다.
하지만 이동하는 도중 공원을 벗어나거나 장애물을 만나면 해당 명령은 무시해야 합니다.
즉, 한 칸이라도 이동할 수 없는 상황이 있으면 그 명령 전체를 실행하지 않습니다.
| park | routes | result |
|---|---|---|
["SOO","OOO","OOO"] |
["E 2","S 2","W 1"] |
[2,1] |
["SOO","OXX","OOO"] |
["E 2","S 2","W 1"] |
[0,1] |
이 문제는 대표적인 격자 시뮬레이션 문제입니다.
현재 위치를 상태로 관리하고, 명령어를 하나씩 처리하면서 위치를 갱신해야 합니다.
중요한 점은 바로 위치를 변경하면 안 된다는 것입니다.
먼저 이동할 경로가 모두 가능한지 검사한 뒤, 문제가 없을 때만 최종 위치를 변경해야 합니다.
예를 들어 현재 위치에서 동쪽으로 2칸 이동해야 한다면 다음을 확인해야 합니다.
- 첫 번째 칸이 배열 범위 안에 있는지 확인합니다.
- 첫 번째 칸이 장애물인지 확인합니다.
- 두 번째 칸이 배열 범위 안에 있는지 확인합니다.
- 두 번째 칸이 장애물인지 확인합니다.
- 모든 조건을 만족하면 실제 위치를 변경합니다.
중간에 하나라도 실패하면 해당 명령은 무시하고 기존 위치를 유지합니다.
- 공원 배열에서 시작 위치
S를 찾습니다. - 현재 위치를
row,col로 저장합니다. - 방향별 이동 값을 미리 정의합니다.
- routes 배열을 순회하며 명령어를 하나씩 처리합니다.
- 각 명령마다 이동 가능한지 먼저 검사합니다.
- 이동 가능하면 현재 위치를 갱신합니다.
- 모든 명령이 끝난 뒤 최종 위치를 반환합니다.
class Solution {
public int[] solution(String[] park, String[] routes) {
int row = 0;
int col = 0;
int height = park.length;
int width = park[0].length();
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (park[i].charAt(j) == 'S') {
row = i;
col = j;
}
}
}
for (String route : routes) {
String[] command = route.split(" ");
String direction = command[0];
int distance = Integer.parseInt(command[1]);
int dr = 0;
int dc = 0;
if (direction.equals("N")) {
dr = -1;
} else if (direction.equals("S")) {
dr = 1;
} else if (direction.equals("W")) {
dc = -1;
} else if (direction.equals("E")) {
dc = 1;
}
int nextRow = row;
int nextCol = col;
boolean canMove = true;
for (int i = 0; i < distance; i++) {
nextRow += dr;
nextCol += dc;
if (nextRow < 0 || nextRow >= height || nextCol < 0 || nextCol >= width) {
canMove = false;
break;
}
if (park[nextRow].charAt(nextCol) == 'X') {
canMove = false;
break;
}
}
if (canMove) {
row = nextRow;
col = nextCol;
}
}
return new int[]{row, col};
}
}def solution(park, routes):
height = len(park)
width = len(park[0])
row, col = 0, 0
for i in range(height):
for j in range(width):
if park[i][j] == "S":
row, col = i, j
directions = {
"N": (-1, 0),
"S": (1, 0),
"W": (0, -1),
"E": (0, 1)
}
for route in routes:
direction, distance = route.split()
distance = int(distance)
dr, dc = directions[direction]
next_row = row
next_col = col
can_move = True
for _ in range(distance):
next_row += dr
next_col += dc
if next_row < 0 or next_row >= height or next_col < 0 or next_col >= width:
can_move = False
break
if park[next_row][next_col] == "X":
can_move = False
break
if can_move:
row, col = next_row, next_col
return [row, col]function solution(park, routes) {
const height = park.length
const width = park[0].length
let row = 0
let col = 0
for (let i = 0; i < height; i++) {
for (let j = 0; j < width; j++) {
if (park[i][j] === "S") {
row = i
col = j
}
}
}
const directions = {
N: [-1, 0],
S: [1, 0],
W: [0, -1],
E: [0, 1]
}
for (const route of routes) {
const [direction, distanceText] = route.split(" ")
const distance = Number(distanceText)
const [dr, dc] = directions[direction]
let nextRow = row
let nextCol = col
let canMove = true
for (let i = 0; i < distance; i++) {
nextRow += dr
nextCol += dc
if (nextRow < 0 || nextRow >= height || nextCol < 0 || nextCol >= width) {
canMove = false
break
}
if (park[nextRow][nextCol] === "X") {
canMove = false
break
}
}
if (canMove) {
row = nextRow
col = nextCol
}
}
return [row, col]
}Simulation / Implementation 문제는 조건을 하나라도 빼먹으면 오답이 발생하기 쉽습니다.
특히 “이동할 수 없으면 명령 전체를 무시한다”, “중간 경로에 장애물이 있으면 이동하지 않는다”처럼 작은 조건이 정답에 큰 영향을 줍니다.
문제를 풀기 전에는 조건을 문장 단위로 나누어 체크하는 것이 좋습니다.
현재 위치를 바로 바꿔버리면 이동 중간에 장애물을 만나거나 범위를 벗어났을 때 원래 위치로 되돌리기 어려워질 수 있습니다.
따라서 먼저 임시 변수로 이동 결과를 계산하고, 이동 가능한 경우에만 실제 상태를 변경하는 방식이 안전합니다.
현재 위치를 바로 변경
이동 불가능한 상황 발견
다시 원래 위치로 복구 필요
임시 위치로 이동 가능 여부 검사
문제 없으면 실제 위치 변경
문제 있으면 기존 위치 유지
2차원 배열 문제에서는 배열에 접근하기 전에 범위를 먼저 확인해야 합니다.
범위를 벗어난 좌표로 배열에 접근하면 오류가 발생할 수 있습니다.
if (park[nextRow].charAt(nextCol) == 'X') {
canMove = false;
}위 코드는 nextRow 또는 nextCol이 범위를 벗어난 경우 오류가 발생할 수 있습니다.
if (nextRow < 0 || nextRow >= height || nextCol < 0 || nextCol >= width) {
canMove = false;
break;
}
if (park[nextRow].charAt(nextCol) == 'X') {
canMove = false;
break;
}격자 문제에서는 행과 열의 이동 방향을 헷갈리기 쉽습니다.
일반적으로 2차원 배열에서 위아래 이동은 행 번호가 바뀌고, 좌우 이동은 열 번호가 바뀝니다.
| 방향 | 행 변화 | 열 변화 |
|---|---|---|
| N | -1 | 0 |
| S | 1 | 0 |
| W | 0 | -1 |
| E | 0 | 1 |
명령어가 "E 2"처럼 문자열로 주어지는 경우 방향과 숫자를 분리해야 합니다.
숫자도 문자열로 들어오기 때문에 정수로 변환해야 정상적으로 반복문에서 사용할 수 있습니다.
거리만큼 이동해야 하는 문제에서는 한 번에 최종 좌표만 계산하면 중간에 있는 장애물을 놓칠 수 있습니다.
예를 들어 동쪽으로 3칸 이동할 때 최종 위치만 확인하면, 중간 1칸 또는 2칸 지점에 장애물이 있는 경우를 잡아내지 못합니다.
따라서 이동 경로 전체를 한 칸씩 확인해야 합니다.
결과를 반환할 때 [row, col]인지 [x, y]인지 문제에서 요구하는 형식을 확인해야 합니다.
많은 격자 문제에서는 위치를 [세로 위치, 가로 위치], 즉 [row, col] 형태로 반환합니다.
반대로 좌표 문제에서는 [x, y] 형태를 사용할 수 있으므로 문제의 반환 형식을 반드시 확인해야 합니다.
Simulation / Implementation 문제는 결국 문제에 주어진 조건과 절차를 상태 변화로 정확히 옮기는 것이 핵심입니다.
- 시뮬레이션은 시간, 명령, 조건에 따라 상태가 어떻게 변하는지 구현하는 유형입니다.
- 구현 문제는 복잡한 알고리즘보다 문제 조건을 빠짐없이 코드로 옮기는 능력이 중요합니다.
- 현재 위치, 현재 방향, 배열 상태, 남은 시간처럼 변하는 값을 상태로 관리해야 합니다.
- 명령어가 주어지는 문제에서는 입력을 순서대로 처리하며 상태를 갱신해야 합니다.
- 격자 이동 문제에서는 행과 열의 변화량을 정확히 설정해야 합니다.
- 배열 범위, 장애물, 예외 조건은 실제 상태를 변경하기 전에 먼저 확인해야 합니다.
- 이동 중간 경로를 확인해야 하는 문제에서는 최종 위치만 검사하면 안 됩니다.
- 동시에 여러 값이 바뀌는 문제에서는 원본 배열을 바로 수정해도 되는지 확인해야 합니다.
-
Simulation / Implementation문제는 조건이 많을수록 실수하기 쉬우므로 문제 설명을 조건 단위로 나누어 구현하는 것이 좋습니다.