C++ reverse·rotate·reverse_copy: 범위 뒤집기와 회전 알고리즘 사용법

들어가며

<algorithm>의 reverse, reverse_copy, rotate, rotate_copy는 범위의 원소 순서를 뒤집거나 회전시키는 알고리즘입니다. 배열, 벡터, 문자열처럼 반복자로 다룰 수 있는 범위라면 어디에나 쓸 수 있습니다.

이 알고리즘들을 직접 짜는 것은 어렵지 않지만, 표준 함수를 쓰면 경계 조건(빈 범위, 홀수 길이, 회전 수 0)을 모두 올바르게 처리한 구현을 얻고, 코드를 읽는 사람이 루프를 따라가지 않아도 의도를 바로 알 수 있습니다. 특히 rotate는 “앞부분을 떼어 뒤에 붙인다”는 흔한 작업을 추가 메모리 없이 해 주는데, 직접 구현하면 임시 배열을 쓰거나 인덱스 계산에서 실수하기 쉽습니다.

---

기본 알고리즘

주요 알고리즘 목록

알고리즘	원본 수정	시간 복잡도	필요한 반복자	용도
reverse	O	O(n)	양방향	범위 역순
reverse_copy	X	O(n)	양방향(입력), 출력	복사본 역순
rotate	O	O(n)	전진	범위 회전
rotate_copy	X	O(n)	전진(입력), 출력	복사본 회전

---

실전 구현

std::reverse - 범위 역순

template<class BidirIt>
void reverse(BidirIt first, BidirIt last);

전체 역순

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    std::reverse(v.begin(), v.end());
    
    for (int x : v) {
        std::cout << x << " ";  // 5 4 3 2 1
    }
    std::cout << std::endl;
    
    return 0;
}

부분 역순

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 인덱스 1~3 역순
    std::reverse(v.begin() + 1, v.begin() + 4);
    
    for (int x : v) {
        std::cout << x << " ";  // 1 4 3 2 5
    }

    return 0;
}

모든 STL 알고리즘처럼 범위는 반열린 구간 [first, last)입니다. v.begin() + 1부터 v.begin() + 4 직전까지, 즉 인덱스 1, 2, 3이 뒤집힙니다. “인덱스 1~3”을 뒤집으려고 v.begin() + 3을 끝으로 주면 인덱스 1, 2만 뒤집히는 off-by-one 실수가 흔합니다. reverse는 양 끝에서 안쪽으로 오며 std::iter_swap을 n/2번 호출하므로 양방향 반복자(BidirectionalIterator)가 필요하고, 그래서 std::forward_list에는 쓸 수 없습니다(대신 forward_list::reverse() 멤버 함수가 있습니다). std::list도 reverse가 가능하지만 노드를 재연결하는 list::reverse() 멤버 함수가 원소를 교환하지 않아 더 효율적입니다.

문자열 역순

#include <algorithm>
#include <string>
#include <iostream>
int main() {
    std::string str = "hello";
    
    std::reverse(str.begin(), str.end());
    
    std::cout << str << std::endl;  // olleh

    return 0;
}

std::string에 reverse를 적용하면 바이트(char) 단위로 뒤집힙니다. ASCII 문자열에서는 문제가 없지만, UTF-8 한글 문자열 "안녕"을 뒤집으면 각 글자를 이루는 3바이트의 순서까지 뒤집혀 깨진 문자가 나옵니다. 사용자에게 보이는 글자 단위로 뒤집어야 한다면 먼저 코드 포인트(std::u32string 등)로 변환해 뒤집거나, 결합 문자까지 고려해야 한다면 ICU 같은 유니코드 라이브러리가 필요합니다. reverse의 시간 복잡도는 O(n)이고 추가 공간은 O(1)입니다.

---

std::reverse_copy - 복사본 역순

template<class BidirIt, class OutputIt>
OutputIt reverse_copy(BidirIt first, BidirIt last, OutputIt d_first);

기본 사용

#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst;
    
    std::reverse_copy(src.begin(), src.end(), std::back_inserter(dst));
    
    std::cout << "원본: ";
    for (int x : src) {
        std::cout << x << " ";  // 1 2 3 4 5
    }
    
    std::cout << "\n역순: ";
    for (int x : dst) {
        std::cout << x << " ";  // 5 4 3 2 1
    }

    return 0;
}

