C++ Algorithm Partition | "분할 알고리즘" 가이드

Partition이란?

Partition (분할) 은 조건에 따라 요소를 두 그룹으로 나누는 STL 알고리즘입니다. 조건을 만족하는 요소를 앞으로, 그렇지 않은 요소를 뒤로 이동합니다.

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// 짝수를 앞으로
auto pivot = std::partition(v.begin(), v.end(), 
     [](int x) { return x % 2 == 0; });

// [2, 4, 6, 1, 3, 5] (순서는 보장 안 됨)

왜 필요한가?:

• 필터링: 조건별로 그룹화
• 성능: O(n) 시간 복잡도
• 유연성: 커스텀 조건 지원
• 전처리: 정렬 전 분할

// ❌ 수동 분할: 복잡
std::vector<int> evens, odds;
for (int x : v) {
    if (x % 2 == 0) {
        evens.push_back(x);
    } else {
        odds.push_back(x);
    }
}

// ✅ partition: 간결
auto pivot = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

Partition 동작 원리:

flowchart LR
    A[""(1, 2, 3, 4, 5, 6"]"] --> B[partition]
    B --> C[""(2, 4, 6, 1, 3, 5"]"]
    C --> D["true 그룹"]
    C --> E["false 그룹"]
    D -.-> |pivot| E

Partition 종류:

알고리즘	안정성	시간 복잡도	사용 시나리오
partition	❌ 불안정	O(n)	빠른 분할
stable_partition	✅ 안정	O(n log n)	순서 유지
partition_point	-	O(log n)	분할 지점 찾기
partition_copy	✅ 안정	O(n)	복사하며 분할

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: 빠름, 순서 보장 안 됨
auto pivot1 = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

// stable_partition: 느림, 순서 유지
auto pivot2 = std::stable_partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

기본 사용

#include <algorithm>

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// 분할
auto pivot = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

std::cout << "짝수: ";
for (auto it = v.begin(); it != pivot; ++it) {
    std::cout << *it << " ";
}

std::cout << "\n홀수: ";
for (auto it = pivot; it != v.end(); ++it) {
    std::cout << *it << " ";
}

실전 예시

예시 1: 필터링

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {1, -2, 3, -4, 5, -6, 7, -8};
    
    // 양수를 앞으로
    auto pivot = std::partition(numbers.begin(), numbers.end(),
         [](int x) { return x > 0; });
    
    std::cout << "양수: ";
    for (auto it = numbers.begin(); it != pivot; ++it) {
        std::cout << *it << " ";
    }
}

예시 2: stable_partition

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    
    // 안정 분할 (순서 유지)
    auto pivot = std::stable_partition(v.begin(), v.end(),
         [](int x) { return x % 2 == 0; });
    
    for (int x : v) {
        std::cout << x << " ";  // 2 4 6 1 3 5
    }
}

예시 3: partition_point

#include <algorithm>

int main() {
    std::vector<int> v = {2, 4, 6, 1, 3, 5};
    
    // 이미 분할된 범위
    std::partition(v.begin(), v.end(),  [](int x) { return x % 2 == 0; });
    
    // 분할 지점 찾기
    auto pivot = std::partition_point(v.begin(), v.end(),
         [](int x) { return x % 2 == 0; });
    
    std::cout << "분할 지점: " << std::distance(v.begin(), pivot) << std::endl;
}

예시 4: 3-way 분할

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 3으로 나눈 나머지로 분할
    auto pivot1 = std::partition(v.begin(), v.end(),
         [](int x) { return x % 3 == 0; });
    
    auto pivot2 = std::partition(pivot1, v.end(),
         [](int x) { return x % 3 == 1; });
    
    std::cout << "3의 배수: ";
    for (auto it = v.begin(); it != pivot1; ++it) {
        std::cout << *it << " ";  // 3 6 9
    }
    
    std::cout << "\n나머지 1: ";
    for (auto it = pivot1; it != pivot2; ++it) {
        std::cout << *it << " ";  // 1 4 7
    }
    
    std::cout << "\n나머지 2: ";
    for (auto it = pivot2; it != v.end(); ++it) {
        std::cout << *it << " ";  // 2 5 8
    }
}

---

partition vs stable_partition 심화

항목	partition	stable_partition
상대적 순서(같은 그룹 안)	보장하지 않음	유지
시간(일반적인 서술)	O(n)	최악 O(n log n), 추가 메모리 사용 가능
용도	퀵 정렬 피벗 단계, 순서 무관 필터	UI 목록, 타임스탬프 순 유지가 필요한 파이프라인

같은 그룹 안에서의 순서가 중요하지 않다면 partition이 더 싸고 빠릅니다. 원래 순서를 유지한 채 두 덩이로만 나누고 싶다면 stable_partition이 맞습니다. 대용량에서 안정 분할이 병목이면 두 벡터에 partition_copy 로 나누는 방식이 캐시·명확성 면에서 나을 수 있습니다.

---

partition_point: 전제와 이진 탐색

