알고리즘이란?
알고리즘은 주어진 문제를 해결하기 위해 일정한 순서대로 수행되는 명령어들의 집합입니다. 이번 글에서는 배열 회전에 활용되는 반전 알고리즘(Reversal Algorithm)의 원리를 살펴보고, 이를 C언어로 직접 구현해 보겠습니다.
기본 용어 정리
배열(Array) – 동일한 데이터 타입의 요소들을 하나의 컨테이너에 담은 자료구조입니다. 배열의 크기(요소 개수)는 배열을 선언하는 시점에 고정됩니다.
배열 회전(Array Rotation) – 배열에 담긴 요소들의 순서를 바꾸는 작업입니다. 각 요소의 인덱스를 하나씩 증가시키고, 마지막 요소는 인덱스 0으로 이동시키는 방식으로 진행됩니다.
배열 회전 예시
Array[] = {3, 6, 8, 1, 4, 10}
왼쪽으로 2회 회전하면,
Array[] = {8, 1, 4, 10, 3, 6}
반전 알고리즘(Reversal Algorithm)이란?
배열 회전 방법 중 하나인 반전 알고리즘은 배열을 두 개의 부분 배열(subarray)로 나누고, 각각을 뒤집은 뒤 다시 합치고, 마지막으로 전체를 한 번 더 뒤집는 방식으로 회전을 수행합니다. 추가 메모리 없이 제자리(in-place)에서 처리할 수 있어 매우 효율적인 기법으로 널리 사용됩니다.
알고리즘 단계
입력 : 배열 arr[], 회전할 위치 d, 배열의 길이 n 1단계 : 배열을 크기 d와 n-d의 두 부분 배열 a1[d]와 a2[n-d]로 분할합니다. 2단계 : reverse 함수를 이용해 두 부분 배열을 각각 뒤집습니다. 3단계 : a1과 a2를 다시 합쳐 원래 크기의 배열을 만듭니다. 4단계 : 합쳐진 배열 전체를 한 번 더 뒤집으면 회전된 배열이 완성됩니다. 5단계 : 표준 출력 함수로 최종 배열을 출력합니다.
동작 예시
arr[] = {1, 4, 2, 8, 3, 6, 5}, d = 3, n = 7
a1[] = {1, 4, 2} // 첫 번째 부분 배열
a2[] = {8, 3, 6, 5} // 두 번째 부분 배열
a1r[] = {2, 4, 1} // a1을 뒤집은 결과
a2r[] = {5, 6, 3, 8} // a2를 뒤집은 결과
ar[] = {2, 4, 1, 5, 6, 3, 8} // a1r + a2r
arr[] = {8, 3, 6, 5, 1, 4, 2} // 최종 회전 결과
C 언어 구현 예제
#include <stdio.h>
// start부터 end까지의 구간을 뒤집는 함수
void reverse(int arr[], int start, int end){
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
int main(){
int arr[] = { 54, 67, 12, 76, 25, 16, 34 };
int n = 7;
int d = 2;
printf("초기 배열 :\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
// 반전 알고리즘 적용
reverse(arr, 0, d - 1); // 앞부분 d개 요소 뒤집기
reverse(arr, d, n - 1); // 나머지 부분 뒤집기
reverse(arr, 0, n - 1); // 전체 뒤집기
printf("\n왼쪽으로 %d칸 회전한 배열 :\n", d);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
실행 결과
초기 배열 : 54 67 12 76 25 16 34 왼쪽으로 2칸 회전한 배열 : 12 76 25 16 34 54 67
마무리
반전 알고리즘은 세 번의 reverse 연산만으로 배열 회전을 완료하며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 별도의 임시 배열이 필요 없고 구현이 단순해서 대용량 데이터를 다룰 때에도 효율적으로 활용할 수 있습니다.