std::back_inserter(dst)는 쓰기 연산을 dst.push_back()으로 바꿔 주는 출력 반복자입니다. 이것 없이 빈 벡터의 dst.begin()을 넘기면 존재하지 않는 원소에 쓰게 되어 정의되지 않은 동작이 되는데, 컴파일은 되기 때문에 자주 나오는 실수입니다. 크기를 미리 알면 std::vector<int> dst(src.size());로 공간을 잡고 dst.begin()을 넘기는 편이 push_back 반복보다 빠릅니다. 단순히 역순 사본이 필요하다면 std::vector<int> dst(src.rbegin(), src.rend()); 한 줄로도 됩니다. 출력 대상이 고정 크기 배열이어도 크기만 충분하면 그대로 쓸 수 있습니다.

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    int dst[5];
    
    std::reverse_copy(src.begin(), src.end(), dst);
    
    for (int x : dst) {
        std::cout << x << " ";  // 5 4 3 2 1
    }
    
    return 0;
}

---

std::rotate - 범위 회전

template<class ForwardIt>
ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last);

왼쪽 회전

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // [begin, middle) → 끝으로, [middle, end) → 앞으로
    std::rotate(v.begin(), v.begin() + 2, v.end());
    
    for (int x : v) {
        std::cout << x << " ";  // 3 4 5 1 2
    }
    
    return 0;
}

오른쪽 회전

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 오른쪽으로 2칸
    std::rotate(v.begin(), v.end() - 2, v.end());
    
    for (int x : v) {
        std::cout << x << " ";  // 4 5 1 2 3
    }
    
    return 0;
}

rotate 반환값

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 반환값: 회전 후 원래 첫 요소의 위치
    auto newFirst = std::rotate(v.begin(), v.begin() + 2, v.end());
    
    std::cout << "원래 첫 요소의 새 위치: " << *newFirst << std::endl;  // 1

    return 0;
}

rotate의 방향이 헷갈릴 때는 “middle이 가리키던 원소가 맨 앞으로 온다”만 기억하면 됩니다. v.begin() + 2는 값 3을 가리키므로 결과는 3으로 시작하고(왼쪽 2칸), v.end() - 2는 값 4를 가리키므로 4로 시작합니다(오른쪽 2칸). 반환값은 반대로 “원래 맨 앞 원소가 어디로 갔는가”로, 회전된 두 부분의 경계를 알려 줍니다. 이 값은 rotate를 부분 범위에 적용해 원소 하나를 다른 위치로 옮기는 “slide” 관용구에서 유용합니다. 예를 들어 std::rotate(v.begin() + i, v.begin() + i + 1, v.begin() + j + 1)은 인덱스 i의 원소를 j로 옮기고 사이 원소들을 한 칸씩 당깁니다. 벡터에서 erase 후 insert를 하면 i 뒤쪽 원소 전체가 앞으로 한 번, j 뒤쪽 원소 전체가 다시 뒤로 한 번 이동하지만, rotate는 i부터 j까지만 움직입니다. rotate의 시간 복잡도는 O(n)(교환 최대 n번)이고 추가 공간은 O(1)입니다.

---

고급 활용

팰린드롬 검사

#include <algorithm>
#include <string>
#include <iostream>
bool isPalindrome(const std::string& str) {
    std::string reversed = str;
    std::reverse(reversed.begin(), reversed.end());
    
    return str == reversed;
}
int main() {
    std::cout << std::boolalpha;
    std::cout << isPalindrome("racecar") << std::endl;  // true
    std::cout << isPalindrome("hello") << std::endl;    // false
    std::cout << isPalindrome("level") << std::endl;    // true

    return 0;
}

이 방식은 이해하기 쉽지만 문자열 전체를 복사합니다. 복사 없이 확인하려면 앞쪽 절반과 뒤에서부터 읽은 절반을 비교하면 됩니다. std::equal(str.begin(), str.begin() + str.size() / 2, str.rbegin())은 추가 메모리 없이 절반만 비교하고, 다른 글자를 만나는 즉시 멈춥니다. 대소문자나 공백을 무시하는 “A man, a plan, a canal: Panama” 같은 문제(LeetCode 125)는 양 끝 투 포인터로 영숫자가 아닌 문자를 건너뛰며 비교하는 쪽이 자연스럽습니다.

배열 회전 (LeetCode 189)

배열을 오른쪽으로 k칸 회전하는 문제입니다.

