C++ Algorithm Reverse | reverse·rotate·reverse_copy 완벽 정리

들어가며

C++ STL의 역순 알고리즘은 컨테이너의 요소 순서를 뒤집거나 회전시키는 강력한 도구입니다. reverse, reverse_copy, rotate 등을 활용하면 배열, 벡터, 문자열 등의 순서를 효율적으로 조작할 수 있습니다.

이 글을 읽으면

• reverse, reverse_copy로 원본 수정 여부를 제어합니다
• rotate로 배열 회전 문제를 O(n)에 해결합니다
• 팰린드롬, 문자열 역순, 배열 회전 등 실무 패턴을 익힙니다
• 알고리즘 문제에서 자주 쓰이는 트릭을 이해합니다

---

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

기본 알고리즘

주요 알고리즘 목록

알고리즘	원본 수정	시간 복잡도	용도
reverse	O	O(n)	범위 역순
reverse_copy	X	O(n)	복사본 역순
rotate	O	O(n)	범위 회전
rotate_copy	X	O(n)	복사본 회전

---

실전 구현

1) 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;
}

문자열 역순

#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;
}

시간 복잡도: O(n)
공간 복잡도: O(1)

2) std::reverse_copy - 복사본 역순

시그니처:

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

기본 사용

#include <algorithm>
#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;
}

배열로 복사

#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;
}

---

3) 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;
}

시간 복잡도: O(n)
공간 복잡도: O(1)

고급 활용

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;
}

2) 배열 회전 (LeetCode 189)

문제: 배열을 오른으로 k칸 회전

#include <algorithm>
#include <vector>
#include <iostream>
void rotateArray(std::vector<int>& arr, int k) {
    int n = arr.size();
    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;
}

다른 방법: 3번 reverse

void rotateArray(std::vector<int>& arr, int k) {
    int n = arr.size();
    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());
}

3) 단어 순서 뒤집기 (LeetCode 151)

#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>
std::string reverseWords(const std::string& sentence) {
    std::istringstream iss(sentence);
    std::string word;
    std::string result;
    
    while (iss >> word) {
        std::reverse(word.begin(), word.end());
        if (!result.empty()) result += " ";
        result += word;
    }
    
    return result;
}
int main() {
    std::string sentence = "hello world";
    std::cout << reverseWords(sentence) << std::endl;  // olleh dlrow
    
    return 0;
}

---

성능 비교

알고리즘 비교

알고리즘	원본 수정	시간 복잡도	공간 복잡도	용도
reverse	O	O(n)	O(1)	In-place 역순
reverse_copy	X	O(n)	O(n)	복사본 역순
rotate	O	O(n)	O(1)	In-place 회전
rotate_copy	X	O(n)	O(n)	복사본 회전

벤치마크

테스트: 100만 개 정수 역순

#include <algorithm>
#include <vector>
#include <chrono>
#include <iostream>
int main() {
    std::vector<int> v(1000000);
    std::iota(v.begin(), v.end(), 1);
    
    auto start = std::chrono::high_resolution_clock::now();
    std::reverse(v.begin(), v.end());
    auto end = std::chrono::high_resolution_clock::now();
    
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "reverse: " << duration << "ms" << std::endl;
    // 약 2ms
    
    return 0;
}

---

실무 사례

사례 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: 알고리즘 문제 - 배열 회전 검사

문제: 배열 A가 배열 B의 회전인지 확인

#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;
}

최적화: 문자열 연결로 O(n) 검사

#include <string>
#include <sstream>
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 << ",";
    
    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;
}

사례 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;
}

---

트러블슈팅

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

증상: 원본이 의도치 않게 변경됨

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 방향 혼동

증상: 회전 방향이 예상과 다름

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());
// {4, 5, 1, 2, 3}

팁: middle 위치가 새로운 첫 요소

문제 3: rotate 범위 초과

증상: 잘못된 반복자 범위로 인한 undefined behavior

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: 빈 범위 처리

증상: 빈 컨테이너에 대한 예외 처리 누락

std::vector<int> v;
// ❌ 빈 범위 체크 없음
std::reverse(v.begin(), v.end());  // 안전하지만 불필요
// ✅ 사전 체크
if (!v.empty()) {
    std::reverse(v.begin(), v.end());
}

---

마무리

C++ 역순 알고리즘은 배열, 벡터, 문자열 등의 순서를 효율적으로 조작할 수 있게 합니다.

핵심 요약

1. reverse
   • 원본을 in-place로 역순
   • O(n) 시간, O(1) 공간
2. reverse_copy
   • 원본 유지, 복사본 역순
   • O(n) 시간, O(n) 공간
3. rotate
   • 범위를 회전 (왼쪽/오른쪽)
   • O(n) 시간, O(1) 공간

선택 가이드

상황	알고리즘
원본 역순	reverse
원본 유지	reverse_copy
배열 회전	rotate
팰린드롬 검사	reverse + 비교

코드 예제 치트시트

// 전체 역순
std::reverse(v.begin(), v.end());
// 부분 역순
std::reverse(v.begin() + 1, v.begin() + 4);
// 복사본 역순
std::reverse_copy(src.begin(), src.end(), std::back_inserter(dst));
// 왼쪽 회전
std::rotate(v.begin(), v.begin() + k, v.end());
// 오른쪽 회전
std::rotate(v.begin(), v.end() - k, v.end());

다음 단계

• 정렬 알고리즘: C++ Algorithm Sort
• 교체 알고리즘: C++ Algorithm Replace
• 카운트 알고리즘: C++ Algorithm Count

참고 자료

• cppreference: https://en.cppreference.com/w/cpp/algorithm
• “Effective STL” - Scott Meyers
• LeetCode: 189 (Rotate Array), 151 (Reverse Words in a String) 한 줄 정리: 역순과 회전은 reverse, rotate로 O(n) in-place 처리하며, 원본 유지가 필요하면 _copy 버전을 사용한다.

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. C++ reverse, reverse_copy, rotate로 순서 뒤집기·회전. 부분 역순·문자열·배열 회전 패턴을 실전 예제와 함께 정리합니다. C++·알고리즘·reverse 중심으로 설명합니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ Algorithm Replace | ‘치환 알고리즘’ 가이드
• C++ Algorithm MinMax | ‘최소/최대 알고리즘’ 가이드
• 알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기

---

이 글에서 다루는 키워드 (관련 검색어)

C++, 알고리즘, reverse, rotate, STL 등으로 검색하시면 이 글이 도움이 됩니다.