시뮬레이션 (Simulation)

'주어진 답 후보들 중에서, 조건을 만족하는 답을 찾아라' 라는 형태의 문제를 푸는 가장 원초적인 방법은 완전탐색이다. 모든 답후보들에 대해서 조건을 만족하는지 확인하는 것이다.

'주어진 규칙대로 동작을 n번 수행한 뒤의 상태를 찾아라' 라는 형태의 문제를 푸는 가장 원초적인 방법은 시뮬레이션이다. 규칙을 다 프로그래밍 해서, 실제로 n번의 동작을 수행하고 상태를 확인하는 것이다.

물론 추가적으로, 동작을 수행해서 상태가 업데이트 되는 것을 효율적으로 처리하기 위해서 적합한 자료구조를 선택할수 있어야 하는 경우가 있다. 이것은 너무나 다양한 유형이 있어서 쉽게 정리하기 힘들다.

n스텝 뒤의 상태 계산이 가능한 경우, '처음으로 상태가 바뀌는 시점'을 물어볼수도 있다. 이때는 이분 탐색을 사용하면 된다. 상황에 때라서는 병렬 이분 탐색이 유용할 수도 있다

전체 변수값을 모두 추적하는 것은 한스텝씩 시뮬레이션하는 방법밖에 없다 하더라도, 문제에서 요구하는 '특정 변수값'은 n스텝 후의 값을 바로 계산하는 것이 가능한 경우가 있다. 이런 문제라면 단순 시뮬레이션으로 풀면 안된다.

'n스템 뒤의 상태 계산'이 가능한 경우, 문제에서 '처음으로 상태가 바뀌는 시점'을 물어볼수도 있다. 이때는 이분 탐색을 사용하면 된다. 상황에 때라서는 병렬 이분 탐색이 유용할 수도 있다

문제에서 직접적으로 무한한 시간이 주어지지 않더라도, n이 너무 커서 모두 시뮬레이션할 수 없다면 여기에 해당된다.

'어떤 조건을 마지막으로 만족하는 시점이 언제인지' 또는 '어떤 조건을 만족하는 시점이 존재하는지' 와 같은 문제이다.

이것은 사실상, m스텝 이후에는 조건을 만족하는 경우가 존재하지 않는다는 전제가 있어야만 성립할 수 있는 문제이다.

이 상한값 m을 문제 조건들로부터 잘 유추해서, m스텝까지만 시뮬레이션을 돌리는 것이 정해이다

하지만 m을 잘 못구하겠다면, 그냥 돌릴수 있는 만큼 (시간이 허락하는대로) 최대한 돌려보고, 그때까지의 결과를 가지고 답을 제출해도 대충 맞는다