이 글에서는 주어진 배열을 k개 요소만큼 오른쪽으로 회전시키기 위한 반전 알고리즘(Reversal Algorithm)에 대해 자세히 살펴보겠습니다. 먼저 문제를 이해해 보겠습니다.
입력 : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
출력 : { 43, 7, 3, 7, 4, 6, 2, 6 }
설명 : 배열의 모든 요소를 오른쪽으로 4칸씩 회전하면 { 43, 7, 3, 7, 4, 6, 2, 6 }이 됩니다.
입력 : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
출력 : { 4, 9, 3, 8, 5, 8, 2, 1 }
문제 해결 접근 방법
가장 직관적인 방법은 각 요소를 오른쪽으로 한 칸씩 이동하는 작업을 k번 반복하는 것입니다. 하지만 이 방식의 시간 복잡도는 O(k × N)으로, 배열의 크기나 k 값이 커질수록 비효율적입니다.
반전 알고리즘은 '배열을 뒤집는' 연산을 활용해 회전을 구현하는 기법입니다. 특정 범위를 뒤집는 것만으로 배열 회전이 가능하며, 동작 순서는 다음과 같습니다.
- 1단계 : 배열 전체를 뒤집습니다.
- 2단계 : k가 배열 크기 N보다 클 수 있으므로, k를 k % N 값으로 조정합니다.
- 3단계 : 배열의 처음 k개 요소를 다시 뒤집어 원래 순서로 되돌립니다.
- 4단계 : 나머지 요소 범위(k부터 N-1까지)를 뒤집습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void reverse(int nums[], int start, int end) {
int temp = 0;
// 시작 요소와 끝 요소를 교환하며 배열을 뒤집음
while (start <= end) {
temp = nums[end];
nums[end] = nums[start];
nums[start] = temp;
start++;
end--;
}
}
int main() {
int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5};
int N = sizeof(arr) / sizeof(arr[0]);
int k = 4;
// 배열 전체를 뒤집기
reverse(arr, 0, N - 1);
k = k % N;
// 0부터 k-1까지의 요소 범위를 뒤집기
reverse(arr, 0, k - 1);
// k부터 마지막 요소까지의 범위를 뒤집기
reverse(arr, k, N - 1);
cout << "k칸 회전 후 배열 : ";
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
return 0;
}
실행 결과
k칸 회전 후 배열 : 6 2 4 5 4 6 2 6 43 7 3
시간 복잡도 분석
반전 알고리즘은 배열 전체를 한 번 뒤집고, 두 부분을 각각 한 번씩 더 뒤집으므로 총 세 번의 순회로 작업이 완료됩니다. 따라서 전체 시간 복잡도는 O(N)입니다. 또한 추가 메모리 없이 제자리(in-place)로 수행되므로 공간 복잡도 역시 O(1)로 매우 효율적입니다.
마무리
이 글에서는 반전 알고리즘을 사용하여 배열을 k개 요소만큼 오른쪽으로 회전시키는 문제를 다루었습니다. 단순 이동 방식의 O(k × N)과 달리, 반전 알고리즘은 세 번의 뒤집기 연산만으로 O(N) 시간 안에 문제를 해결할 수 있으며, C++ 구현 코드도 함께 확인했습니다. 이 코드는 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.