#include <algorithm>
#include <vector>
#include <iostream>
void rotateArray(std::vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return;  // 빈 배열이면 % 연산이 0으로 나누기가 됨
    k = k % n;  // k가 n보다 클 수 있음

    std::rotate(arr.begin(), arr.end() - k, arr.end());
}
int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7};
    
    rotateArray(arr, 3);
    
    for (int x : arr) {
        std::cout << x << " ";  // 5 6 7 1 2 3 4
    }
    
    return 0;
}

세 번 뒤집어서 풀 수도 있습니다.

void rotateArray(std::vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return;
    k = k % n;
    
    // 1. 전체 역순
    std::reverse(arr.begin(), arr.end());
    
    // 2. 앞 k개 역순
    std::reverse(arr.begin(), arr.begin() + k);
    
    // 3. 뒤 n-k개 역순
    std::reverse(arr.begin() + k, arr.end());
}

세 번 뒤집기가 회전이 되는 이유는 이렇습니다. 배열을 A(앞 n-k개)와 B(뒤 k개)로 나누면 원하는 결과는 BA입니다. 전체를 뒤집으면 reverse(B) reverse(A)가 되고, 각 부분을 다시 뒤집으면 B A가 됩니다. 원소 교환 횟수가 약 n번으로 고정되어 있고 구현이 단순해서 면접에서 자주 묻는 풀이입니다. std::rotate도 결과는 같지만, 구현은 반복자 종류에 따라 다른 알고리즘을 고릅니다. 임의 접근 반복자에서는 GCD 기반 순환 교환을 쓰기도 하는데, 캐시 효율은 오히려 세 번 뒤집기가 나은 경우도 있습니다. 코딩 테스트에서는 어느 쪽이든 충분하고, 실무 코드에서는 의도가 드러나는 std::rotate가 읽기 좋습니다.

단어 순서 뒤집기 (LeetCode 151)

#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
std::string reverseWords(const std::string& sentence) {
    std::istringstream iss(sentence);
    std::vector<std::string> words;
    std::string word;

    while (iss >> word) {          // 연속 공백·앞뒤 공백은 자동으로 무시됨
        words.push_back(word);
    }
    std::reverse(words.begin(), words.end());  // 단어의 순서를 뒤집음

    std::string result;
    for (const auto& w : words) {
        if (!result.empty()) result += " ";
        result += w;
    }
    return result;
}
int main() {
    std::string sentence = "  the sky  is blue ";
    std::cout << reverseWords(sentence) << std::endl;  // blue is sky the

    return 0;
}

LeetCode 151은 단어의 순서를 뒤집는 문제이고, 각 단어의 글자를 뒤집는 문제(“hello world” → “olleh dlrow”)는 557번입니다. 557번이라면 위 루프에서 words에 넣기 전에 std::reverse(word.begin(), word.end())를 하고 순서는 그대로 두면 됩니다. istringstream과 >>를 쓰면 여러 칸의 공백과 앞뒤 공백이 자동으로 정리되므로 151번의 까다로운 조건이 한 번에 해결됩니다. 추가 메모리 없이 풀어야 한다면 “문자열 전체를 뒤집은 뒤 각 단어를 다시 뒤집는” 방식을 쓰는데, 앞의 세 번 뒤집기 회전과 같은 원리입니다.

---

성능 측정

reverse와 rotate는 추가 메모리 없이 제자리에서 동작하고, _copy 버전은 결과를 담을 n개 크기의 출력 공간이 필요합니다. 실제 실행 시간을 확인하고 싶다면 다음처럼 측정할 수 있습니다.

#include <algorithm>
#include <numeric>   // std::iota
#include <vector>
#include <chrono>
#include <iostream>
int main() {
    std::vector<int> v(1000000);
    std::iota(v.begin(), v.end(), 1);
    
    auto start = std::chrono::steady_clock::now();
    std::reverse(v.begin(), v.end());
    auto end = std::chrono::steady_clock::now();
    
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    std::cout << "reverse: " << duration << "us, v[0] = " << v[0] << std::endl;  // 결과를 사용

    return 0;
}

100만 개 정수 뒤집기는 메모리 대역폭에 묶인 단순 작업이라 최적화 빌드에서는 밀리초 단위 이하로 끝나는 것이 보통이고, 정확한 값은 CPU와 캐시에 따라 다릅니다. 그래서 milliseconds로 자르면 0이 나오기 쉬우므로 위 코드는 microseconds를 쓰고, 한 번이 아니라 여러 번 반복한 평균을 보는 것이 좋습니다. 결과를 사용하지 않으면 컴파일러가 연산 자체를 없앨 수 있으므로 v[0]을 출력했습니다. reverse와 rotate의 비용은 결국 원소 교환 횟수와 메모리 접근 패턴이 결정하므로, 원소가 큰 구조체라면 교환 대신 인덱스나 포인터 배열을 뒤집는 편이 훨씬 빠를 수 있습니다.