partition_point(first, last, pred)는 이미 다음을 만족할 때만 올바릅니다.

• [first, mid)의 모든 요소에 pred가 참
• [mid, last)의 모든 요소에 pred가 거짓

즉 단조(monotonic) 한 분할입니다. 전제가 깨지면 결과는 의미가 없거나 UB입니다. partition_point는 내부적으로 이진 탐색으로 “첫 번째 false” 위치를 O(log n)에 찾습니다.

std::vector<int> sorted = {1, 3, 5, 7, 9};
auto it = std::partition_point(sorted.begin(), sorted.end(),
    [](int x) { return x < 6; });
// it는 첫 6 이상 원소(7)를 가리킴

---

실전: 퀵 정렬 한 단계(스케치)

퀵 정렬의 핵심은 피벗을 기준으로 작은 그룹 | 큰 그룹으로 한 번에 나누는 것이며, 이에 std::partition이 해당합니다. 교육용으로 “피벗보다 작은 값을 앞으로”만 보여주면 다음과 같습니다.

#include <algorithm>
#include <vector>

void partition_step(std::vector<int>& a, int pivot) {
    std::partition(a.begin(), a.end(), [pivot](int x) { return x < pivot; });
}

완전한 퀵 정렬은 피벗을 구간 안에 확정시키고 양쪽 부분 구간을 재귀하는 등 추가 로직이 필요하고, 실무 정렬은 std::sort(인트로소트) 사용이 일반적입니다. 여기서 기억할 점은 partition 한 번이 선형이라는 것입니다.

---

partition과 이진 탐색의 조합

정렬된 범위에서 “임계값 이상이 처음 나오는 위치”는 lower_bound로 구합니다. 이는 정렬에 의해 자연스럽게 pred(*it)가 앞쪽에서만 참이 되는 단조 구조와 맞닿아 있습니다.

• 원본 순서를 유지하며 두 그룹으로만 나누기 → stable_partition 또는 partition_copy
• 이미 키 기준 정렬되어 있고 경계만 필요 → lower_bound / upper_bound / partition_point류가 적합

점수 순으로 정렬된 학생 목록에서 “합격선 이상 인원”은 lower_bound로 경계를 찾고 std::distance로 개수를 구하면 됩니다.

---

분할 알고리즘

// partition: 불안정
auto pivot = std::partition(begin, end, pred);

// stable_partition: 안정 (순서 유지)
auto pivot = std::stable_partition(begin, end, pred);

// partition_point: 분할 지점
auto pivot = std::partition_point(begin, end, pred);

// is_partitioned: 분할 확인
bool partitioned = std::is_partitioned(begin, end, pred);

// partition_copy: 복사하며 분할
std::partition_copy(begin, end, out1, out2, pred);

자주 발생하는 문제

문제 1: 순서

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: 순서 보장 안 됨
std::partition(v.begin(), v.end(),  [](int x) { return x % 2 == 0; });
// 가능: [2, 6, 4, 1, 3, 5]

// stable_partition: 순서 유지
std::stable_partition(v.begin(), v.end(),  [](int x) { return x % 2 == 0; });
// 보장: [2, 4, 6, 1, 3, 5]

문제 2: partition_point

std::vector<int> v = {1, 2, 3, 4, 5};

// ❌ 분할 안 됨
// auto pivot = std::partition_point(v.begin(), v.end(), pred);  // 정의되지 않은 동작

// ✅ 분할 후
std::partition(v.begin(), v.end(), pred);
auto pivot = std::partition_point(v.begin(), v.end(), pred);

문제 3: 성능

// partition: O(n), 불안정
std::partition(v.begin(), v.end(), pred);

// stable_partition: O(n log n), 안정
std::stable_partition(v.begin(), v.end(), pred);

// 순서 중요하지 않으면 partition 사용

문제 4: 반환값

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition 반환: 분할 지점 반복자
auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

활용 패턴

// 1. 필터링
auto pivot = std::partition(v.begin(), v.end(), pred);

// 2. 안정 분할
auto pivot = std::stable_partition(v.begin(), v.end(), pred);

// 3. 분할 지점
auto pivot = std::partition_point(v.begin(), v.end(), pred);

// 4. 복사 분할
std::partition_copy(v.begin(), v.end(), out1, out2, pred);

실무 패턴

패턴 1: 우선순위 처리

#include <algorithm>
#include <vector>

struct Task {
    std::string name;
    int priority;
    bool urgent;
};

void processTasks(std::vector<Task>& tasks) {
    // 긴급 작업을 앞으로
    auto pivot = std::stable_partition(tasks.begin(), tasks.end(),
         [](const Task& t) { return t.urgent; });
    
    // 긴급 작업 처리
    for (auto it = tasks.begin(); it != pivot; ++it) {
        std::cout << "긴급: " << it->name << '\n';
    }
    
    // 일반 작업 처리
    for (auto it = pivot; it != tasks.end(); ++it) {
        std::cout << "일반: " << it->name << '\n';
    }
}

