2. 구현 / 시뮬레이션

특별한 알고리즘 없이, 문제에 적힌 규칙을 그대로 코드로 옮기는 유형입니다. 문법에서 알고리즘으로 넘어가는 진짜 다리예요. 화려한 아이디어보다 "실수 없이 꼼꼼하게 옮기는 힘"을 기릅니다. 소수 챕터가 "관찰로 똑똑하게 줄이기"였다면, 여기는 정반대로 "시키는 대로 정확히 다 하기" 가 핵심입니다.

이 한 챕터에서 배우는 것:

상하좌우 이동을 dx/dy 배열 하나로 깔끔하게 다루는 법
2차원 리스트(격자) 를 만들고 순회하는 법, 그리고 흔한 함정
시각·날짜처럼 시간이 흐르는 시뮬레이션을 코드로 옮기는 법
방향을 바꿔가며 격자를 채우는 나선(달팽이) 채우기

시뮬레이션 문제는 뭐가 다를까?

지금까지는 "정답을 어떻게 빨리 구하지?"를 고민했다면, 시뮬레이션은 "문제가 시키는 행동을 순서대로 재현" 하면 끝입니다. 대신 조건이 많고 예외 처리가 잦아서, 딴 데서 실수가 나요. "경계를 벗어났나?", "인덱스가 반대 아닌가?" 같은 걸 침착하게 챙기는 게 실력입니다.

1단계: 상하좌우 이동 (dx/dy 배열)

격자 위의 캐릭터가 상하좌우로 움직이는 문제는 정말 자주 나옵니다. if 문으로 네 방향을 하나하나 쓰면 코드가 길어지고 실수도 늘어요. 대신 방향을 배열로 정리합니다.

격자에서는 보통 (행 r, 열 c)로 위치를 나타냅니다. 위로 가면 행이 줄고(-1), 아래로 가면 행이 늘죠(+1). 이걸 두 배열에 담습니다.

# 상, 하, 좌, 우 순서로 짝을 맞춰 둔다
dr = [-1, 1, 0, 0]   # 행(row) 변화량
dc = [0, 0, -1, 1]   # 열(col) 변화량

r, c = 2, 2          # 현재 위치
for d in range(4):   # 네 방향을 한 번에 훑기
    nr = r + dr[d]
    nc = c + dc[d]
    print(nr, nc)
# 1 2
# 3 2
# 2 1
# 2 3

dr[d]와 dc[d]는 같은 인덱스끼리 한 쌍이라는 게 핵심입니다. d=0이면 (-1, 0) = 위, d=1이면 (1, 0) = 아래. 방향이 8개(대각선 포함)여도 배열만 늘리면 코드는 그대로예요.

💡 네 방향을 if 위: ... elif 아래: ...로 쓰지 마세요. dx/dy 배열 + for 하나면 코드가 4분의 1로 줄고, 방향 추가도 배열만 고치면 됩니다. 구현 문제의 국룰 패턴입니다.

2단계: 격자(2차원 리스트) 다루기

격자는 리스트 안에 리스트로 만듭니다. 그런데 초보자가 100% 걸려 넘어지는 함정이 하나 있어요.

# ❌ 함정: 이렇게 만들면 안 됩니다
grid = [[0] * 3] * 3
grid[0][0] = 5
print(grid)
# [[5, 0, 0], [5, 0, 0], [5, 0, 0]]   ← 한 칸만 바꿨는데 세 줄이 다 바뀜!

[...] * 3은 똑같은 리스트 하나를 3번 가리키게 복제합니다. 그래서 한 줄만 고쳐도 전부 따라 바뀌어요. 올바른 방법은 각 행을 따로 만드는 것입니다.

# ✅ 올바름: 리스트 컴프리헨션으로 행마다 새 리스트
n, m = 3, 3
grid = [[0] * m for _ in range(n)]
grid[0][0] = 5
print(grid)
# [[5, 0, 0], [0, 0, 0], [0, 0, 0]]   ← 딱 한 칸만 바뀜

