[ps] 순환되는 행렬 인덱스 (Index)

N × N 행렬 탐색 문제를 풀다보면 1번 행(열)과 N번 행(열) 연결되는 경우가 있다.

▶ 1번 행 위에 N번행이 존재하고 / N번 행 아래에 1번행이 존재하는 경우

 

임의의 위치 (x, y)에서 상 / 하 / 좌 / 우 방향 중 한 가지 방향으로 k 칸 이동한다고 했을 때,

▶ 10 × 10 크기의 map[10][10] 변수가 주어지고, 인덱스 범위는 0 ~ 9 이다.

K = K % N;
int nextX = (cur.x + (dx[dir] * K) + N) % N
int nextY = (cur.y + (dy[dir] * K) + N) % N

(K의 수치가 크게 주어지는 경우 1 Cycle 기준으로 나머지 연산 처리)

 

도착하는 위치를 크게 아래 4가지 경우로 고려한다.

- 증가해서 (우측 이동) 범위 안에 도착하는 경우

- 증가해서 (우측 이동) 범위를 초과하는 경우

- 감소해서 (좌측 이동) 범위 안에 도착하는 경우

- 감소해서 (좌측 이동) 범위를 초과하는 경우

 

계산식을 if문으로 풀어서 구현

#include <stdio.h>

// 상하좌우
enum {
       UP = 0,
       DOWN = 1,
       LEFT = 2,
       RIGHT = 3,
};
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
const int N = 10;
int map[N][N], dir, K;
struct Node
{
       int x, y;
       void print()
       {
              printf("(%d, %d)", x, y);
       }
}cur;

inline int move(int pos, int s)
{
       pos = pos + s;
       if (pos >= N)
              return 0;
       else if (pos < 0)
              return N - 1;
       return pos;
}

int main()
{
       
       cur = {3, 7}; dir = RIGHT;
       K = 5;
       
       cur.print(); printf(" -> ");
       for (int i = 0; i < K; ++i)
       {
              cur.x = move(cur.x, dx[dir]);
              cur.y = move(cur.y, dy[dir]);
       }
       cur.print(); printf("\n");
}

위와 같이 구현다면 for문과 if문이 K만큼 반복되기 때문에 성능이 좋지 못하다.

현재 위치(x, y) / 방향 dir / 이동 횟수 K가 주어질 때, 계산식을 이용할 수 있다.

 

계산식 도출

(3, 7)에서 우측으로 5(=K)칸 이동한다고 했을 때,

    → (3, 2)로 이동된다.

우측으로 이동하므로 행(row)은 고정이고 열(col)만 계산했을 때,

▶ 7 + K = 7 + 5 = 12 → 12 % N = 12 % 10 = 2

 

(2, 2)에서 아래 방향으로 12(= K)칸 이동

열(col)은 고정되고,  행(row)만 계산한다.

▶ 2 + K = 2 + 12 = 14 → 14 % N = 14 % 10 = 4

이동하는 칸 개수 "12" 는 { N × N } 크기에서 1 Cycle보다 크기에 

실제로 12 % N = "2" 만큼만 더해서 위치를 계산해도 된다.

하지만 더해지는 수치가 int 범위를 넘어서서 계산되지 않는 경우에는 크게 고려하지 않아도 된다.

nextX = (curX + K) % N

nextY = (curY + K) % N

 

이번에는 감소하는 경우를 고려해보자.

(4, 5)에서 좌측으로 3칸(= K) 이동할 때,

5 - K = 5 - 3 = "2" → (4, 2) 가 된다.

 

(2, 2)에서 좌측으로 5칸(= K) 이동할 때,

열(col) 위치를 계산했을 때,

▶ 2 - 5 = -3 → map[][]의 범위를 벗어난다.

    → N - 3 = 10 - 3 = "7"

즉, 감소하는 경우에는 map의 범위를 벗어나는 경우에는

      해당 수치를 크기 N에서 빼주어야 한다. (음수 처리)

      * 이 부분은 map[][] 크기 N 더해서 나머지 연산하면 된다.

▶ 2 - K + N = 2 - 3 + 10 = 7 

     → 7 % N = 7 % 10 = 7

 

음수가 아닌 경우에도 정상적으로 처리되는 것을 확인할 수 있다.

(4, 5) → 좌측 3칸 이동 → (4, 2)

▶ 5 - 3 + N = 5 - 3 + 10 = 12 

    → 12 % N = 12 % 10 = 2

다음 위치 = (현재 위치 + 이동 횟수 + N) % N 

#include <stdio.h>

// 상하좌우
enum {
       UP = 0,
       DOWN = 1,
       LEFT = 2,
       RIGHT = 3,
};
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
const int N = 10;
int map[N][N], dir, K;
struct Node
{
       int x, y;
       void print()
       {
              printf("(%d, %d)", x, y);
       }
}cur;

int main()
{
       
       cur = {2, 2}; dir = LEFT;
       K = 5;
       
       cur.print(); printf(" -> ");
       
       cur.x = (cur.x + K * dx[dir] + N) % N;
       cur.y = (cur.y + K * dy[dir] + N) % N;
       
       cur.print(); printf("\n");
}

 

결론

for문으로 한 칸씩 이동하지 않고, 아래 계산으로 한번에 다음 위치를 구할 수 있다.

계산식만 잘 도출한다면 if 문을 사용하지 않아도 되기에

Code 가독성은 물론 성능적으로도 더 좋다.

 

위와 같은 계산식은 map 인덱스 범위를 {0 ~ N - 1}가 아닌 {1 ~ N}로 구현하는 등

문제 조건에 따라 상이할 수 있다.

계산식 도출이 명확하지 않은 경우에는 Code가 조금 지저분해지더라도

if 문 등으로 분기 처리하는 것이 오히려 문제 풀이에 안정적이라고 생각한다.

 

이러한 방식을 적용한 문제로 S사 코딩테스트 기출 등이 있다.

▶ BOJ 21610 마법사 사엉와 비바라기

[BOJ] 백준 21610 마법사 상어와 비바라기

 

Reference

- 삼성 SW 기출 모음  

- [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기  

- [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)  

- 알고리즘을 어떻게 공부해야 될까?  

- 삼성 SW 코딩 테스트 준비(A형)   

- 여러 정수 기준에 따른 우선순위 비교 및 정렬  

- BOJ 21610 마법사 사엉와 비바라기