[C++] 회전 알고리즘

이번 게시물에서는 구현의 첫번째인 회전 알고리즘에 대해 작성해보려 한다.

사실 회전 알고리즘은 너무 간단한 내용이라 게시물로 따로 정리할까 말까 고민하기도 했다.....

체계적으로 정리하기에 간단한 내용이라도 나눠서 정리하는게 낫다 생각해서 '회전 알고리즘'에 대해 따로 정리하기로 했다.

 

1. 회전 알고리즘

회전 알고리즘은 말 그대로 '회전'에 대한 내용이다.

코딩테스트에서 아래와 같은 회전판이 나온다면 코드로 어떻게 구현할지에 대한 내용이다.

여러가지 방법이 있겠지만, 이 게시물에서는 1차원 배열로 나타내는 방법을 작성하려 한다.

1

int arr[4] = { 1, 2, 3, 4 };

cs

1차원 배열로 나타내면 단순하게 다음과 같이 나타낼 수 있다.

처음에 말했던 것처럼 진짜 엄청 쉽다......

그런데 여기서 주의해야할 점이 회전이다.

 

1-1. 회전

회전판을 시계방향으로 회전한다 생각하면 아래와 같은 그림이 될 것이다.

만약에 시계방향으로 회전판을 회전했을때 상단에 오는 숫자의 값을 구하고 싶다면,

회전판 상단의 숫자는 1 -> 4 가 된다.

회전판을 보는 내 입장에서 시계방향으로 돌렸지만,

상단의 숫자는 회전판의 '1' 을 기준으로 반시계방향에 있는 '4'가 되었다.

회전판을 돌릴때 돌리는 방향에 따른 회전판의 위치 변화를 잘 생각해야 한다.

1-2. 큰 회전

회전을 위처럼 한 칸씩만 하면 상관이 없지만 만약에 회전이 회전판의 인덱스의 수보다 훨씬 큰 값이라면 어떻게 해야 할까?

만약에 아래와 같은 회전판에서 초기 값이 상단에 있는 1일때, 회전판을 시계방향으로 25칸 이동시키면 회전판의 상단 값은 어떻게 될까? 

회전판은 시계방향으로 회전할 때 다음과 같은 순서대로 회전한다.

1칸 이동

2칸 이동

3칸 이동

4칸 이동

회전판은 4칸, 즉 회전판의 인덱스 수만큼 이동 했을 때, 다시 초기의 회전판 상태가 된다.

다시 말하면, 4회, 8회, 12회.... 4n회. 4의 배수 회만큼 이동하면 초기 회전판 상태가 된다고 할 수 있다.

그러므로 회전판을 25칸 이동시킨다면, 25%4 => 1이므로,

1칸 이동한 

다음 상태가 되는 것을 알 수 있다.

 

회전판 개념을 사용하면 아래처럼 또는 아래보다 훨씬 많은 회전판을 사용하는 문제를 풀거나

회전판이 여러개가 중첩되어 있는 '회전탑' 같은 문제도 풀 수 있다.