Implementation
Implementation & Simulation
구현(Implementation)은 문제에서 요구하는 동작을 그대로 코드로 옮기는 유형이다.
한 줄로 요약하면 다음과 같다.
알고리즘보다 정확한 시뮬레이션이 핵심인 문제
특별한 자료구조나 알고리즘 없이도 풀 수 있지만, 조건이 많고 실수가 나기 쉬워서 체계적인 접근이 중요하다.
1. 언제 나오는가
문제에서 아래 표현이 보이면 구현/시뮬레이션을 의심하면 된다.
- 격자 위에서 이동
- 방향 회전
- 주사위, 톱니바퀴, 뱀
- 조건이 많고 복잡함
- “규칙대로 반복”
- 시간 순서대로 처리
대표 출제처:
- 삼성 SW 역량 테스트
- 카카오 1차 구현 문제
- 프로그래머스 Lv2~3 구현
2. 구현 문제의 핵심 난이도
구현 문제가 어려운 이유는 알고리즘이 아니라 다음 세 가지다.
1. 조건이 많다
2. 예외가 숨어 있다
3. 코드가 길어지면 실수가 쌓인다
따라서 구현 문제에서는:
- 문제를 꼼꼼하게 읽고
- 동작을 단계별로 분리하고
- 각 단계를 함수로 나누는 것
이 가장 중요하다.
3. 격자 이동: 방향 배열
격자 문제에서 가장 먼저 세팅하는 것이 방향 배열이다.
4방향 (상하좌우)
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
8방향 (대각선 포함)
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
이동은 항상 다음 형태로 처리한다.
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
// 범위 안이면 처리
}
4. 방향 회전
시뮬레이션에서 방향을 다루는 문제는 매우 자주 나온다.
방향 인덱스 관례
보통 다음처럼 정한다.
0: 상 (북)
1: 우 (동)
2: 하 (남)
3: 좌 (서)
flowchart LR
subgraph "방향 인덱스"
D0["0: 상 ↑"]
D1["1: 우 →"]
D2["2: 하 ↓"]
D3["3: 좌 ←"]
end
D0 -->|"시계 90°"| D1
D1 -->|"시계 90°"| D2
D2 -->|"시계 90°"| D3
D3 -->|"시계 90°"| D0
시계 방향 90도 회전
dir = (dir + 1) % 4;
반시계 방향 90도 회전
dir = (dir + 3) % 4;
180도 회전
dir = (dir + 2) % 4;
이 패턴은 외워야 한다.
특히 반시계를 (dir - 1 + 4) % 4로 써도 맞고, (dir + 3) % 4는 읽기가 더 단순하다.
5. 격자 회전
격자 자체를 90도 회전하는 문제도 자주 나온다.
시계 방향 90도
int[][] rotate90(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[j][n - 1 - i] = grid[i][j];
}
}
return result;
}
핵심 공식:
시계 90도: (i, j) -> (j, N-1-i)
반시계 90도: (i, j) -> (M-1-j, i)
180도: (i, j) -> (N-1-i, M-1-j)
6. 배열 돌리기 (테두리 회전)
격자 회전이 배열 전체를 90도 돌리는 것이라면, 배열 돌리기는 테두리(링)를 따라 원소를 한 칸씩 밀어내는 문제다.
백준 16926번(배열 돌리기 1), 16927번(배열 돌리기 2) 등이 대표적이다.
핵심 아이디어
N×M 배열에서 테두리(링)의 개수는 min(N, M) / 2개다.
┌───────────┐
│ 링 0 │
│ ┌───────┐ │
│ │ 링 1 │ │
│ │ ┌───┐ │ │
│ │ │ 2 │ │ │
│ │ └───┘ │ │
│ └───────┘ │
└───────────┘
flowchart TD
A["전체 배열"] --> B["링 개수 = min(N, M) / 2"]
B --> C["각 링마다"]
C --> D["링의 원소를 1차원으로 추출"]
D --> E["R칸만큼 회전"]
E --> F["다시 링 위치에 채우기"]
k번째 링의 범위
시작점: (k, k)
끝점: (N-1-k, M-1-k)
링의 원소 추출 순서
시계 방향으로 테두리를 따라 순서대로 꺼내면 된다.
1. 위쪽 변: (k, k) → (k, M-1-k) 왼쪽에서 오른쪽
2. 오른쪽 변: (k+1, M-1-k) → (N-1-k, M-1-k) 위에서 아래
3. 아래쪽 변: (N-1-k, M-2-k) → (N-1-k, k) 오른쪽에서 왼쪽
4. 왼쪽 변: (N-2-k, k) → (k+1, k) 아래에서 위
구현 코드
void rotateRing(int[][] arr, int N, int M, int R) {
int rings = Math.min(N, M) / 2;
for (int k = 0; k < rings; k++) {
// 1. 링의 원소를 리스트로 추출
List<Integer> list = new ArrayList<>();
// 위쪽 변
for (int j = k; j < M - k; j++)
list.add(arr[k][j]);
// 오른쪽 변
for (int i = k + 1; i < N - k; i++)
list.add(arr[i][M - 1 - k]);
// 아래쪽 변
for (int j = M - 2 - k; j >= k; j--)
list.add(arr[N - 1 - k][j]);
// 왼쪽 변
for (int i = N - 2 - k; i > k; i--)
list.add(arr[i][k]);
// 2. R칸 회전 (반시계: 앞에서 R개를 뒤로 보내기)
int len = list.size();
int r = R % len; // 링 길이로 나머지
List<Integer> rotated = new ArrayList<>();
for (int i = r; i < len; i++) rotated.add(list.get(i));
for (int i = 0; i < r; i++) rotated.add(list.get(i));
// 3. 다시 링 위치에 채우기
int idx = 0;
for (int j = k; j < M - k; j++)
arr[k][j] = rotated.get(idx++);
for (int i = k + 1; i < N - k; i++)
arr[i][M - 1 - k] = rotated.get(idx++);
for (int j = M - 2 - k; j >= k; j--)
arr[N - 1 - k][j] = rotated.get(idx++);
for (int i = N - 2 - k; i > k; i--)
arr[i][k] = rotated.get(idx++);
}
}
배열 돌리기 주의사항
1. R이 링 길이보다 클 수 있다 → R %= len 필수
2. 추출 순서와 채우기 순서가 반드시 동일해야 한다
3. 반시계 회전이면 앞에서 R개를 뒤로, 시계 회전이면 뒤에서 R개를 앞으로
4. 각 링은 독립적이므로 링마다 개별 처리한다
배열 돌리기 2 (큰 R 최적화)
배열 돌리기 2(백준 16927)에서는 R이 최대 10⁹로 매우 크다.
하지만 각 링의 길이만큼 회전하면 원래대로 돌아오므로,
R % len으로 실제 회전 횟수를 줄이면 시간 내에 풀 수 있다.
링 길이 = 2 * (가로 + 세로) - 4
→ 한 바퀴 돌면 원상 복구
→ R % 링길이 만큼만 회전
7. 시뮬레이션 문제 접근법
시뮬레이션은 보통 다음 구조를 따른다.
flowchart TD
A["입력 파싱 & 초기 상태 세팅"] --> B["매 턴/시간 반복"]
B --> C["조건에 따라 상태 변경"]
C --> D{"종료 조건?"}
D -->|No| B
D -->|Yes| E["결과 출력"]
실전 팁:
- 상태를 변수로 명확히 정의한다
- 매 턴의 동작을 함수 하나로 분리한다
- 디버깅할 때 매 턴 상태를 출력해 보면 빠르다
8. 뱀 게임 같은 시뮬레이션 예시
전형적인 시뮬레이션 구조를 요약하면 다음과 같다.
1. 초기 위치, 방향 설정
2. 매 턴마다:
a. 현재 방향으로 한 칸 이동
b. 벽이나 자기 몸이면 종료
c. 사과가 있으면 먹고 꼬리 유지
d. 사과가 없으면 꼬리 줄이기
e. 방향 전환 명령이 있으면 적용
3. 반복
이런 문제는 Deque로 뱀의 몸을 관리하면 편하다.
Deque<int[]> snake = new ArrayDeque<>();
snake.offerFirst(new int[]{headX, headY});
// 사과가 없으면 꼬리 제거
if (!apple) {
int[] tail = snake.pollLast();
grid[tail[0]][tail[1]] = 0;
}
9. 좌표계 주의
격자 문제에서 가장 많이 실수하는 부분이 좌표계다.
배열 인덱스 vs 수학 좌표
배열: (행, 열) = (row, col) → 아래로 갈수록 row 증가
수학: (x, y) → 위로 갈수록 y 증가
문제가 “위쪽 이동”이라고 하면:
- 배열 기준이면
row - 1 - 수학 좌표 기준이면
y + 1
문제를 먼저 읽고 좌표 체계를 확인한 뒤,
dx, dy 방향 배열을 그에 맞게 설정해야 한다.
10. 2차원 배열 복사
시뮬레이션에서 상태를 복사해야 하는 경우가 자주 있다.
주의: 얕은 복사 함정
// 틀림: 1차원 배열 참조만 복사됨
int[][] copy = grid.clone();
올바른 깊은 복사
int[][] copy = new int[N][M];
for (int i = 0; i < N; i++) {
copy[i] = grid[i].clone();
}
혹은:
int[][] copy = new int[N][M];
for (int i = 0; i < N; i++) {
System.arraycopy(grid[i], 0, copy[i], 0, M);
}
11. 구현 문제에서 함수 분리의 중요성
구현 문제에서 코드가 100줄이 넘어가면 실수 확률이 급격히 올라간다.
다음처럼 동작 단위로 함수를 분리하면 디버깅이 훨씬 쉬워진다.
void solve() {
init(); // 초기 상태 설정
for (int t = 0; t < T; t++) {
move(); // 이동
rotate(); // 회전
spread(); // 확산
clean(); // 제거
}
print(); // 결과 출력
}
각 함수는 하나의 동작만 담당한다. 이렇게 하면:
- 버그가 어느 단계에서 나는지 빠르게 특정할 수 있고
- 단계별로 중간 상태를 출력하기 쉽다
12. 삼성 스타일 문제 패턴
삼성 코테에서 자주 나오는 시뮬레이션 패턴을 정리하면 다음과 같다.
1) 격자 + BFS/DFS
영역을 찾고, 조건에 맞는 영역을 처리
2) 격자 + 방향 이동 + 조건 분기
로봇이나 물체가 조건에 따라 격자 위를 이동
3) 격자 + 확산/복사
미세먼지, 바이러스 확산 같은 동시 갱신
동시 갱신 문제에서는 반드시:
현재 상태를 읽되 새 상태에 기록한다
를 지켜야 한다. 같은 배열에서 읽고 쓰면 틀린다.
int[][] next = deepCopy(grid);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// grid에서 읽고 next에 쓴다
}
}
grid = next;
4) 여러 동작의 순서 조합
격자 회전 + 중력 + 폭발 + 또 회전
각 동작을 함수로 분리하고 순서대로 호출하면 된다.
13. 문자열 파싱 구현
카카오 스타일 문제에서 자주 나오는 유형이다.
특정 포맷의 문자열을 파싱해서 조건대로 처리
예를 들어 시간 문자열 "12:30:45"를 초 단위로 바꾸기:
String[] parts = time.split(":");
int h = Integer.parseInt(parts[0]);
int m = Integer.parseInt(parts[1]);
int s = Integer.parseInt(parts[2]);
int totalSec = h * 3600 + m * 60 + s;
파싱 문제는 split, substring, charAt, StringBuilder 네 가지만 알면 거의 다 풀린다.
14. 진법 변환
구현 문제에서 간간이 나오는 유형이다.
10진수 -> N진수
String toBaseN(int num, int n) {
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
while (num > 0) {
int r = num % n;
sb.append(r < 10 ? (char)('0' + r) : (char)('A' + r - 10));
num /= n;
}
return sb.reverse().toString();
}
N진수 -> 10진수
int toDecimal(String s, int n) {
int result = 0;
for (char c : s.toCharArray()) {
int digit = Character.isDigit(c) ? c - '0' : c - 'A' + 10;
result = result * n + digit;
}
return result;
}
15. 자주 하는 실수
1) 범위 체크를 빼먹음
격자 이동에서 nx < 0 || nx >= N 확인은 필수다.
2) 방향 인덱스와 dx/dy 매핑 불일치
0이 상인데 dx[0] = 1 로 잘못 넣으면 전체가 틀린다
3) 동시 갱신을 순차 갱신으로 처리
확산이나 이동에서 읽기/쓰기를 같은 배열에 하면 안 된다.
4) 깊은 복사를 안 함
clone()만으로는 2차원 배열이 복사되지 않는다.
5) 문제 조건을 빠뜨림
구현 문제는 조건이 5~10개 넘는 경우가 많다. 체크리스트를 만들어 두면 좋다.
6) 0-indexed와 1-indexed 혼동
문제가 1-based이면 배열도 N + 1 크기로 만드는 편이 안전하다.
16. 실전 판단 기준
아래 신호가 보이면 구현/시뮬레이션이다.
- 격자 위에서 무언가 움직인다
- 시간 순서대로 처리한다
- 알고리즘보다 조건이 많다
- “규칙대로 반복 수행”
- 문제 자체가 게임처럼 생겼다
그리고 이런 문제에서는 다음이 가장 중요하다.
빠르게 풀기보다 정확하게 풀기
17. 시험장용 최소 암기 버전
구현/시뮬레이션:
문제 조건을 그대로 코드로 옮기기
격자 이동:
dx, dy 방향 배열 + 범위 체크
방향 회전:
시계: (dir + 1) % 4
반시계: (dir + 3) % 4
격자 회전:
시계 90도: (i,j) -> (j, N-1-i)
동시 갱신:
읽는 배열과 쓰는 배열을 분리
핵심 습관:
동작 단위로 함수 분리
18. 최종 요약
구현/시뮬레이션은 다음 문장으로 정리할 수 있다.
특별한 알고리즘 없이
문제의 조건과 규칙을 정확하게 코드로 옮기는 유형
핵심만 다시 압축하면:
- 방향 배열, 범위 체크, 격자 회전 공식은 외워야 한다
- 동시 갱신 문제는 읽기/쓰기 배열을 반드시 분리한다
- 코드가 길어질수록 함수 분리가 핵심이다
- 문제 조건을 체크리스트로 만들면 실수가 줄어든다
문제를 보면 먼저 이 질문을 하면 된다.
이 문제는 특정 알고리즘이 필요한가,
아니면 규칙을 정확히 옮기면 되는가?
규칙을 옮기는 것이 핵심이면 구현 문제다.
Comments
Sign in with GitHub to join the discussion.