C++ reverse·rotate·reverse_copy: 범위 뒤집기와 회전 알고리즘 사용법
이 글의 핵심
rotate는 가운데 반복자가 새 첫 원소가 되는 방식이라 왼쪽·오른쪽 회전 방향을 헷갈리기 쉽고, 회전 수가 크기를 넘으면 범위 오류가 납니다. 원본 수정 여부 혼동, 빈 범위 처리 같은 문제를 짚고, 경로 역순 처리와 순환 버퍼처럼 실무에서 쓰는 패턴까지 연결합니다.
들어가며
C++ STL의 역순 알고리즘은 컨테이너의 요소 순서를 뒤집거나 회전시키는 강력한 도구입니다. reverse, reverse_copy, rotate 등을 활용하면 배열, 벡터, 문자열 등의 순서를 효율적으로 조작할 수 있습니다.
이 알고리즘들을 직접 짜는 것은 어렵지 않지만, 표준 함수를 쓰면 경계 조건(빈 범위, 홀수 길이, 회전 수 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는 바이트 단위로 뒤집습니다. ASCII 문자열에서는 문제가 없지만, UTF-8 한글 문자열 "안녕"을 뒤집으면 각 글자를 이루는 3바이트의 순서까지 뒤집혀 깨진 문자가 나옵니다. 사용자에게 보이는 글자 단위로 뒤집어야 한다면 먼저 코드 포인트(std::u32string 등)로 변환해 뒤집거나, 결합 문자까지 고려해야 한다면 ICU 같은 유니코드 라이브러리가 필요합니다.
시간 복잡도: 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 <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를 하는 것보다 메모리 재할당이 없습니다.
시간 복잡도: O(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;
}다른 방법: 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());
}세 번 뒤집기가 회전이 되는 이유는 이렇습니다. 배열을 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 | 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 <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::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;
return 0;
}100만 개 정수 뒤집기는 메모리 대역폭에 묶인 단순 작업이라 최적화 빌드에서는 밀리초 단위 이하로 끝나는 것이 보통이고, 정확한 값은 CPU와 캐시에 따라 다릅니다. 이런 측정에서는 std::chrono::milliseconds로 자르면 0이 나오기 쉬우니 microseconds를 쓰고, 여러 번 반복한 평균을 보는 것이 좋습니다. 결과를 사용하지 않으면 컴파일러가 연산 자체를 없앨 수 있다는 점도 기억해야 합니다. 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: 알고리즘 문제 - 배열 회전 검사
문제: 배열 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;
}최적화: a + a 안에서 b 찾기
#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 << ",";
// 앞에 구분자를 붙여야 {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: 원본 수정 여부 혼동
증상: 원본이 의도치 않게 변경됨
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: 빈 범위 처리
증상: 빈 컨테이너에서 회전 수 계산이 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으로 나누기가 되어 대부분의 플랫폼에서 SIGFPE(Floating point exception)로 프로세스가 죽습니다. 또 v.size()는 부호 없는 size_t라서 k가 음수이면 k % v.size()에서 k가 거대한 양수로 변환되어 엉뚱한 값이 나옵니다. 음수 회전(반대 방향)을 받아야 한다면 ((k % n) + n) % n처럼 int끼리 계산해 정규화합니다.
마무리
C++ 역순 알고리즘은 배열, 벡터, 문자열 등의 순서를 효율적으로 조작할 수 있게 합니다.
핵심 요약
- reverse
- 원본을 in-place로 역순
- O(n) 시간, O(1) 공간
- reverse_copy
- 원본 유지, 복사본 역순
- O(n) 시간, O(n) 공간
- 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. 배열을 k칸 회전할 때 k가 배열 길이보다 크면 어떻게 되나요?
A. std::rotate(v.begin(), v.begin() + k, v.end())에서 v.begin() + k가 end()를 넘으면 유효하지 않은 반복자를 쓰게 되어 미정의 동작이 됩니다. 회전은 길이 n마다 원래 모양으로 돌아오므로 먼저 k %= v.size()로 줄인 뒤 호출해야 합니다. 빈 벡터에서는 나머지 연산 자체가 0으로 나누기가 되니, 크기가 0인 경우를 먼저 걸러야 합니다.
같이 보면 좋은 글
- C++ replace·replace_if·replace_copy: 값 치환과 transform 중 무엇을 쓸까
- C++ min·max·minmax_element와 std::clamp: 값 비교와 범위 제한
- 알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기