C++ Algorithm Search | "검색 알고리즘" 가이드

검색 알고리즘이란?

검색 알고리즘 (Search Algorithm) 은 컨테이너에서 특정 값이나 조건을 만족하는 요소를 찾는 STL 알고리즘입니다.

#include <algorithm>
#include <vector>

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

// 선형 검색
auto it = std::find(v.begin(), v.end(), 3);

// 이진 검색 (정렬 필요)
bool found = std::binary_search(v.begin(), v.end(), 3);

왜 필요한가?:

• 효율성: 최적화된 검색 알고리즘
• 간결성: 복잡한 로직 간소화
• 안전성: 범위 체크 자동
• 유연성: 다양한 검색 방법 지원

// ❌ 수동 검색: 복잡
bool found = false;
for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] == 3) {
        found = true;
        break;
    }
}

// ✅ find: 간결
auto it = std::find(v.begin(), v.end(), 3);
bool found = (it != v.end());

검색 알고리즘 종류:

알고리즘	시간 복잡도	정렬 필요	설명
find	O(n)	❌	값 검색
find_if	O(n)	❌	조건 검색
binary_search	O(log n)	✅	이진 검색 (존재 여부)
lower_bound	O(log n)	✅	>= value 첫 위치
upper_bound	O(log n)	✅	> value 첫 위치
equal_range	O(log n)	✅	[lower, upper) 범위

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

// 선형 검색: O(n)
auto it = std::find(v.begin(), v.end(), 3);

// 이진 검색: O(log n) (정렬 필요)
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 3);

검색 알고리즘 선택 가이드:

flowchart TD
    A["검색 시작"]
    B{"정렬됨?"}
    C{"값 검색?"}
    D["find"]
    E["find_if"]
    F{"존재 확인?"}
    G["binary_search"]
    H{"삽입 위치?"}
    I["lower_bound"]
    J["equal_range"]
    
    A --> B
    B -->|No| C
    C -->|Yes| D
    C -->|No| E
    B -->|Yes| F
    F -->|Yes| G
    F -->|No| H
    H -->|Yes| I
    H -->|No| J

find

#include <algorithm>

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

// find: 값 검색
auto it = std::find(v.begin(), v.end(), 3);

if (it != v.end()) {
    std::cout << "찾음: " << *it << std::endl;
}

// find_if: 조건 검색
auto it2 = std::find_if(v.begin(), v.end(),  {
    return x > 3;
});

실전 예시

예시 1: 구조체 검색

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

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    
    // 이름으로 검색
    auto it = std::find_if(people.begin(), people.end(),
         { return p.name == "Bob"; });
    
    if (it != people.end()) {
        std::cout << "찾음: " << it->name << " (" << it->age << ")" << std::endl;
    }
}

예시 2: binary_search

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 이진 검색 (정렬 필요)
    bool found = std::binary_search(v.begin(), v.end(), 5);
    
    if (found) {
        std::cout << "5 존재" << std::endl;
    }
}

예시 3: lower_bound & upper_bound

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 2, 2, 3, 4, 5};
    
    // lower_bound: >= value
    auto lower = std::lower_bound(v.begin(), v.end(), 2);
    std::cout << "lower: " << std::distance(v.begin(), lower) << std::endl;  // 1
    
    // upper_bound: > value
    auto upper = std::upper_bound(v.begin(), v.end(), 2);
    std::cout << "upper: " << std::distance(v.begin(), upper) << std::endl;  // 4
    
    // equal_range: [lower, upper)
    auto [first, last] = std::equal_range(v.begin(), v.end(), 2);
    std::cout << "개수: " << std::distance(first, last) << std::endl;  // 3
}

예시 4: 삽입 위치

#include <algorithm>

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9};
    
    // 정렬 유지하며 삽입할 위치
    int value = 6;
    auto pos = std::lower_bound(v.begin(), v.end(), value);
    
    v.insert(pos, value);
    
    for (int x : v) {
        std::cout << x << " ";  // 1 3 5 6 7 9
    }
}

