티스토리 뷰

카테고리 없음

배열 회전(Array Rotation) 알고리즘

머니지니87 2026. 2. 3. 11:19

목차


    반응형

    소프트웨어 엔지니어링 인터뷰나 알고리즘 코딩 테스트에서 '배열 회전(Array Rotation)'은 가장 빈번하게 등장하는 주제 중 하나입니다. 언뜻 보기에 단순히 원소의 위치를 옮기는 쉬운 문제처럼 보이지만, 제약 조건(메모리 사용량, 실행 시간)에 따라 해결 방법이 극명하게 갈리는 문제이기도 합니다. 특히 대용량 데이터를 처리하는 실무 환경에서 배열을 효율적으로 제어하는 능력은 시스템 성능과 직결됩니다.

    단순히 빈 배열을 하나 더 만들어 데이터를 복사하는 방식은 가장 쉽지만, 공간 복잡도 측면에서 비효율적입니다. 본 글에서는 메모리 사용량을 최소화하면서도 빠른 속도로 배열을 회전시킬 수 있는 다양한 알고리즘을 비교 분석하고, 현업에서 가장 선호하는 '역전 알고리즘(Reversal Algorithm)'의 구현 방법을 상세히 다루겠습니다.

    1. 배열 회전의 정의와 문제 상황

    배열 회전이란, 배열 내의 모든 요소를 특정 방향(왼쪽 또는 오른쪽)으로 $d$만큼 이동시키는 작업을 의미합니다. 배열의 크기를 $n$, 이동 횟수를 $d$라고 가정할 때, 인덱스 범위를 벗어나는 요소는 반대편 끝으로 다시 들어오는 순환 구조를 가집니다.

    1-1. 단순 접근법 (Temp Array)

    가장 직관적인 방법은 임시 배열(Temporary Array)을 생성하여 회전된 결과를 저장하는 것입니다. 예를 들어, 크기 $d$만큼의 임시 배열에 앞쪽 요소를 저장해두고, 나머지 요소들을 앞으로 이동시킨 뒤, 임시 배열의 값을 뒤쪽에 붙이는 방식입니다.

    • 장점: 구현이 매우 간단하고 직관적입니다.
    • 단점: 배열의 크기가 클수록 추가적인 메모리 공간($O(d)$ 또는 $O(n)$)이 필요합니다. 메모리가 제한된 임베디드 환경이나 대규모 데이터 처리 시에는 적합하지 않습니다.

    1-2. 하나씩 이동하기 (Rotate One by One)

    모든 요소를 한 칸씩 이동시키는 작업을 $d$번 반복하는 방법입니다.

    • 공간 복잡도: $O(1)$로 추가 메모리가 거의 필요 없습니다.
    • 시간 복잡도: $O(n \times d)$가 됩니다. 만약 $d$가 $n$에 가깝고 $n$이 매우 크다면, 실행 시간이 기하급수적으로 늘어나 '시간 초과(Time Limit Exceeded)'가 발생할 수 있습니다.

    2. 최적의 해결책: 역전 알고리즘 (Reversal Algorithm)

    시간 복잡도 $O(n)$을 유지하면서도 공간 복잡도를 $O(1)$로 억제할 수 있는 가장 우아한 해결책은 역전 알고리즘(Reversal Algorithm)입니다. 이 방식은 배열의 특정 구간을 뒤집는(Reverse) 연산만을 사용하여 회전을 구현합니다.

    2-1. 알고리즘의 작동 원리

    배열 $A$를 왼쪽으로 $d$칸 회전시킨다고 가정할 때, 알고리즘은 다음 세 단계로 진행됩니다. 여기서 $n$은 배열의 길이입니다.

    1. Step 1: 배열의 앞부분 $A[0 ... d-1]$을 역순으로 뒤집습니다.
    2. Step 2: 배열의 뒷부분 $A[d ... n-1]$을 역순으로 뒤집습니다.
    3. Step 3: 배열 전체 $A[0 ... n-1]$를 역순으로 뒤집습니다.

    이 방법은 추가적인 배열 할당 없이 인덱스 교환(Swap)만으로 수행되므로 메모리 효율이 극대화됩니다.

    3. 코드 구현 (Java/C++ Logic)

    아래 코드는 역전 알고리즘을 사용하여 배열을 왼쪽으로 $d$만큼 회전시키는 예제입니다. 언어는 JavaScript를 사용하였으나, 로직은 C++, Java 등 모든 언어에 동일하게 적용됩니다.

    
/**
 * 배열의 start 인덱스부터 end 인덱스까지를 역전(Reverse)시키는 함수
 * @param {Array} arr - 대상 배열
 * @param {Number} start - 시작 인덱스
 * @param {Number} end - 종료 인덱스
 */
function reverseArray(arr, start, end) {
    while (start < end) {
        let temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

/**
 * 역전 알고리즘을 이용한 왼쪽 회전 함수
 * @param {Array} arr - 대상 배열
 * @param {Number} d - 회전할 횟수
 * @param {Number} n - 배열의 크기
 */
function leftRotate(arr, d, n) {
    if (d === 0) return;
    
    // d가 n보다 클 경우를 대비해 모듈러 연산 수행
    d = d % n; 
    
    // 1단계: 앞부분(0 ~ d-1) 역전
    reverseArray(arr, 0, d - 1);
    
    // 2단계: 뒷부분(d ~ n-1) 역전
    reverseArray(arr, d, n - 1);
    
    // 3단계: 전체(0 ~ n-1) 역전
    reverseArray(arr, 0, n - 1);
}

// 실행 예시
let data = [1, 2, 3, 4, 5, 6, 7];
let n = data.length;
let d = 2;

leftRotate(data, d, n);
console.log(data); // 출력 결과: [3, 4, 5, 6, 7, 1, 2]

    3-1. 구현 시 주의사항

    회전 횟수 $d$가 배열의 크기 $n$보다 클 경우 불필요한 연산이 발생합니다. 따라서 반드시 d = d % n 연산을 통해 $d$의 크기를 최소화해야 합니다. 또한, 인덱스 접근 시 Array Index Out Of Bounds 오류를 방지하기 위해 $n$의 값을 정확히 파악하는 것이 중요합니다.

    [핵심 요약]
    1. 단순 접근의 한계: 임시 배열 사용은 메모리 낭비가 심하며, 하나씩 이동하는 방식은 시간이 오래 걸립니다.
    2. 역전 알고리즘: 배열을 구간별로 뒤집는(Reverse) 것만으로 회전을 구현하며, 시간 복잡도 $O(n)$, 공간 복잡도 $O(1)$의 최적 성능을 보장합니다.
    3. 실무 적용: 대용량 데이터 처리나 메모리 제약이 있는 임베디드 시스템에서 필수적으로 사용되는 기법입니다.
    반응형