시뮬레이션(Simulation)은 문제에 주어진 상황이 시간에 따라 변화하는 것을 직접 구현해서 문제를 해결하는 구현의 한 가지 방법이다. 시뮬레이션이 복잡한 문제들이 코딩 테스트(대회에는 별로 나오지 않는다)에 나오는 경우도 있는데, 이런 유형의 문제의 경우 헷갈리지 않게 구현하는 것이 중요하다.
[연습문제]
BOJ 14920. 3n+1 수열 (Bronze III)
유명한 문제다. 각각의 항을 직접 구하면서 $1$이 처음으로 나타나는 항을 찾으면 된다.
프린터 큐의 작동을 시뮬레이션하면서 각각의 문서가 인쇄되는 순서를 찾는다.
마찬가지로 공기청정기의 작동을 시뮬레이션하면 된다. 각각의 상태에 대해 $1$초 뒤의 상태와 현재 상태가 섞이지 않도록 구현해야 한다.
Thinkfun의 퍼즐 Tilt와 규칙이 같은데 구슬의 개수, 판의 크기에 제한이 있다. 각각의 방향으로 판을 기울이는 작업을 시뮬레이션하면 되는데 나중 글에서 설명할 백트래킹으로 구현해야 한다.
이 문제도 간단하지만은 않다. 최대한 구현을 단순하게 만드는 것이 중요한데, 어떤 방향으로 $x$만큼 이동하는 것과 그 반대 방향으로 $-x$만큼 이동하는 것이 같다는 점을 이용해 상어의 이동 방향이 위/아래와 왼쪽/오른쪽 중 하나만 남도록 바꿀 수 있다. 또한 상어의 위치와 진행 방향을 따로 처리하지 않고 하나의 값으로 묶어서 처리하면 구현이 조금 더 간단해진다.
CF 1191C. Tokitsukaze and Discard Items (1400)
각각의 차례에 아이템을 제거하는 과정을 시뮬레이션하면 된다. 아이템의 간격이 클 수 있기 때문에 다음 아이템까지의 거리가 먼 경우 한 번에 그 위치로 이동하게 하는 구현이 필요하다.
CF 1304C. Air Conditioner (1500)
각각의 손님이 찾아오는 시간에 대해 가능한 식당의 온도의 범위를 관리하면서 마지막 손님이 찾아올 때까지 가능한 범위가 존재하는지 확인하면 된다. 멀티테케 문제에서는 입력을 받으면서 바로 처리하다가 입력을 다 안 받고 다음으로 넘어가서 틀리는 경우가 자주 있으므로 주의해야 한다.
'Algorithm > B. Basic Algorithms' 카테고리의 다른 글
| 22. Recursion (0) | 2021.01.30 |
|---|---|
| 21. Greedy (0) | 2021.01.29 |
| 19. Brute Force (0) | 2021.01.28 |
| 18. Implementation (0) | 2021.01.28 |
| 17. Basic Algorithms Intro (0) | 2021.01.26 |
