% 연산을 이용한 Circular Array 구현 및 응용

PS를 하면 종종 Circular Array의 필요성을 느낄 때가 있다

아래의 문제들은 내가 circular 배열을 이용해서 푼 문제들의 목록이다

문제

www.acmicpc.net/problem/20055

20055번: 컨베이어 벨트 위의 로봇

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

www.acmicpc.net/problem/17822

17822번: 원판 돌리기

www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

 

그렇다면 circular array는 뭐고, problem solving에 어떻게 활용될까?

 

Circular Array는, 기존의 배열의 개념에 "마지막 element 다음 원소는 첫 번째 element"라는 조건을 추가한 자료구조다

크기가 N인 Array가 있다고 가정할 때, 일반적으로는 (index는 0~n-1) n-1번째 element가 마지막이고, n번째 부터는 접근이 불가능하다. 그러므로 인덱스를 배열의 크기로 제한해야 할 필요가 있다.

하지만 circular array에서는 이러한 제한이 없어진다. n-1번째 element의 다음(n번째)은 0번째 element이고, 그 다음(n+1번째)는 1번째 element이고, 등등

이러한 circular array의 구현은 생각보다 아주 간단하게 할 수 있다.

 

 

기존에 index를 통해 array에 접근했다면, 거기에 % 연산자를 추가해 (index % n)번째 array에 접근하면 된다.

 

 

위의 그림처럼 현재 current가 4라고 했을 때 current에서 3만큼 이동한 배열 값은 (4 + 3)%6 = 1이 된다. 

그림에서도 3칸 이동한 index가 1임을 나타낸다.

 

이러한 circular array의 개념은 배열의 회전 등에서 응용할 수 있다.

예를 들어, [0,1,2,3,4,5]의 배열을 2번 left shift 한다고 가정했을 때 결과는 [2,3,4,5,0,1]이 된다.

이렇게 left shift된 배열에 접근하는 방법에는, 실제로 배열을 한칸씩 밀어서 구현할 수도 있겠지만 circular array의 개념을 적용하여 접근하는 index에 변화를 주어도 가능하다.

	int n = 6;
	int array[6] = { 0,1,2,3,4,5 };
	int newArray[6];

	for (int i = 0; i < n - 2; i++) {
		newArray[i] = array[i + 2];
	}
	for (int i = 0; i < 2; i++) {
		newArray[n - 2 + i] = array[i];
	}//shift된 만큼 따로 옮겨주어야 함

	for (int i = 0; i < n; i++) {
		newArray[i] = array[(i + 2) % n];
	}

 직접 array를 옮겨주게 된다면 index가 n을 넘어갈 수 없기 때문에 위의 두 개의 for문처럼 두 번에 나누어서 옮겨줘야 한다.

하지만 circular array의 개념을 적용한다면 index는 2,3,4,5,0,1로 순차적으로 접근하기 때문에 한 번의 연산만으로도 가능하다.

그런데, 위와 같이 index가 증가하는 방향인 left shift에서는 적용이 가능하지만, index를 감소시킨 right shift에서는 적용이 힘들 수 있다.

Array[ (i -1) % n]을 하게 되면, i가 0일 때 필연적으로 에러가 발생하기 때문이다.

 

 

그러한 때에는 index가 0 이상이 될 만큼 n을 더해주면 된다. 어떤 수에 n의 배수를 더한 뒤 n으로 나눈 나머지는 처음 수와 항상 같기 때문이다.

이러한 개념을 응용해서 left, right shift된 배열에 대해서도 접근할 수 있다.

 

중요한 것은 index를 이용한 circular array의 구현이 실제 데이터에 적용되지 않아도 된다는 점 이다 ... !

삼성 20년도 하반기 기출문제인 '컨베이어 벨트 위의 로봇'에서는 1초가 지날 때 마다 내구도를 지닌 컨베이어 벨트(배열)을 1칸씩 이동시켜야 한다.

그러한 이동 과정을 실제로 구현한다면 아마 두 개의 큐를 이용해서, 두 번의 pop과 push가 발생할 것이다.

하지만 컨베이어 벨트가 이동한다는 행위를, 배열을 직접 값을 변경해서 구현하지 않고 circular index를 통해 추상적으로 구현한다면 아래와 같이 접근할 수 있다.

#include <cstdio>
int arr[2][205], n, k,ans,idx;
int count() {
	int sum = 0;
	for (int i = 0; i < 2 * n; i++)
		if (arr[1][i] <= 0)sum++;
	return sum;
}
int main() {	//arr[0] = 로봇 유무, arr[1] = 내구도
	scanf("%d%d", &n, &k);
	for (int i = 0; i < 2 * n; i++)scanf("%d", &arr[1][i]);

	while (++ans) {
		arr[0][(idx + n - 1) % (2 * n)] = 0;
		idx = (idx - 1 + 2 * n) % (2 * n);	//index를 -1

		
		for (int i = n-1; i >= 0; i--) {
			int cur = (idx + i) % (2 * n);	//현재 index
			if (i == n - 1) {
				arr[0][cur] = 0;
				continue;
			}
			if (!arr[0][cur])continue;

			int next = (cur + 1) % (2 * n);	//현재 index 다음의 index
            if (!arr[0][next] && arr[1][next] >= 1) {
				arr[0][next] = 1;
				arr[0][cur] = 0;
				arr[1][next]--;
			}
		}
		if (arr[0][idx] == 0 && arr[1][idx] >= 1) {
			arr[0][idx] = 1;
			arr[1][idx]--;
		}
		if (count() >= k)break;
	}

	printf("%d", ans);
	return 0;
}

컨베이어 벨트의 길이는 주어진 n의 두 배인 2*n이다.

현재 index는 계속해서 감소하게 구현하고(index가 0이 된다면 2*n), 현재 index에서 n만큼 오른쪽으로 이동한 칸에서 부터 감소하는 방향으로 로봇의 이동을 시작한다.

이렇게 구현한다면 하나의 array만 가지고 문제를 해결할 수 있다.

circular index를 이용한다면 배열의 잘못된 index 접근이 사라진다. 

 

circular index의 개념은 "배열이 회전하는 문제"에 대해 적용할 수 있다.

원판 돌리기, 톱니바퀴 문제 또한 원형의 배열이 회전하는 성질을 가지고 있기 때문에 circular index를 이용해서 해결할 수 있다.