22.2. 프로그램언어 C++에서의 검색 알고리즘

by

프로그램언어 C++의 순차 검색

C++의 순차 검색(Sequential Search)

순차 검색은 주어진 목록에서 원하는 항목을 찾기 위해 처음부터 끝까지 순서대로 탐색하는 방법입니다. 이 방법은 간단하지만 큰 목록에서는 효율적이지 않을 수 있습니다.

순차 검색의 원리

순차 검색은 목록의 첫 번째 항목부터 마지막 항목까지 차례대로 비교하면서 원하는 항목을 찾습니다. 원하는 항목을 찾을 때까지 계속 검색을 진행하며, 찾으면 해당 항목의 인덱스를 반환하거나 찾지 못하면 -1을 반환합니다.

순차 검색의 예제 코드


#include <iostream>
using namespace std;

int sequentialSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i; // 원하는 항목을 찾으면 인덱스 반환
        }
    }
    return -1; // 원하는 항목을 찾지 못한 경우
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 30;
    
    int result = sequentialSearch(arr, n, key);
    
    if (result != -1) {
        cout << "원하는 항목의 인덱스: " << result << endl;
    } else {
        cout << "원하는 항목을 찾지 못했습니다." << endl;
    }
    
    return 0;
}

프로그램언어 C++의 이진 검색

이진 검색(Binary Search)은 정렬된 배열에서 원하는 값을 찾는 알고리즘입니다. C++에서 이진 검색은 배열의 중간 요소와 비교하여 탐색 범위를 반으로 줄여가며 원하는 값을 찾습니다. 이를 통해 빠르게 원하는 값을 찾을 수 있습니다.

이진 검색의 원리는 다음과 같습니다. 먼저, 배열을 정렬한 후 중간 요소를 선택합니다. 이 중간 요소와 찾고자 하는 값과 비교하여 중간 요소가 더 작으면 왼쪽 부분 배열을, 중간 요소가 더 크면 오른쪽 부분 배열을 탐색합니다. 이 과정을 반복하여 원하는 값을 찾을 때까지 탐색 범위를 반으로 줄여가는 방식입니다.

아래는 C++로 구현된 이진 검색의 예제 코드입니다. 


#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // 찾는 값이 배열에 없을 경우 -1 반환
}

int main() {
    vector nums = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;

    int result = binarySearch(nums, target);

    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

프로그램언어 C++의 해쉬 검색

해쉬 검색은 효율적인 데이터 검색을 위한 방법 중 하나로, 키-값 쌍을 저장하고 검색하는 데 사용됩니다. C++에서는 해쉬 검색을 위해 unordered_map 컨테이너를 제공합니다. 이 컨테이너는 해쉬 함수를 사용하여 키를 해싱하고, 이를 기반으로 빠르게 값을 찾을 수 있습니다.

아래는 C++에서 해쉬 검색을 사용하는 간단한 예제 코드입니다. 


#include 
#include 

int main() {
    // unordered_map을 사용하여 해쉬 테이블 생성
    std::unordered_map hashTable;

    // 해쉬 테이블에 값 추가
    hashTable["apple"] = 5;
    hashTable["banana"] = 3;
    hashTable["cherry"] = 7;

    // 해쉬 테이블에서 값 찾기
    std::string key = "banana";
    if (hashTable.find(key) != hashTable.end()) {
        std::cout << key << "의 값: " << hashTable[key] << std::endl;
    } else {
        std::cout << key << "를 찾을 수 없습니다." << std::endl;
    }

    return 0;
}

프로그램언어 C++의 이터폴레이션 검색

이터폴레이션 검색은 C++ 프로그래밍에서 사용되는 중요한 기술 중 하나입니다. 이터폴레이션 검색은 주어진 데이터 집합에서 주어진 값에 가장 근접한 값을 찾는 과정을 의미합니다. 이는 데이터를 보간하거나 근사하는 데 유용하게 활용됩니다.

이터폴레이션 검색을 구현하는 방법 중 하나는 선형 보간법(linear interpolation)을 사용하는 것입니다. 선형 보간법은 두 개 이상의 점을 연결하여 주어진 값에 대한 근사값을 계산하는 방법입니다. 아래는 C++에서 선형 보간법을 사용한 이터폴레이션 검색의 예제 코드입니다. 


#include <iostream>
#include <vector>
#include <algorithm>

// 선형 보간법을 사용한 이터폴레이션 함수
double linearInterpolation(const std::vector<double>& x, const std::vector<double>& y, double query) {
    auto it = std::lower_bound(x.begin(), x.end(), query); // query보다 크거나 같은 첫 번째 원소의 위치를 찾음
    if (it == x.begin()) {
        return y.front(); // query가 x의 최솟값보다 작을 경우
    }
    if (it == x.end()) {
        return y.back(); // query가 x의 최댓값보다 클 경우
    }
    
    // 선형 보간 계산
    size_t idx = it - x.begin();
    double x0 = x[idx - 1];
    double x1 = x[idx];
    double y0 = y[idx - 1];
    double y1 = y[idx];
    
    return y0 + (query - x0) * (y1 - y0) / (x1 - x0);
}

int main() {
    std::vector<double> x = {1.0, 2.0, 3.0, 4.0, 5.0};
    std::vector<double> y = {10.0, 20.0, 30.0, 40.0, 50.0};
    
    double query = 2.5;
    double result = linearInterpolation(x, y, query);
    
    std::cout << "Interpolated value at " << query << ": " << result << std::endl;
    
    return 0;
}

위 예제 코드는 주어진 x와 y 값들을 이용하여 선형 보간법을 적용하여 query 값에 대한 근사값을 계산하는 방법을 보여줍니다. 선형 보간법은 두 점을 직선으로 연결하여 값을 추정하는 간단하면서도 유용한 방법 중 하나입니다.

프로그램언어 C++의 피보나치 검색

피보나치 검색은 피보나치 수열의 특정 항을 찾는 과정을 말합니다. C++에서 피보나치 검색을 구현하기 위해서는 주로 재귀 함수나 반복문을 활용합니다. 아래는 C++로 피보나치 검색을 구현한 예제 코드입니다. 


#include <iostream>

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int n = 10; // 찾고자 하는 피보나치 수열의 항
    int result = fibonacci(n);

    std::cout << "피보나치 수열의 " << n << "번째 항은 " << result << "입니다." << std::endl;

    return 0;
}

Leave a Comment