검색 알고리즘

// 선형 검색
std::find(begin, end, value)
std::find_if(begin, end, pred)
std::find_if_not(begin, end, pred)

// 이진 검색 (정렬 필요)
std::binary_search(begin, end, value)
std::lower_bound(begin, end, value)
std::upper_bound(begin, end, value)
std::equal_range(begin, end, value)

// 인접 검색
std::adjacent_find(begin, end)

// 부분 검색
std::search(begin1, end1, begin2, end2)

자주 발생하는 문제

문제 1: 정렬 여부

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

// ❌ 정렬 안 됨
// bool found = std::binary_search(v.begin(), v.end(), 3);  // 정의되지 않은 동작

// ✅ 정렬 후 이진 검색
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 3);

문제 2: 반복자 무효화

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

auto it = std::find(v.begin(), v.end(), 3);

// ❌ 삽입 후 반복자 무효화
v.push_back(6);
// it 무효화 가능

// ✅ 인덱스 사용
auto index = std::distance(v.begin(), it);
v.push_back(6);
auto newIt = v.begin() + index;

문제 3: 성능

// find: O(n)
auto it = std::find(v.begin(), v.end(), value);

// binary_search: O(log n) (정렬 필요)
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), value);

// 여러 번 검색 시 정렬 후 이진 검색

문제 4: 범위

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

// ✅ 전체 검색
auto it = std::find(v.begin(), v.end(), 3);

// ✅ 부분 검색
auto it2 = std::find(v.begin() + 1, v.begin() + 4, 3);

활용 패턴

// 1. 선형 검색
auto it = std::find(v.begin(), v.end(), value);

// 2. 조건 검색
auto it = std::find_if(v.begin(), v.end(), pred);

// 3. 이진 검색
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), value);

// 4. 삽입 위치
auto pos = std::lower_bound(v.begin(), v.end(), value);
v.insert(pos, value);

실무 패턴

패턴 1: 조건부 검색

#include <algorithm>
#include <vector>

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

std::vector<User>::iterator findActiveUser(
    std::vector<User>& users,
    const std::string& name
) {
    return std::find_if(users.begin(), users.end(),
        [&name](const User& u) {
            return u.active && u.name == name;
        });
}

// 사용
std::vector<User> users = {
    {"Alice", 25, true},
    {"Bob", 30, false},
    {"Charlie", 35, true}
};

auto it = findActiveUser(users, "Charlie");
if (it != users.end()) {
    std::cout << "활성 사용자 찾음: " << it->name << '\n';
}

패턴 2: 범위 검색

#include <algorithm>
#include <vector>

std::pair<int, int> findRange(
    const std::vector<int>& sorted,
    int minVal,
    int maxVal
) {
    auto lower = std::lower_bound(sorted.begin(), sorted.end(), minVal);
    auto upper = std::upper_bound(sorted.begin(), sorted.end(), maxVal);
    
    return {
        std::distance(sorted.begin(), lower),
        std::distance(sorted.begin(), upper)
    };
}

// 사용
std::vector<int> scores = {60, 70, 75, 80, 85, 90, 95};
auto [start, end] = findRange(scores, 75, 90);

std::cout << "75-90 범위: ";
for (int i = start; i < end; ++i) {
    std::cout << scores[i] << " ";
}
// 출력: 75 80 85 90

패턴 3: 정렬 유지 삽입

#include <algorithm>
#include <vector>

template<typename T>
void insertSorted(std::vector<T>& sorted, const T& value) {
    auto pos = std::lower_bound(sorted.begin(), sorted.end(), value);
    sorted.insert(pos, value);
}

// 사용
std::vector<int> numbers = {1, 3, 5, 7, 9};

insertSorted(numbers, 6);
insertSorted(numbers, 2);