---

실무 사례

사례 1: 문자열 처리 - 경로 역순

#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
std::string reversePath(const std::string& path) {
    std::vector<std::string> parts;
    std::istringstream iss(path);
    std::string part;
    
    while (std::getline(iss, part, '/')) {
        if (!part.empty()) {
            parts.push_back(part);
        }
    }
    
    std::reverse(parts.begin(), parts.end());
    
    std::string result;
    for (size_t i = 0; i < parts.size(); ++i) {
        if (i > 0) result += "/";
        result += parts[i];
    }
    
    return result;
}
int main() {
    std::string path = "/home/user/documents/file.txt";
    std::cout << reversePath(path) << std::endl;
    // file.txt/documents/user/home
    
    return 0;
}

사례 2: 알고리즘 문제 - 배열 회전 검사

배열 b가 배열 a를 회전한 것인지 확인하는 문제입니다.

#include <algorithm>
#include <vector>
#include <iostream>
bool isRotation(const std::vector<int>& a, const std::vector<int>& b) {
    if (a.size() != b.size()) return false;
    
    for (size_t k = 0; k < a.size(); ++k) {
        std::vector<int> rotated = a;
        std::rotate(rotated.begin(), rotated.begin() + k, rotated.end());
        
        if (rotated == b) return true;
    }
    
    return false;
}
int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {3, 4, 5, 1, 2};
    
    std::cout << std::boolalpha;
    std::cout << isRotation(a, b) << std::endl;  // true
    
    return 0;
}

a를 두 번 이어 붙인 것 안에서 b를 찾으면 모든 회전을 만들지 않아도 됩니다.

#include <sstream>
#include <string>
#include <vector>
bool isRotation(const std::vector<int>& a, const std::vector<int>& b) {
    if (a.size() != b.size()) return false;

    std::ostringstream oss_a, oss_b;
    for (int x : a) oss_a << x << ",";
    for (int x : b) oss_b << x << ",";

    // 앞에 구분자를 붙여야 {1,23}과 {1,2}처럼 숫자 경계가 어긋난 오탐을 막을 수 있음
    std::string str_a = "," + oss_a.str() + oss_a.str();
    std::string str_b = "," + oss_b.str();

    return str_a.find(str_b) != std::string::npos;
}

첫 번째 방법은 가능한 회전 n가지를 모두 만들어 비교하므로 O(n²)입니다. 두 번째 방법은 “b가 a의 회전이라면 a를 두 번 이어 붙인 것 안에 반드시 b가 들어 있다”는 성질을 이용합니다. 숫자를 문자열로 바꿀 때는 구분자 처리가 중요합니다. 구분자를 원소 뒤에만 붙이면 a = {11, 2}의 "11,2,11,2," 안에 b = {1, 2}의 "1,2,"가 부분 문자열로 들어 있어 틀린 true가 나옵니다. 위 코드는 맨 앞에도 구분자를 붙여 모든 원소가 , 사이에 끼도록 만들었습니다. 또 std::string::find는 최악의 경우 O(n·m)일 수 있어, 엄밀하게 O(n)이 필요하면 KMP나 std::boyer_moore_searcher(C++17)를 씁니다. 문자열로 바꾸지 않고 정수 벡터에 직접 KMP를 적용하는 것이 가장 깔끔합니다.

사례 3: 데이터 처리 - 순환 버퍼

#include <algorithm>
#include <vector>
#include <iostream>
class CircularBuffer {
private:
    std::vector<int> buffer;
    size_t head = 0;
    
public:
    CircularBuffer(size_t size) : buffer(size, 0) {}
    
    void push(int value) {
        buffer[head] = value;
        head = (head + 1) % buffer.size();
    }
    
    std::vector<int> getOrdered() const {
        std::vector<int> result = buffer;
        std::rotate(result.begin(), result.begin() + head, result.end());
        return result;
    }
};
int main() {
    CircularBuffer cb(5);
    
    for (int i = 1; i <= 7; ++i) {
        cb.push(i);
    }
    
    auto ordered = cb.getOrdered();
    for (int x : ordered) {
        std::cout << x << " ";  // 3 4 5 6 7
    }

    return 0;
}