순회는 행 인덱스 → 열 인덱스 이중 반복문으로 합니다. 경계를 벗어나는지 확인하는 함수도 하나 만들어두면 편해요.

grid = [
    [1, 2, 3],
    [4, 5, 6],
]
R, C = len(grid), len(grid[0])   # 행 수, 열 수

def in_range(r, c):
    return 0 <= r < R and 0 <= c < C   # 격자 안에 있으면 True

total = 0
for r in range(R):
    for c in range(C):
        total += grid[r][c]
print(total)                # 21
print(in_range(1, 2))       # True
print(in_range(2, 0))       # False  (행이 범위를 벗어남)

💡 이동(dr/dc)한 다음에는 반드시 in_range로 격자 밖인지 먼저 확인하세요. 확인 없이 grid[nr][nc]에 접근하면 인덱스 에러가 나거나, 파이썬에서는 음수 인덱스가 반대편을 가리켜 조용히 틀린 답이 나옵니다.

이제 앞의 dr/dc와 격자를 합치면, 한 칸에서 갈 수 있는 이웃만 골라낼 수 있습니다.

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
R, C = len(grid), len(grid[0])
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def in_range(r, c):
    return 0 <= r < R and 0 <= c < C

r, c = 0, 0                  # 왼쪽 위 모서리
neighbors = []
for d in range(4):
    nr, nc = r + dr[d], c + dc[d]
    if in_range(nr, nc):    # 격자 안에 있는 이웃만
        neighbors.append(grid[nr][nc])
print(neighbors)            # [4, 2]  (아래 4, 오른쪽 2 — 위/왼쪽은 격자 밖)

이 "이웃 훑기" 패턴은 나중에 BFS/DFS(그래프 탐색) 의 기본 뼈대가 됩니다. 지금 손에 익혀두면 뒤에서 크게 덕을 봐요.

3단계: 시각 시뮬레이션

시간이 흐르는 문제도 결국 "규칙대로 하나씩 세기"입니다. 예를 들어 하루(0시 0분 0초 ~ 23시 59분 59초) 중 숫자 3이 하나라도 포함된 시각의 개수를 세는 고전 문제를 봅시다.

똑똑한 수학 대신, 모든 시각을 실제로 다 만들어보고 세면 됩니다. 하루는 24 × 60 × 60 = 86,400초뿐이라, 컴퓨터에겐 순식간이에요.

def count_three():
    count = 0
    for h in range(24):
        for m in range(60):
            for s in range(60):
                # 시:분:초를 한 문자열로 이어붙여 '3'이 있는지 확인
                if '3' in f'{h}{m}{s}':
                    count += 1
    return count

print(count_three())   # 43875

반복 횟수는 24 × 60 × 60 ≈ 8.6만 번. 1초에 1억 번 기준으로 보면 눈 깜짝할 사이입니다. 이렇게 경우의 수가 작으면 그냥 다 돌려버리는 게(완전탐색) 가장 안전하고 빠른 정답입니다.

💡 시각·날짜 문제에서 "3이 든 시각", "특정 요일" 같은 조건은 문자열로 바꿔서 in으로 확인하면 조건 분기가 확 줄어듭니다. 자릿수를 일일이 % 10으로 뜯지 마세요.

분이 60이 되면 시가 넘어가는 자리 올림(carry) 도 자주 나옵니다. "현재 시각에서 K분 뒤"를 구하려면 전체를 분 단위로 바꿨다가 되돌리는 게 깔끔해요.

def after_minutes(h, m, k):
    total = h * 60 + m + k        # 전부 '분'으로 환산해 더하기
    total %= 24 * 60              # 하루(1440분)를 넘으면 다음 날 0시로 돌아옴
    return total // 60, total % 60   # 다시 (시, 분)으로 분해

print(after_minutes(10, 30, 45))   # (11, 15)
print(after_minutes(23, 50, 20))   # (0, 10)   ← 자정을 넘어 다음 날로

% (24*60)로 하루를 넘으면 자동으로 0시부터 다시 세도록 한 게 포인트입니다. 이 "큰 단위로 합쳤다가 나눠서 되돌리기" 는 날짜 계산에도 그대로 통합니다.

