C 프로그래밍에서 배열을 왼쪽으로 지정한 횟수만큼 회전하는 것은 자주 등장하는 기본 알고리즘 문제입니다. 이 글에서는 배열을 왼쪽으로 n칸 회전하는 논리를 단계별로 살펴보고, 실제로 동작하는 C 예제 코드와 실행 결과까지 함께 확인해 보겠습니다.
문제 개요
입력: arr[] = 1 2 3 4 5 6 7 8 9 10 N = 3 출력: 4 5 6 7 8 9 10 1 2 3
풀이 접근 방식
배열 arr에 요소들을 입력받습니다.
회전할 횟수를 변수 N에 저장합니다.
배열을 왼쪽으로 1칸씩 회전하는 동작을 N번 반복합니다. 여기서 왼쪽 회전이란 모든 요소를 한 칸씩 앞으로 이동시키고, 첫 번째 요소를 마지막 위치로 옮기는 것을 의미합니다.
예제 코드
#include <stdio.h>
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int i, j, N = 3;
int len = sizeof(arr) / sizeof(arr[0]);
/* 배열을 N번 왼쪽으로 회전 */
for (i = 0; i < N; i++) {
int first = arr[0];
for (j = 0; j < len - 1; j++) {
arr[j] = arr[j + 1];
}
arr[len - 1] = first;
}
/* 회전된 배열 출력 */
for (i = 0; i < len; i++) {
printf("%d\t", arr[i]);
}
return 0;
}실행 결과
4 5 6 7 8 9 10 1 2 3
코드 동작 원리
바깥쪽 루프는 회전 횟수 N만큼 반복됩니다. 각 회전이 시작되면 첫 번째 요소를 임시 변수 first에 저장하고, 안쪽 루프가 나머지 요소를 모두 한 칸씩 앞으로 당깁니다. 안쪽 루프가 끝나면 저장해 두었던 첫 번째 요소를 배열의 마지막에 넣어 한 번의 왼쪽 회전을 완성합니다. 이 과정을 N번 반복하면 배열 전체가 왼쪽으로 N칸 회전됩니다.
이 방식은 한 번의 회전에 배열 길이만큼의 연산이 필요하므로 시간 복잡도는 O(N × len)입니다. 요소 수와 회전 횟수가 모두 크다면 아래에서 소개하는 반전 알고리즘을 사용하는 것이 좋습니다.
더 효율적인 방법: 반전(Reverse) 알고리즘
배열을 세 번 뒤집는 방법을 사용하면 O(len) 시간에 회전을 처리할 수 있습니다.
처음 N개의 요소를 뒤집습니다. → 3 2 1 4 5 6 7 8 9 10
나머지 요소를 뒤집습니다. → 3 2 1 10 9 8 7 6 5 4
배열 전체를 다시 뒤집습니다. → 4 5 6 7 8 9 10 1 2 3
세 번의 뒤집기만으로 원하는 회전 결과를 얻을 수 있으므로, 대용량 데이터를 다룰 때도 효율적으로 동작합니다.