2026-02-03 | 8 min read | 170 | 시뮬레이션 알고리즘 예시

8-3. 코딩 테스트: 시뮬레이션 문제 풀이

1. 시뮬레이션 문제 소개

시뮬레이션(Simulation) 문제는 주어진 규칙에 따라 일련의 과정을 직접 "따라 해보는" 유형의 문제입니다. 현실 세계의 물리적인 움직임, 게임의 턴 진행, 또는 복잡한 시스템의 작동 방식을 코드로 모방하는 것이 핵심입니다. 이러한 문제는 문제 해결을 위한 알고리즘을 고안하는 것보다, 주어진 조건을 정확하게 이해하고, 그것을 코드로 얼마나 꼼꼼하게 구현하는지가 중요합니다.

시뮬레이션 문제는 다양한 형태로 출제될 수 있으며, 문제의 난이도 역시 천차만별입니다. 어떤 문제들은 단순한 조건의 나열로 쉽게 해결될 수 있지만, 복잡한 조건, 예외 처리, 그리고 최적화까지 고려해야 하는 문제들도 있습니다. 따라서, 시뮬레이션 문제를 효과적으로 해결하기 위해서는 문제 분석 능력, 꼼꼼함, 그리고 코드 구현 능력이 모두 필요합니다.

2. 시뮬레이션 문제 해결 단계

시뮬레이션 문제를 해결하는 데는 다음과 같은 단계별 접근 방식이 유용합니다.

1) 문제 분석 및 이해

가장 먼저 해야 할 일은 문제를 정확하게 이해하는 것입니다. 문제에서 요구하는 사항, 주어진 조건, 제약 사항 등을 꼼꼼하게 파악해야 합니다.

입력: 입력으로 주어지는 데이터의 형태와 범위, 그리고 어떤 정보가 주어지는지 정확하게 이해해야 합니다.
출력: 최종적으로 출력해야 하는 결과가 무엇인지, 어떤 형식으로 출력해야 하는지 명확하게 파악해야 합니다.
조건: 문제에 주어진 모든 조건(예: 제한 시간, 메모리 사용량, 특별한 규칙 등)을 꼼꼼하게 확인해야 합니다.
예시 분석: 문제에 제시된 예시 입력을 가지고, 예상되는 출력 결과를 손으로 직접 계산해 보면서 문제의 로직을 파악하는 것이 좋습니다.

2) 모델링 및 설계

문제를 이해했다면, 문제를 해결하기 위한 모델을 설계해야 합니다.

자료 구조 선택: 문제에서 주어진 데이터를 효율적으로 저장하고 관리하기 위한 자료 구조(배열, 리스트, 큐, 스택, 딕셔너리 등)를 선택해야 합니다. 선택한 자료 구조가 문제의 복잡성을 얼마나 줄여줄 수 있는지 고려해야 합니다.
알고리즘 설계: 문제의 핵심 로직을 구현하기 위한 알고리즘을 설계해야 합니다. 문제의 조건에 따라 다양한 알고리즘(반복문, 조건문, 재귀 함수 등)을 조합하여 사용할 수 있습니다.
흐름도 또는 의사 코드 작성: 복잡한 문제의 경우, 흐름도나 의사 코드를 작성하여 문제 해결 과정을 시각적으로 표현하거나, 코드 구현 전에 전체적인 구조를 설계하는 것이 도움이 됩니다.

3) 코드 구현

설계가 완료되면, 선택한 프로그래밍 언어를 사용하여 코드를 구현합니다.

모듈화: 코드를 기능별로 분리하여 모듈화하면, 코드의 가독성을 높이고 유지 보수를 용이하게 할 수 있습니다. 함수나 클래스를 적절하게 활용하는 것이 좋습니다.
테스트 케이스 고려: 문제에 주어진 예시 외에도, 다양한 테스트 케이스(경계값, 특수한 경우, 에러 케이스 등)를 고려하여 코드를 작성해야 합니다.
디버깅: 코드를 구현하면서 발생할 수 있는 오류를 디버깅 도구를 사용하여 찾아내고 수정해야 합니다.

4) 테스트 및 디버깅

코드를 작성한 후, 테스트 케이스를 사용하여 코드의 정확성을 검증합니다.

예시 테스트: 문제에서 제공하는 예시 입력과 예상 출력값을 비교하여, 코드의 기본적인 동작을 확인합니다.
추가 테스트 케이스: 예시 외에, 다양한 테스트 케이스를 직접 만들어 테스트합니다.
디버깅: 예상과 다른 결과가 나오면, 디버깅 도구를 사용하여 코드의 실행 과정을 추적하고 오류를 수정합니다.
코드 개선: 모든 테스트 케이스를 통과했다면, 코드의 효율성을 개선할 수 있는 여지가 있는지 확인하고, 필요하다면 코드를 리팩토링합니다.

5) 복잡도 분석