for (int n : numbers) {
    std::cout << n << " ";
}
// 출력: 1 2 3 5 6 7 9

FAQ

Q1: find와 binary_search의 차이는?

A:

• find: 선형 검색, O(n), 정렬 불필요
• binary_search: 이진 검색, O(log n), 정렬 필수

// find: 정렬 불필요
std::vector<int> v = {3, 1, 4, 1, 5};
auto it = std::find(v.begin(), v.end(), 4);

// binary_search: 정렬 필요
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 4);

Q2: lower_bound와 upper_bound의 차이는?

A:

• lower_bound: >= value 첫 위치
• upper_bound: > value 첫 위치

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

auto lower = std::lower_bound(v.begin(), v.end(), 2);
// 인덱스 1 (첫 번째 2)

auto upper = std::upper_bound(v.begin(), v.end(), 2);
// 인덱스 4 (마지막 2 다음)

Q3: binary_search는 위치를 반환하나요?

A: 아니요. 존재 여부만 반환합니다. 위치가 필요하면 lower_bound를 사용하세요.

// binary_search: bool 반환
bool found = std::binary_search(v.begin(), v.end(), 3);

// lower_bound: 반복자 반환
auto it = std::lower_bound(v.begin(), v.end(), 3);
if (it != v.end() && *it == 3) {
    std::cout << "위치: " << std::distance(v.begin(), it) << '\n';
}

Q4: 정렬되지 않은 범위에서 이진 검색하면?

A: 정의되지 않은 동작입니다. 반드시 정렬 후 사용하세요.

// ❌ 정렬 안 됨
std::vector<int> v = {3, 1, 4, 1, 5};
bool found = std::binary_search(v.begin(), v.end(), 3);  // UB

// ✅ 정렬 후
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 3);

Q5: find_if의 성능은?

A: O(n) 입니다. 조건을 만족하는 첫 요소를 찾을 때까지 순회합니다.

auto it = std::find_if(v.begin(), v.end(),  {
    return x > 5;
});

Q6: equal_range는 무엇인가요?

A: [lower_bound, upper_bound) 범위를 반환합니다.

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

auto [lower, upper] = std::equal_range(v.begin(), v.end(), 2);
std::cout << "2의 개수: " << std::distance(lower, upper) << '\n';  // 3

Q7: 반복자 무효화는?

A: 검색 알고리즘은 반복자를 무효화하지 않습니다. 하지만 삽입/삭제 후에는 주의하세요.

auto it = std::find(v.begin(), v.end(), 3);

// ❌ 삽입 후 반복자 무효화 가능
v.push_back(6);
// it 무효화 가능 (vector의 경우)

// ✅ 인덱스 사용
auto index = std::distance(v.begin(), it);
v.push_back(6);
auto newIt = v.begin() + index;

Q8: 검색 알고리즘 학습 리소스는?

A:

• “Effective STL” by Scott Meyers (Item 43-45)
• “C++ Primer” by Stanley Lippman
• cppreference.com - Search operations

관련 글: algorithm, sort, binary_search.

한 줄 요약: 검색 알고리즘은 컨테이너에서 특정 값이나 조건을 만족하는 요소를 찾는 STL 알고리즘입니다.

---

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

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

• C++ Algorithm MinMax | “최소/최대 알고리즘” 가이드
• C++ Algorithm Partition | “분할 알고리즘” 가이드
• C++ 알고리즘 | “STL algorithm” 핵심 정리

실전 팁

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

디버깅 팁

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

성능 팁

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

코드 리뷰 팁

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

---

실전 체크리스트

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

코드 작성 전

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

코드 작성 중

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

코드 리뷰 시

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

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

---

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

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

---

관련 글

• C++ STL 알고리즘 기초 완벽 가이드 | sort·find
• C++ Algorithm Copy |
• C++ Algorithm Count |
• C++ Algorithm Generate |
• C++ 알고리즘 |