시뮬레이션, 구현, 완전 탐색은 서로 유사한 점이 많다.
시뮬레이션(Simulation)
- 일련의 명령에 따라서 개체를 차례대로 이동시키는 것
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
종류
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
특징
- 일반적으로 2차원 공간을 다루는 문제가 많이 나온다
- 2차원 공간을 다루기 위해 행렬(Matrix) 개념을 사용
시뮬레이션, 구현
문제에서 제시한 상황을 알고리즘으로 수행해내도록 구현하는 문제
일반적으로 게임 상황을 재현하는 문제들이 자주 등장한다.
예를들면 다음과 같은 문제들이다.
<카카오 블라인드 채용 문제>
이 유형 문제는 아래 링크에서 확인할 수 있다.
https://programmers.co.kr/learn/courses/30/lessons/17679
이런 형태의 문제들은 딱히 대단한 전략을 갖고있어야 하는것은 아니지만,분석해야하는 요구사항이나 구현해야하는 코드량과 예외처리들이 많기 때문에 생각보다 시간을 많이 잡아먹게 된다.
그리고 그러한 이유 때문에 여러 기업에서도 실력측정용으로 자주 등장하는 유형이다.
딱히 이런 유형을 깔끔하게 처리할 수 있는 마법같은 전략이 있는 것은 아니지만, 그래도 이런 시뮬레이션 문제들에 공통적으로 등장하는 개념들과 이런 유형을 다루기 위한 구현 습관들은 알아둘 필요가 있다.
모듈화
모듈화란, 공통적 혹은 반복적으로 사용되는 코드를 재활용하기 쉬운 형태로 분리하는 작업을 의미한다.
특히 시뮬레이션 문제에서는 어떤 반복적인 작업들에 대한 요구사항이 자주 등장한다.
예를들면 테트리스 게임에서 블럭을 떨어뜨리는 기능, 블럭을 제거하는 기능, 블럭을 회전시키는 기능 등이 있을 것이다.
이러한 기능들은 현재 뿐만 아니라 매래에도 혹은 다른 모듈 내에서도 사용되게 될 가능성이 크기 때문에,함수 형태로 분리하여 설계하는것이 좋을 것이다.
데이터의 분리
구현작업을 할 때 코드가 어려워지는 큰 이유 중 하나는 데이터를 따로 분리하지 않기 때문이다.
배열에서 2 x 2 직사각형을 찾는 코드를 작성한다고 생각해보자.
1 1 0 0 0
1 1 0 0 0
1 0 0 1 0
0 1 0 0 1
0 0 0 1 1어떤 특정 위치를 인풋으로 받고, 그 위치에서부터 직사각형 검사를 한다면 다음과 같이 구현할 수 있을 것이다.
(아래 코드는 좋지않은 코드의 예시이며, 특정 위치p에서부터 오른쪽 아래로만 검사하는 코드이다)
bool CheckRect(int board[5][5], Pos p)
{
if (p.i + 1 >= 5 || p.j + 1 >= 5)
return false;
if (board[p.i][p.j] == 1 &&
board[p.i + 1][p.j] == 1 &&
board[p.i][p.j + 1] == 1 &&
board[p.i + 1][p.j + 1] == 1)
{
return true;
}
return false;
}하지만 이 코드는 데이터를 코드 수준에서 처리하려 했다는 점에서 문제가 있다.
만약 테스트해야하는 직사각형이 2 x 2, 4 x 2, 2 x 4 로 늘어난다면 어떻게 될까??
조건을 위한 코드량과 심지어 예외처리를 위한 코드량도 늘어날 것이다.
만약 데이터와 코드를 분리한다면 어떻게 될까??
bool CheckRect(int board[5][5], Pos x)
{
vector<Pos> v = { {0, 0}, {0, 1}, {1, 0}, {1, 1} };
for (Pos y : v)
{
int i = x.i + y.i;
int j = x.j + y.j;
if (i >= 5 || j >= 5 || board[i][j] != 1)
return false;
}
return true;
}이렇게 한다면 테스트해야하는 직사각형에 대한 데이터만 교체해주면,
어떤 형태의 직사각형이 오더라도 테스트가 가능하다.
그리고 예외처리에 대한 코드도 변하지 않는다.
이렇게 데이터들만 따로 관리하는 자료구조를 두고 데이터를 활용하는 방향으로 구현한다면,
시뮬레이션 및 구현 문제들을 풀 때 많은 도움이 될 것이다.
물론 어디서부터 어디까지가 데이터인지 먼저 구분해낼 수 있어야한다.
조건 or 행동의 데이터화
위에서 데이터에 대한 부분들을 분리하여 많은 이점을 취했었다.
여기에 더해, 만약 조건 및 행동들을 데이터화시킬 수 있다면,이 부분들에 대해서도 데이터 분리의 이점을 똑같이 취할 수 있게 된다.
다음문제를 보자.
https://programmers.co.kr/learn/courses/30/lessons/77485
어떤 특수한 알고리즘 전략이 필요한 어려운 문제는 아니지만,
구현에 자신이 없는 사람들 입장에서는 시간을 잡아먹는 귀찮은 문제일 것이다.
이 문제에서 제일 귀찮은 부분은 회전 시 인덱스의 변화를 컨트롤하는 부분이다.
적절한 타이밍마다 변화되어야하는 인덱스가 달라지게 구현해야 하는데,
이것을 코드에서 다 작업하려고 하면 꽤나 복잡해질 수 있다.
그럼 어떻게 해야하는가?
먼저 문제를 보면 시작 위치부터 회전방향의 반대방향으로 swap을 반복하면 모든 데이터가 회전됨을 알 수 있다.
(가장 첫 원소는 계속 swap에 걸려서 계속 움직이고, 심지어 시계 반대방향으로 계속 움직이니 무슨소리인가 싶을 수 있겠지만, 반대로 생각해보면 그렇게 첫 시작 원소가 처음에 swap한 원소를 만나기 직전까지(그래서 마지막에 왼쪽으로 가는건 횟수 -1 해줘야한다)만 swap하면 결론적으로 시계방향으로 한 번 움직인게 된다)
인덱스의 변화를 어떤 행동 데이터로 본다면 다음과 같이 나타낼 수 있을 것이다.
//아래, 오른쪽, 위, 왼쪽 (시계반대방향)
const vector<Vec> directions = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};또한 각 행동들이 몇 번씩 수행되어야 하는지도 query의 값을 통해 미리 알아낼 수 있을 것이다.
const vector<int> movecounts = { qrows, qcolumns, qrows, qcolumns - 1 };
이렇게 작업이 되었다면, 이제 movecounts 횟수만큼 directions로 이동시켜주며, swap하면 된다.
void Rotate(vector<int>& query)
{
int si = query[0] - 1;
int sj = query[1] - 1;
int fi = query[2] - 1;
int fj = query[3] - 1;
int qrows = fi - si;
int qcolumns = fj - sj;
const vector<Vec> directions = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const vector<int> movecounts = { qrows, qcolumns, qrows, qcolumns - 1 };
for (int i = 0; i < directions.size(); ++i)
{
Vec dir = directions[i];
int moves = movecounts[i];
for (int j = 0; j < moves; ++j)
{
int nexti = si + dir.i;
int nextj = sj + dir.j;
swap(arr[si][sj], arr[nexti][nextj]);
si = nexti;
sj = nextj;
}
}
}이처럼 문제에서 제시하는 조건이나 행동을 데이터수준으로 끌고올 수 있다면,
구현이 훨씬 쉬워질 것이다.
참고
https://velog.io/@jehjong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84Implementation-%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98%EA%B3%BC-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89
https://algorfati.tistory.com/131
