🤔 시뮬레이션 문제란?
특정 알고리즘 및 자료구조에 속하지 않고 빡세게 구현해야 하는 문제들 (일명 노가다)

📍결국 얼마나 빠르게 구현을 할 수 있는가가 중요. 구현 능력을 기르자.

코드를 짜기 전에 시간 복잡도를 먼저 대략적으로 계산해보고 1초 기준 5억 번 이하의 연산량이 나오는지 확인

예시 문제

1) 감시

https://www.acmicpc.net/problem/15683

• 접근 방법은 위의 두 단계를 거친다.
• 다만, cctv의 방향을 정할 때 각 변수들끼리 독립적인 상태에서 모든 조합을 확인해봐야 하니까 백트래킹은 조금 복잡하다.
• 다음과 같이 '진법'을 사용하자.

• 예를 들어 1번 cctv가 3개면 각 cctv마다 방향이 4개가 있으니까 4X4X4이다.
• 보다 수월한 코드 작성을 위해 모든 cctv는 방향 4개가 있다고 가정

• 오른쪽과 같은 코드를 통해 모든 조합 확인 가능

• 화살표를 따라 벽을 만나기 전까지 마크를 남김
• 💻 코드 참고

2) 스티커 붙이기

https://www.acmicpc.net/problem/18808

• 접근 방법은 위의 두 단계를 거친다.
• 회전하는 것은 규칙을 찾아야 한다.

• 헷갈리면 이렇게 직접 그려서 확인
• 💻 코드 참고

3) 2048 (Easy)

https://www.acmicpc.net/problem/12100

• 접근 방법은 위의 두 단계를 거친다.
• 2번의 경우 '감시' 문제의 cctv 방향을 정해줬던 것처럼 하면 된다.

• 한 행씩 블록 옮기는 아이디어1
• merged라는 배열이 필요
• 시간복잡도 O(N^2)

• 한 행씩 블록 옮기는 아이디어2
• merged라는 배열이 불필요
• 시간복잡도 O(N)

• 전체 시간 복잡도는 위와 같다.
• 💻 코드 참고

4) 치킨 배달

https://www.acmicpc.net/problem/15686

• 접근 방법은 위의 두 단계를 거친다.

• 백트래킹 or next_permutation 함수 이용

• 치킨 거리 구하는 코드는 간단하게 구현

• 폐업시키지 않을 치킨집을 뽑는 경우의 수는 6개나 7개를 뽑는 것이 가장 많은 경우의 수가 나오므로 시간 복잡도를 위와 같이 계산
• 💻 코드 참고