시뮬레이션 문제란?

시뮬레이션 유형은 말 그대로 문제에 나와있는 상황과 조건을 토대로 구현하면 되는 문제이다. 따라서 특별히 알아야 하는 알고리즘은 없지만 다양한 문제를 경험해보는 것이 중요하다.
구현 및 시뮬레이션은 그냥 문제에서 시키는대로 코딩하는 유형이다.
문제에 나온 내용을 그대로 구현만 하면 되는 문제로 특별한 알고리즘 지식 없이 문제에 나온대로 구현만 잘하면 풀 수 있습니다. 또한 그 구현도 몇가지 틀 안에서 나오니 자주 나오는 몇가지 구현 형태를 익히면 비교적 쉽게 풀 수 있습니다.
일련의 명령에 따라서 개체를 차례대로 이동시키는 것
대단한 전략을 가지고있어야 하는것은 아니지만, 분석해야하는 요구사항이나 구현해야하는 코드, 예외처리가 많기에 생각보다 시간을 많이 잡아먹게 된다. 그렇기에 여러 기업에서도 자주 등장하는 유형이다. 시뮬레이션 문제들에 공통적으로 등장하는 개념들과 이런 유형을 다루기 위한 구현 스킬들을 정리해 둘 필요가 있다.

시뮬레이션 문제의 특징

문제에서 주어진 처리를 수행하기만 하면 되는 간단한 내용이 주를 이룬다.
“이런 과정을 거쳐서 나온 결과가 무엇인가?” 라고 물어보는 문제가 많다.
일반적으로 2차원 공간을 다루는 문제가 많이 나온다.
2차원 공간을 다루기 위해 행렬(Matrix) 개념을 사용한다.
이차원 공간에서의 방향 벡터가 자주 나온다.

시뮬레이션 문제 종류

알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
적절한 라이브러리를 찾아서 사용해야 하는 문제

주요 유형

2차원 공간을 다루는 문제가 자주 나온다. → 방향(상, 하, 좌, 우)에 대한 나만의 처리 방식이 있으면 좋다!
특정 게임을 구현하는 문제 → 몇 가지 자체적인 테스트 케이스를 만들어주면 유용하다!

필요한 기술

문제를 천천히 잘 읽고 빠진 조건 없이 메모한다. → 그림이나 표처럼 코드 작동 과정이 명확히 보이게끔하면 좋다!
문제 풀이에 적절한 자료구조를 사용한다. → 단일 원소면 set, 앞뒤로 원소를 자유롭게 넣고 빼려면 deque …

자주나오는 개념

행렬

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.

for i in range(5):
    for j in range(5):
        print('(', i, ',', j, ')', end=' ')
    print()

벡터

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x, y = 2, 2

for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

결론

많은 문제를 풀어보고, 다른 사람 코드도 참조하는게 좋다!
단번에 모든 테스트 케이스를 통과할 만한 코드를 짜긴 어렵다!
→ 틈틈이 코드 사이에 주석을 달아 디버깅을 편하게 해주자!
자신이 사용할 수 있는 라이브러리에 따라, 사용 언어에 따라 난이도가 달라진다. 따라서 많은 문제들을 풀어보며 언어에 따른 다양한 라이브러리를 경험해보는 것이 중요하다.
자주 사용되는 구현 스킬들을 정리하는 것도 좋은 방법(https://kimjingo.tistory.com/205)
→ 배열 shift, 원소 하나 삭제,
→ 2차원 배열의 나선형 알고리즘(달팽이문제), 배열 회전 문제등
다양한 문제를 경험해보는 것이 중요+ 자주 나오는 구현 스킬 정리

기타

알고리즘 교재나 문제 풀이 사이트에 따라서 시뮬레이션, 구현, 완전탐색 유형을 다르게 일컬을 수도 있다. 코딩 태스트에서의 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억하면 된다.

전체탐색 vs 시뮬레이션

시뮬레이션: 수행해야 하는 과정이 모두 나와있는 문제
전체탐색: 모든 패턴을 조사해야 하는 것과 그것을 필요로 하는 문제

알고리즘 문제 해결 과정

일반적인 알고리즘 문제 해결 과정

지문 읽기 및 컴퓨터적 사고
요구사항(복잡도) 분석
문제 해결을 위한 아이디어 찾기
소스코드 설계 및 코딩

일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결

코테에서 자주 출제되는 유형

브루트 포스, DFS, BFS, 시뮬레이션/구현, DP, 그리디, 이분탐색, 투포인터

그중 가장 많이 출제되는 유형은 브루트 포스, DFS, BFS, 시뮬레이션/구현