ps:시뮬레이션
시뮬레이션 (Simulation)
- 알고리즘이라기 보다는, 그냥 시키는 대로 구현해서 돌려보는 가장 원초적인 문제풀이 방법이다.
- PS의 문제들을 정말 크게 나눠볼때
- '주어진 답 후보들 중에서, 조건을 만족하는 답을 찾아라' 라는 형태의 문제를 푸는 가장 원초적인 방법은 완전탐색이다. 모든 답후보들에 대해서 조건을 만족하는지 확인하는 것이다.
- '주어진 규칙대로 동작을 n번 수행한 뒤의 상태를 찾아라' 라는 형태의 문제를 푸는 가장 원초적인 방법은 시뮬레이션이다. 규칙을 다 프로그래밍 해서, 실제로 n번의 동작을 수행하고 상태를 확인하는 것이다.
- 그래서 단순 시뮬레이션으로 풀리는 문제를 풀때 가장 어려운 부분은, 알고리즘적인 발상이 아니라 복잡한 규칙을 실수없이 구현할 수 있는 구현 능력인 경우가 많다
- 물론 추가적으로, 동작을 수행해서 상태가 업데이트 되는 것을 효율적으로 처리하기 위해서 적합한 자료구조를 선택할수 있어야 하는 경우가 있다. 이것은 너무나 다양한 유형이 있어서 쉽게 정리하기 힘들다.
- 시뮬레이션처럼 보이지만 단순 시뮬레이션이 아닌 문제들으로 풀 수 없는 문제들은,
- n번의 동작을 일일히 수행해보지 않더라도, 한번에 n번 뒤의 상태가 어떻게 될지 계산할수 있는 경우.
- 문제에서 요구하는 것이 전체 상태가 아닌, 전체 상태의 일부분인 경우가 있다. 이때 n번 동작후의 전체 상태는 계산이 불가능하더라도 문제에서 요구하는 상태는 계산이 가능한 경우가 있다
- n스텝 뒤의 상태 계산이 가능한 경우, '처음으로 상태가 바뀌는 시점'을 물어볼수도 있다. 이때는 이분 탐색을 사용하면 된다. 상황에 때라서는 병렬 이분 탐색이 유용할 수도 있다
몇가지 팁
- 문제에서 요구하는 'n스텝 뒤의 상태'를 구하는 방법이 정말로 시뮬레이션밖에 없는지 생각해보자.
- 전체 변수값을 모두 추적하는 것은 한스텝씩 시뮬레이션하는 방법밖에 없다 하더라도, 문제에서 요구하는 '특정 변수값'은 n스텝 후의 값을 바로 계산하는 것이 가능한 경우가 있다. 이런 문제라면 단순 시뮬레이션으로 풀면 안된다.
- 'n스템 뒤의 상태 계산'이 가능한 경우, 문제에서 '처음으로 상태가 바뀌는 시점'을 물어볼수도 있다. 이때는 이분 탐색을 사용하면 된다. 상황에 때라서는 병렬 이분 탐색이 유용할 수도 있다
- 이론적으로 무한한 시간의 시뮬레이션을 돌려야 하는 문제
- 문제에서 직접적으로 무한한 시간이 주어지지 않더라도, n이 너무 커서 모두 시뮬레이션할 수 없다면 여기에 해당된다.
- '어떤 조건을 마지막으로 만족하는 시점이 언제인지' 또는 '어떤 조건을 만족하는 시점이 존재하는지' 와 같은 문제이다.
- 이것은 사실상, m스텝 이후에는 조건을 만족하는 경우가 존재하지 않는다는 전제가 있어야만 성립할 수 있는 문제이다.
- 이 상한값 m을 문제 조건들로부터 잘 유추해서, m스텝까지만 시뮬레이션을 돌리는 것이 정해이다
- 하지만 m을 잘 못구하겠다면, 그냥 돌릴수 있는 만큼 (시간이 허락하는대로) 최대한 돌려보고, 그때까지의 결과를 가지고 답을 제출해도 대충 맞는다
- 관련 문제
- 장난감 강아지 :
ps/시뮬레이션.txt · 마지막으로 수정됨: 2024/02/15 03:23 저자 teferi
토론