패턴 2: 조건부 삭제

#include <algorithm>
#include <vector>

template<typename T, typename Pred>
void removeIf(std::vector<T>& vec, Pred pred) {
    // 삭제할 요소를 뒤로
    auto pivot = std::partition(vec.begin(), vec.end(),
        [&pred](const T& item) { return !pred(item); });
    
    // 뒤쪽 삭제
    vec.erase(pivot, vec.end());
}

// 사용
std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
removeIf(numbers,  [](int x) { return x % 2 == 0; });
// 결과: {1, 3, 5}

패턴 3: 그룹별 처리

#include <algorithm>
#include <vector>
#include <string>

struct User {
    std::string name;
    bool premium;
    int age;
};

void processUsers(std::vector<User>& users) {
    // 프리미엄 사용자를 앞으로
    auto pivot = std::stable_partition(users.begin(), users.end(),
         [](const User& u) { return u.premium; });
    
    // 프리미엄 사용자 처리
    std::cout << "프리미엄 사용자:\n";
    for (auto it = users.begin(); it != pivot; ++it) {
        std::cout << "- " << it->name << '\n';
    }
    
    // 일반 사용자 처리
    std::cout << "일반 사용자:\n";
    for (auto it = pivot; it != users.end(); ++it) {
        std::cout << "- " << it->name << '\n';
    }
}

FAQ

Q1: partition은 무엇인가요?

A: 조건에 따라 요소를 두 그룹으로 나누는 알고리즘입니다.

auto pivot = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

Q2: 안정성은?

A:

• partition: 불안정 (순서 보장 안 됨)
• stable_partition: 안정 (순서 유지)

// partition: [2, 6, 4, 1, 3, 5] (가능)
// stable_partition: [2, 4, 6, 1, 3, 5] (보장)

Q3: 반환값은?

A: 분할 지점 반복자를 반환합니다.

auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

Q4: 성능은?

A:

• partition: O(n)
• stable_partition: O(n log n)

// 빠름
std::partition(v.begin(), v.end(), pred);

// 느림 (순서 유지)
std::stable_partition(v.begin(), v.end(), pred);

Q5: partition_point는?

A: 이미 분할된 범위에서 분할 지점을 찾습니다. O(log n) 시간 복잡도입니다.

// 분할 후
std::partition(v.begin(), v.end(), pred);

// 분할 지점 찾기
auto pivot = std::partition_point(v.begin(), v.end(), pred);

Q6: partition_copy는?

A: 복사하며 분할합니다.

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> evens, odds;

std::partition_copy(v.begin(), v.end(),
    std::back_inserter(evens),
    std::back_inserter(odds),
     [](int x) { return x % 2 == 0; });

Q7: 분할 확인은?

A: std::is_partitioned 를 사용합니다.

if (std::is_partitioned(v.begin(), v.end(), pred)) {
    std::cout << "분할됨\n";
}

Q8: Partition 학습 리소스는?

A:

• “Effective STL” by Scott Meyers
• “C++ Primer” by Stanley Lippman
• cppreference.com - partition

관련 글: algorithm, sort, remove_if.

한 줄 요약: Partition은 조건에 따라 요소를 두 그룹으로 나누는 STL 알고리즘입니다.

---

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

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

• C++ Algorithm Sort | “정렬 알고리즘” 가이드
• C++ 알고리즘 | “STL algorithm” 핵심 정리
• C++ Algorithm Search | “검색 알고리즘” 가이드

실전 팁

실무에서 바로 적용할 수 있는 팁입니다.

디버깅 팁

• 문제가 발생하면 먼저 컴파일러 경고를 확인하세요
• 간단한 테스트 케이스로 문제를 재현하세요

성능 팁

• 프로파일링 없이 최적화하지 마세요
• 측정 가능한 지표를 먼저 설정하세요

코드 리뷰 팁

• 코드 리뷰에서 자주 지적받는 부분을 미리 체크하세요
• 팀의 코딩 컨벤션을 따르세요

---

실전 체크리스트

실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.

코드 작성 전

• 이 기법이 현재 문제를 해결하는 최선의 방법인가?
• 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
• 성능 요구사항을 만족하는가?

코드 작성 중

• 컴파일러 경고를 모두 해결했는가?
• 엣지 케이스를 고려했는가?
• 에러 처리가 적절한가?

코드 리뷰 시

• 코드의 의도가 명확한가?
• 테스트 케이스가 충분한가?
• 문서화가 되어 있는가?

이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.

---

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

C++, algorithm, partition, STL, sort 등으로 검색하시면 이 글이 도움이 됩니다.

---

관련 글

• C++ 알고리즘 |
• C++ Algorithm Sort |
• C++ STL 고급 알고리즘 | partition·merge·집합 연산·힙으로 데이터 처리 마스터
• C++ STL 알고리즘 기초 완벽 가이드 | sort·find
• C++ STL 알고리즘 완벽 가이드 | sort·transform·accumulate [#54-1]