코드의 시간 복잡도와 공간 복잡도를 분석하여, 효율적인 코드를 작성했는지 확인합니다. 특히, 코딩 테스트에서는 제한 시간 내에 문제를 해결해야 하므로, 시간 복잡도 분석은 매우 중요합니다.

3. 복잡도 고려 사항

시뮬레이션 문제에서 효율적인 코드를 작성하기 위해서는 복잡도를 고려해야 합니다.

1) 시간 복잡도

시간 복잡도는 알고리즘의 실행 시간을 나타내는 지표입니다. 문제에서 주어진 입력 크기(N)에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타냅니다. 시간 복잡도가 높을수록 실행 시간이 오래 걸리며, 코딩 테스트에서는 제한 시간 내에 실행을 완료하지 못할 수 있습니다.

O(1) (상수 시간): 입력 크기에 관계없이 실행 시간이 일정한 알고리즘.
O(log N) (로그 시간): 입력 크기가 증가할수록 실행 시간이 로그 함수적으로 증가하는 알고리즘 (예: 이진 탐색).
O(N) (선형 시간): 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘 (예: 배열을 한 번 순회하는 경우).
O(N log N): 입력 크기에 N log N에 비례하여 실행 시간이 증가하는 알고리즘 (예: 정렬 알고리즘).
O(N^2) (제곱 시간): 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘 (예: 이중 반복문).
O(N^3) (세제곱 시간) 이상: 입력 크기의 세제곱 이상에 비례하여 실행 시간이 증가하는 알고리즘. 일반적으로 입력 크기가 작은 경우에만 사용 가능합니다.
O(2^N) (지수 시간), O(N!) (팩토리얼 시간): 입력 크기가 증가함에 따라 실행 시간이 매우 빠르게 증가하는 알고리즘. 문제 해결이 어려운 경우가 많습니다.

문제의 조건을 확인하고, 시간 제한 내에 모든 테스트 케이스를 통과할 수 있도록 알고리즘을 설계하고 구현해야 합니다. 만약 시간 초과가 발생한다면, 알고리즘의 시간 복잡도를 줄일 수 있는 방법을 찾아야 합니다. 예를 들어, 불필요한 연산을 줄이거나, 자료 구조를 변경하거나, 알고리즘 자체를 개선해야 할 수도 있습니다.

2) 공간 복잡도

공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 나타내는 지표입니다.

시간 복잡도와 마찬가지로, 공간 복잡도도 입력 크기에 따라 증가합니다.
코딩 테스트에서는 메모리 사용량 제한도 고려해야 합니다.
불필요한 데이터 구조를 사용하지 않도록 주의하고, 필요한 경우 메모리 사용량을 최소화할 수 있는 자료 구조나 알고리즘을 선택해야 합니다.

4. 시뮬레이션 문제 예시 및 풀이

다음은 시뮬레이션 문제의 예시와 풀이를 제시합니다.

1) 문제: "상어 초등학교"

문제 설명:

크기가 N x N인 상어 초등학교에 학생들이 등교했습니다. 각 학생은 좋아하는 학생 4명을 가지고 있으며, 자리에 앉을 때 다음 규칙을 따릅니다.

가장 많은 친구가 인접한 칸에 앉는다. (만약 여러 자리가 있다면)

비어있는 칸이 가장 많은 칸에 앉는다. (만약 여러 자리가 있다면)

행 번호가 가장 작은 칸에 앉는다. (만약 여러 자리가 있다면)

열 번호가 가장 작은 칸에 앉는다. (만약 여러 자리가 있다면)

모든 학생이 자리에 앉은 후, 각 학생의 만족도를 계산합니다. 만족도는 인접한 칸에 앉은 친구의 수에 따라 결정됩니다.

1명: 1점, 2명: 10점, 3명: 100점, 4명: 1000점

입력:

첫 번째 줄에는 N (2 ≤ N ≤ 20)이 주어집니다.

두 번째 줄부터 N^2 줄에 걸쳐 각 학생의 번호, 좋아하는 학생 4명의 번호가 주어집니다.

출력:

모든 학생의 만족도 합을 출력합니다.

예시 입력:

예시 출력:

2) 문제 해결

1) 문제 분석

자리 배치 규칙을 정확하게 이해해야 합니다.
각 학생의 만족도를 계산하는 로직을 구현해야 합니다.
입력으로 주어지는 학생의 번호와 좋아하는 학생의 정보를 저장해야 합니다.

2) 모델링 및 설계

자료 구조:
- N x N 크기의 2차원 배열 board를 사용하여 학생들의 자리 배치를 저장합니다.
- 각 학생의 번호와 좋아하는 학생의 정보를 저장하기 위해 students라는 딕셔너리를 사용합니다.
- 알고리즘: 1. 각 학생의 자리를 배치합니다.
  - 자리를 배치할 때, 문제에 주어진 4가지 규칙을 순서대로 적용합니다. 2. 모든 학생의 자리가 배치되면, 각 학생의 만족도를 계산합니다.
  - 각 학생의 인접한 칸에 있는 친구의 수를 세어 만족도를 계산합니다. 3. 모든 학생의 만족도를 더하여 최종 결과를 출력합니다.
