[알고리즘] 시뮬레이션 문제를 풀려면 이것부터 알자!

시뮬레이션 문제는 어려운 구현, 노가다 느낌이 강한 문제들로 N * N 크기의 판에서 길 찾기를 하거나 간단한 게임을 구현하고 그 속에서 시뮬레이션을 돌려보는 느낌의 문제이다.

 

시뮬레이션 알고리즘은 정렬이나 그래프, 동적 계획법처럼 일반화하여 상황에 맞게 그 알고리즘을 사용하는 느낌은 아니다. 문제를 정확히 이해하고 문제를 부분 문제로 나누어서 차근차근 독립적인 함수로 구현하는 편이 디버깅하기도 좋고 예외처리에도 용이하다. 기본적으로 알아야 할 몇 가지 배경지식 외에는 본인의 구현력이 가장 중요하다. 행렬의 연산과 좌표계를 다루는 것만 알면 나머지는 구현의 문제이다.

---

행렬 연산

행렬 덧셈/뺄셈

행렬의 덧셈과 뺄셈은 간단하게 각 행렬의 동일한 위치에 있는 값들끼리 연산해 주면 된다. 당연히 두 행렬의 크기는 같아야 한다. 일반식으로 C [i, j] = A [i, j] + B [i, j]이다.

---

행렬 곱셈

행렬의 곱은 조금 복잡한데, A의 각 행과 B의 각 열의 원소들의 곱의 합이다. 즉, C의 i행 j열은 A의 i행과 B의 j열의 곱의 합이다. 따라서 A의 행 크기와 B의 열 크기가 같아야 하고 결과물의 크기는 A의 행 크기 * B의 열 크기의 행렬이 된다.

일반식으로 C [i, j] = A [i, 0] * B [0, j] + A [i, 1] * B [1, j] +...이다.

---

전치 행렬

행렬을 대각선 기준으로 대칭되는 원소들을 맞바꾼 행렬이다.

---

좌표 연산

2차원 배열은 2차원 배열로 구현할 수 있다. 그리고 주변 좌표를 탐색해야 하는 경우가 많은데, 이는 8개로 나눌 수 있다. 상하좌우 4개, 대각선 4개로 나누어서 if문 8개를 사용해서 구분할 수 있다. 그러나 if문을 8개 쓰면 코드가 굉장히 난잡해진다.  이를 간단하게 if문 하나로 처리할 수 있다.

 

x가 이동하는 경우인 dx와 y가 이동하는 경우인 dy 배열을 만들어서 반복문 하나로 구현이 가능하다.

 

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for(int i = 0 ~ 7)
  if([x + dx[i], y + dy[i] == 1) count++;