4단계: 나선(달팽이) 채우기

방향을 바꿔가며 격자를 채우는 문제입니다. 안쪽으로 빙글빙글 도는 나선 모양으로 1, 2, 3, ...을 채워봅시다.

핵심 아이디어: 오른쪽으로 쭉 가다가 벽이나 이미 채운 칸을 만나면 시계 방향으로 방향을 튼다. 방향 배열을 우 → 하 → 좌 → 상 순서로 두면, 방향 전환은 그냥 인덱스를 +1 하는 것과 같아요.

def spiral(n):
    grid = [[0] * n for _ in range(n)]   # n×n을 0으로 초기화
    dr = [0, 1, 0, -1]                   # 우, 하, 좌, 상
    dc = [1, 0, -1, 0]

    r = c = 0
    d = 0                                # 처음엔 오른쪽(인덱스 0)
    for num in range(1, n * n + 1):      # 1부터 n*n까지 채우기
        grid[r][c] = num
        nr, nc = r + dr[d], c + dc[d]
        # 다음 칸이 격자 밖이거나 이미 채워졌으면 방향을 시계방향으로 튼다
        if not (0 <= nr < n and 0 <= nc < n) or grid[nr][nc] != 0:
            d = (d + 1) % 4              # 우→하→좌→상→우 ... 순환
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc                    # 실제로 한 칸 이동
    return grid

for row in spiral(4):
    print(row)
# [1, 2, 3, 4]
# [12, 13, 14, 5]
# [11, 16, 15, 6]
# [10, 9, 8, 7]

방향 전환의 정체는 d = (d + 1) % 4 한 줄입니다. % 4 덕분에 상(3) 다음이 다시 우(0)로 자연스럽게 돌아와요. 앞에서 배운 dr/dc 배열과 in_range 검사가 그대로 쓰인 게 보이나요? 구현 문제는 이렇게 작은 패턴들의 조합입니다.

💡 "이미 채웠는지"를 grid[nr][nc] != 0으로 확인하는 게 트릭입니다. 방문 여부를 별도 배열로 두지 않고, 채운 값(0이 아님) 자체를 방문 표시로 재활용했어요. 소수 챕터에서 리스트를 "칠판"으로 쓴 발상과 똑같습니다.

정리

패턴	핵심 도구	자주 나오는 실수
상하좌우 이동	`dr/dc` 배열 + `for d in range(4)`	행/열 변화량을 반대로 씀
격자 생성	`[[0]*m for _ in range(n)]`	`[[0]m]n`으로 만들어 행이 공유됨
격자 순회	이중 `for` + `in_range` 검사	경계 확인 없이 접근해 인덱스 에러
시각/날짜	큰 단위로 합쳤다 `%`, `//`로 복원	자리 올림(carry) 누락
나선 채우기	`d = (d+1) % 4`로 방향 전환	방향 순서와 전환 조건 꼬임

💡 구현 문제엔 지름길이 없습니다. 대신 ① 규칙을 작은 단계로 쪼개고 → ② dr/dc·in_range 같은 검증된 패턴을 조립하고 → ③ 예시 입력으로 손으로 한 번 따라가 본다. 이 습관이 실수를 막는 유일한 방법이에요.

직접 풀어보기

dr/dc를 대각선 4방향까지 포함한 8방향 배열로 확장해, 격자 한가운데 칸의 이웃 8칸을 모두 출력해보세요. (힌트: dr = [-1,-1,-1,0,0,1,1,1], dc = [-1,0,1,-1,1,-1,0,1])
하루 중 숫자 3이 하나도 없는 시각의 개수를 세보세요. (정답: 86400 - 43875 = 42525)
spiral(n)을 바깥에서 안으로가 아니라, 채우는 값을 거꾸로 넣어 n*n부터 1까지 나선으로 채워보세요. (힌트: range(n*n, 0, -1)을 쓰거나, 채운 뒤 각 칸을 n*n+1 - 값으로 바꿔보세요.)