블록 스왑(Block Swap) 알고리즘은 배열 회전에 사용되는 매우 효율적인 알고리즘입니다. 이 알고리즘을 활용하면 O(n)의 시간 복잡도로 배열 회전 작업을 수행할 수 있습니다.
배열 회전 문제에서는 크기가 n인 배열 arr[]와 회전할 원소의 개수를 나타내는 숫자 k가 주어집니다.
배열 회전 예시
입력 −
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (회전 횟수)출력 −
{1, 8, 9, 2, 4, 6}설명 − 회전이 일어나면 맨 앞의 원소 하나가 마지막 위치로 이동하고, 나머지 원소들은 각각 한 칸씩 앞으로 이동합니다.
즉, 인덱스 0에 있던 원소는 인덱스 n-1로 이동하며, 나머지 원소들은 각자 이전 인덱스로 한 칸씩 당겨집니다.
블록 스왑 알고리즘이란?
블록 스왑 알고리즘은 배열을 여러 개의 블록(부분 배열)으로 나눈 뒤, 이 블록들을 서로 교환하는 방식으로 배열 회전을 정확하게 수행하는 기법입니다.
알고리즘 동작 과정
1단계 − 배열을 분할 지점 k를 기준으로 두 개의 부분 배열로 나눕니다. 이때 X = arr[0...k-1], Y = arr[k...n-1]이라고 합니다.
2단계 − X와 Y의 크기가 같아질 때까지 아래 과정을 반복합니다.
2.1단계 − 만약 X의 크기가 Y보다 크다면, X를 Y와 크기가 같은 X1과 나머지 X2로 분할합니다. 그런 다음 부분 배열 X1과 Y를 서로 교환(swap)합니다. 이렇게 하면 원래 배열 구조가 X1X2Y에서 YX2X1로 바뀝니다.
2.2단계 − 만약 Y의 크기가 X보다 크다면, Y를 X와 크기가 같은 Y2와 나머지 Y1로 분할합니다. 그런 다음 부분 배열 X와 Y2를 교환합니다. 이렇게 하면 원래 배열 구조가 XY1Y2에서 Y2Y1X로 바뀝니다.
3단계 − X와 Y의 크기가 같아졌다면, 두 부분 배열을 서로 교환합니다.
이 알고리즘은 동일한 코드 블록을 반복적으로 호출해야 합니다. 이러한 반복 호출은 재귀(recursive) 방식과 반복(iterative) 방식, 두 가지 접근법으로 구현할 수 있습니다. 아래에서 프로그램 예제와 함께 각 방식을 살펴보겠습니다.
예제 1: 재귀(Recursive) 방식 구현
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, int k){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgo(int arr[], int k, int n) {
if(k == 0 || k == n)
return;
if(k<(n-k)) {
swapSubArray(arr, 0, (n-k), k);
blockSwapAlgo(arr, k, (n-k));
}
else if(k>(n-k)){
swapSubArray(arr, 0, k, (n-k));
blockSwapAlgo((arr+n-k), (2*k-n), k);
}
else{
swapSubArray(arr, 0, (n-k), k);
return;
}
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgo(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
}실행 결과
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1
예제 2: 반복(Iterative) 방식 구현
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, int k){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgoIt(int arr[], int k, int size) {
int i, j;
if(k == 0 || k == size)
return;
i = k;
j = size - k;
while (i != j) {
if(i < j){
swapSubArray(arr, k-i, k+j-i, i);
j -= i;
}
else{
swapSubArray(arr, k-i, k, j);
i -= j;
}
}
swapSubArray(arr, k-i, k, i);
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgoIt(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
}실행 결과
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1
마무리
블록 스왑 알고리즘은 추가 메모리 없이 제자리(in-place)에서 배열을 회전할 수 있다는 점에서 공간 복잡도 측면에서도 유리합니다. 재귀 방식은 코드가 직관적이라 이해하기 쉬운 반면, 반복 방식은 함수 호출 오버헤드가 없어 성능 면에서 더 안정적입니다. 문제 상황과 요구 사항에 따라 적절한 구현 방식을 선택하시기 바랍니다.