head는 “다음에 쓸 위치”이자 버퍼가 가득 찬 뒤에는 “가장 오래된 원소의 위치”이므로, head를 기준으로 회전하면 오래된 순서로 정렬됩니다. 이 구현은 버퍼가 아직 다 차지 않았을 때 초기값 0이 결과에 섞인다는 한계가 있습니다. 실제로 쓰려면 저장된 개수(count)를 따로 세어 count < size일 때는 앞의 count개만 돌려주도록 해야 합니다. 또 getOrdered()를 호출할 때마다 전체 복사가 일어나므로, 자주 순회한다면 복사 없이 head부터 인덱스를 % size로 돌며 읽는 반복자를 제공하는 편이 낫습니다.

---

트러블슈팅

문제 1: 원본 수정 여부 혼동

reverse는 원본을 바꿉니다. 원본을 유지해야 한다면 reverse_copy를 씁니다.

std::vector<int> v = {1, 2, 3, 4, 5};
// 원본 수정
std::reverse(v.begin(), v.end());
// v는 이제 {5, 4, 3, 2, 1}
// 원본 유지
std::vector<int> dst;
std::reverse_copy(v.begin(), v.end(), std::back_inserter(dst));
// v는 그대로, dst는 {5, 4, 3, 2, 1}

문제 2: rotate 방향 혼동

middle이 가리키던 원소가 새 첫 원소가 된다는 것만 기억하면 방향을 헷갈리지 않습니다.

std::vector<int> v = {1, 2, 3, 4, 5};
// 왼쪽 회전 (middle → 앞으로)
std::rotate(v.begin(), v.begin() + 2, v.end());
// {3, 4, 5, 1, 2}
// 오른쪽 회전 (end - k → 앞으로)
std::rotate(v.begin(), v.end() - 2, v.end());
// 위 결과 {3, 4, 5, 1, 2}에 다시 적용하면 {1, 2, 3, 4, 5}

문제 3: rotate 범위 초과

middle이 [first, last] 밖을 가리키면 미정의 동작입니다. 회전 수가 크기보다 클 수 있다면 먼저 나머지 연산으로 줄입니다.

std::vector<int> v = {1, 2, 3, 4, 5};
int k = 7;  // 배열 크기보다 큼
// 범위 초과
std::rotate(v.begin(), v.begin() + k, v.end());  // UB!
// 모듈로 연산
k = k % v.size();
std::rotate(v.begin(), v.begin() + k, v.end());

문제 4: 빈 범위 처리

알고리즘 자체는 빈 범위에서 안전하지만, 회전 수를 계산하는 나머지 연산이 0으로 나누기가 될 수 있습니다.

std::vector<int> v;
// reverse·rotate 자체는 빈 범위에서도 안전 (아무것도 하지 않음)
std::reverse(v.begin(), v.end());
// 위험한 것은 회전 수 계산
int k = 3;
// k = k % v.size();  // v.size()가 0이면 정의되지 않은 동작 (0으로 나누기)
// 크기를 먼저 확인
if (!v.empty()) {
    k = k % v.size();
    std::rotate(v.begin(), v.begin() + k, v.end());
}

표준 알고리즘은 빈 범위(first == last)를 정상적인 입력으로 처리하므로 reverse나 rotate 앞에 empty() 검사를 둘 필요는 없습니다. 문제가 되는 것은 그 주변의 계산입니다. k % v.size()에서 크기가 0이면 0으로 나누기가 되어 미정의 동작이고, x86 Linux에서는 SIGFPE(Floating point exception)로 프로세스가 죽습니다. 또 v.size()는 부호 없는 size_t라서 k가 음수이면 k % v.size()에서 k가 거대한 양수로 변환되어 엉뚱한 값이 나옵니다. 음수 회전(반대 방향)을 받아야 한다면 ((k % n) + n) % n처럼 int끼리 계산해 정규화합니다.

---

참고 자료

• cppreference: algorithm 라이브러리
• LeetCode 189 (Rotate Array), 151 (Reverse Words in a String), 557 (Reverse Words in a String III)

---

같이 보면 좋은 글

• C++ replace·replace_if·replace_copy: 값 치환과 transform 중 무엇을 쓸까
• C++ count·count_if와 all_of·any_of·none_of로 조건 집계하기
• C++ min·max·minmax_element와 std::clamp: 값 비교와 범위 제한
• 알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기
• C++ set_union·set_intersection·set_difference: 정렬된 범위의 집합 연산