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 동작 원리:

다음은 mermaid 예제 코드입니다.

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)	복사하며 분할

C/C++ 예제 코드입니다.

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이 해당합니다. 교육용으로 “피벗보다 작은 값을 앞으로”만 보여주면 다음과 같습니다.

partition_step 함수의 구현 예제입니다.

#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로 개수를 구하면 됩니다.

---

분할 알고리즘

C/C++ 예제 코드입니다.

// 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: 순서

C/C++ 예제 코드입니다.

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

C/C++ 예제 코드입니다.

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: 성능

C/C++ 예제 코드입니다.

// 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: 반환값

C/C++ 예제 코드입니다.

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

활용 패턴

C/C++ 예제 코드입니다.

// 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: 조건부 삭제

removeIf 함수의 구현 예제입니다.

#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: 복사하며 분할합니다.

C/C++ 예제 코드입니다.

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++)

• 컴파일러 경고를 최대로 켜고(-Wall -Wextra 등 팀 합의), Sanitizer(ASan/UBSan)로 미정의 동작을 조기에 잡습니다.
• 최적화는 프로파일 결과를 본 뒤에 합니다.
• STL <algorithm> 사용 시 반복자 무효화·비교자 일관성을 함께 검토합니다.

---

실전 체크리스트 (C++)

• 경고·정적 분석에서 새로운 이슈가 없는가?
• 빈 범위·단일 원소 등 경계 조건을 테스트했는가?

---

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

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

---

관련 글

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

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「C++ Algorithm Partition | ‘분할 알고리즘’ 가이드」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

• 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
• 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
• 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
• 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「C++ Algorithm Partition | ‘분할 알고리즘’ 가이드」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

1. 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
2. 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
3. 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
4. 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
5. 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.