문제의 힌트로 예상치 못했던 ‘시뮬레이션’이라는 단어가 나와서 놀랐습니다.
알고리즘에서 ‘시뮬레이션’은 특정 상황이나 문제를 실제로 일어나는 것처럼 단계별로 구현하는 방식입니다. 즉, 문제의 주어진 규칙이나 동작을 그대로 따라가면서 결과를 도출하는 겁니다.
일반적으로 성능에 초점을 맞춘 알고리즘 문제와는 조금 다르게, 구현에 초점을 맞춰 문제를 풀이해야 합니다.
일반적으로 다음과 같은 문제로 보일 때 시뮬레이션 문제라고 합니다.
따라서 문제의 상황에 따라 구현하므로, 알고리즘을 일반화 하는 것은 불가능합니다.
시뮬레이션 문제를 풀 때는, 우선 문제를 최대한 작은 조각으로 나누어서 이해해야 합니다. 보통은 구현시 코드가 복잡해지는 문제가 생기므로 구현할 부분들을 작게 나누는 것이 중요합니다.
<aside> 🌐
</aside>
2, 3, 5, 7, 11, 13, 17 과 같은 1과 자기 자신 만으로 나누어 떨어지는 1보다 큰 양의 정수를 말합니다.
시뮬레이션에 따라 문제를 푸는 가장 직접적인 방법은 반복문으로 숫자를 하나씩 돌면서 소수 인지 판별하는 것입니다. 2부터 n-1까지 숫자를 나누어 보며 O(n)번으로 판별할 수 있습니다.