[Algorithm] 시뮬레이션, 구현

시뮬레이션, 구현

시뮬레이션 및 구현 문제는 문제에서 제시한 상황을 알고리즘으로 수행해내도록 구현하는 문제이다.

일반적으로 게임 상황을 재현하는 문제들이 자주 등장한다.

예를들면 다음과 같은 문제들이다.

 

카카오 블라인드 채용 문제

 

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

 

이런 형태의 문제들은 딱히 대단한 전략을 갖고있어야 하는것은 아니지만,

분석해야하는 요구사항이나, 구현해야하는 코드량과 예외처리들이 많기 때문에,

생각보다 시간을 많이 잡아먹게 된다.

그리고 그러한 이유 때문에 여러 기업에서도 실력측정용으로 자주 등장하는 유형이다.

딱히 이런 유형을 깔끔하게 처리할 수 있는 마법같은 전략이 있는 것은 아니지만,

그래도 이런 시뮬레이션 문제들에 공통적으로 등장하는 개념들과,

이런 유형을 다루기 위한 구현 습관들은 알아둘 필요가 있다.

 

 

모듈화

모듈화란, 공통적 혹은 반복적으로 사용되는 코드를 재활용하기 쉬운 형태로 분리하는 작업을 의미한다.

특히 시뮬레이션 문제에서는 어떤 반복적인 작업들에 대한 요구사항이 자주 등장한다.

예를들면 테트리스 게임에서 블럭을 떨어뜨리는 기능, 블럭을 제거하는 기능, 블럭을 회전시키는 기능 등이 있을 것이다.

이러한 기능들은 현재 뿐만 아니라 매래에도 혹은 다른 모듈 내에서도 사용되게 될 가능성이 크기 때문에,

함수 형태로 분리하여 설계하는것이 좋을 것이다.

 

 

데이터의 분리

구현작업을 할 때 코드가 어려워지는 큰 이유 중 하나는 데이터를 따로 분리하지 않기 때문이다.

배열에서 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

 

어떤 특정 위치를 인풋으로 받고, 그 위치에서부터 직사각형 검사를 한다면 다음과 같이 구현할 수 있을 것이다.

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을 반복하면 모든 데이터가 회전됨을 알 수 있다.

인덱스의 변화를 어떤 행동 데이터로 본다면 다음과 같이 나타낼 수 있을 것이다.

//아래, 오른쪽, 위, 왼쪽
const vector<Vec> directions = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};

또한 각 행동들이 몇 번씩 수행되어야 하는지도 query의 크기를 통해 미리 알아낼 수 있을 것이다.

위에 예제에서는 다음 순서대로 swap하며 지나가면 된다.

아래, 아래, 아래, 오른쪽, 오른쪽, 위, 위, 위, 왼쪽

마지막 왼쪽은 한번 수행하지 않아야 문제에서 요구하는 회전을 구현할 수 있다.

그러므로 수행 횟수는 다음과 같다.

3,			2,			3,			1
끝 - 시작(행)		끝 - 시작(열)		끝 - 시작(행)		끝 - 시작(열) - 1

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;
        }
    }
}

 

이처럼 문제에서 제시하는 조건이나 행동을 데이터수준으로 끌고올 수 있다면,

구현이 훨씬 쉬워질 것이다.