- 의사 코드:

function solve():
    read N
    read students_info (student_id, [favorite_students])
    initialize board (N x N, filled with 0)

    for each student_id, favorite_students in students_info:
        find best_position = find_best_position(student_id, favorite_students)
        place student_id in board at best_position

    calculate satisfaction_sum
    print satisfaction_sum

function find_best_position(student_id, favorite_students):
    for each cell in board:
        calculate score_1 (neighbor_friends_count)
        calculate score_2 (empty_neighbor_count)
    select cell based on priority(score_1, score_2, row, col)
    return best_position

function calculate_satisfaction(student_id):
    count = number of favorite_students in neighbor cells
    return satisfaction_score based on count

3) 코드 구현

다음은 Python으로 구현된 코드의 예시입니다.

def solve():
    N = int(input())
    students = {}
    for _ in range(N * N):
        line = list(map(int, input().split()))
        student_id = line[0]
        favorite_students = line[1:]
        students[student_id] = favorite_students

    board = [[0] * N for _ in range(N)]
    positions = {}  # student_id : (row, col)

    def count_neighbors(row, col, student_id):
        count = 0
        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        for i in range(4):
            nr, nc = row + dr[i], col + dc[i]
            if 0 <= nr < N and 0 <= nc < N and board[nr][nc] in students.keys():
                count += (board[nr][nc] in students[student_id])
        return count

    def count_empty_neighbors(row, col):
        count = 0
        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        for i in range(4):
            nr, nc = row + dr[i], col + dc[i]
            if 0 <= nr < N and 0 <= nc < N and board[nr][nc] == 0:
                count += 1
        return count

    def find_best_position(student_id):
        candidates = []
        for r in range(N):
            for c in range(N):
                if board[r][c] == 0:
                    score1 = count_neighbors(r, c, student_id)
                    score2 = count_empty_neighbors(r, c)
                    candidates.append((score1, score2, r, c))

        if not candidates:
            return None

        candidates.sort(key=lambda x: (-x[0], -x[1], x[2], x[3])) # 규칙 1~4 반영
        return candidates[0][2], candidates[0][3]

    for student_id, _ in students.items():
        best_position = find_best_position(student_id)
        if best_position:
            row, col = best_position
            board[row][col] = student_id
            positions[student_id] = (row, col)

    satisfaction_sum = 0
    for student_id, favorite_students in students.items():
        row, col = positions[student_id]
        count = count_neighbors(row, col, student_id)
        if count == 1:
            satisfaction_sum += 1
        elif count == 2:
            satisfaction_sum += 10
        elif count == 3:
            satisfaction_sum += 100
        elif count == 4:
            satisfaction_sum += 1000

    print(satisfaction_sum)

solve()

4) 테스트 및 디버깅

문제에 주어진 예시 입력을 코드로 실행하여 출력을 확인합니다.
다양한 테스트 케이스를 만들어 코드가 예상대로 동작하는지 확인합니다. 예를 들어, 학생들이 좋아하는 학생이 없는 경우, 모든 칸이 비어있는 경우, 좋아하는 학생이 여러 명 인접한 경우 등 다양한 경우를 테스트합니다.
디버깅 도구를 사용하여 코드의 실행 과정을 추적하고 오류를 수정합니다.

5) 복잡도 분석

시간 복잡도: 각 학생의 자리를 배치하는 과정에서 N^2 크기의 board를 순회하고, 각 칸에 대해 인접한 칸을 확인하므로, 대략 O(N^4)의 시간 복잡도를 가집니다. (N: board의 크기, N^2: 학생 수, 각 학생마다 N^2칸을 순회, 각 칸마다 4방향 확인)
공간 복잡도: board (N x N)와 학생 정보를 저장하는 자료 구조를 사용하므로 O(N^2)의 공간 복잡도를 가집니다.

5. 시뮬레이션 문제 해결 팁

꼼꼼하게 문제 분석: 문제의 조건을 정확하게 파악하고, 예외 상황을 고려하여 코드를 설계해야 합니다.
자료 구조 선택: 문제에 적합한 자료 구조를 선택하여 효율적으로 데이터를 관리합니다.
모듈화: 코드를 기능별로 분리하여 모듈화하면 코드의 가독성을 높이고, 유지 보수를 용이하게 할 수 있습니다.
테스트 케이스: 다양한 테스트 케이스를 사용하여 코드의 정확성을 검증합니다. 경계값, 특수한 경우, 에러 케이스 등을 포함하는 것이 좋습니다.
디버깅 도구: 디버깅 도구를 사용하여 코드의 실행 과정을 추적하고 오류를 찾아 수정합니다.
시간 복잡도: 시간 복잡도를 고려하여 효율적인 알고리즘을 설계하고, 불필요한 연산을 줄여 시간 초과를 방지합니다.