C++ 기본적인 알고리즘 (정렬, 탐색)

1. 도입 (왜 배워야 하는가)

알고리즘은 데이터를 효율적으로 처리하는 방법을 정의하는 수학적 절차입니다. 실무에서는 대량의 데이터 처리나 성능 최적화가 필수적이기 때문에, 정렬과 탐색 알고리즘은 매우 중요합니다. 예를 들어, 쇼핑몰에서는 고객의 장바구니에 담은 상품을 가격 순서로 정렬하거나, 특정 상품을 검색하는 기능이 필요합니다. 이러한 알고리즘을 모르면 데이터 처리 속도가 느려지고, 사용자 경험이 저하될 수 있습니다.

2. 핵심 개념 설명

정렬 (Sorting)

정렬은 데이터를 특정 기준에 따라 순서대로 배열하는 과정입니다. 예를 들어, 친구의 생일 목록을 생일 순으로 정렬하는 것을 생각해 볼 수 있습니다. 생일이 빠른 친구부터 차례로 정리하면 나중에 축하할 때 편리해지겠죠.

탐색 (Searching)

탐색은 데이터 집합에서 특정 값을 찾는 과정입니다. 예를 들어, 도서관에서 원하는 책을 찾기 위해 책꽂이를 살펴보는 것을 비유할 수 있습니다. 책 제목을 알면 쉽게 찾을 수 있지만, 제목을 모르면 모든 책을 살펴봐야 합니다.

3. 기본 코드 예제

정렬 예제: 버블 정렬 (Bubble Sort)

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { // i: 전체 배열을 반복
        for (int j = 0; j < n - i - 1; j++) { // j: 현재 정렬되지 않은 부분을 반복
            if (arr[j] > arr[j + 1]) { // 두 인접한 원소 비교
                swap(arr[j], arr[j + 1]); // 원소 교환
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    
    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "; // 정렬된 배열 출력
    }
    return 0;
}

실행 결과:

정렬된 배열: 11 12 22 25 34 64 90

• bubbleSort 함수는 배열을 정렬하는 함수입니다.
• 첫 번째 for 루프는 전체 배열을 반복합니다.
• 두 번째 for 루프는 현재 정렬되지 않은 부분을 반복합니다.
• if 문은 두 인접한 원소를 비교하고, 필요 시 swap 함수를 통해 교환합니다.
• 마지막으로 정렬된 배열을 출력합니다.

탐색 예제: 선형 탐색 (Linear Search)

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) { // 배열을 처음부터 끝까지 순회
        if (arr[i] == x) { // 찾고자 하는 값과 비교
            return i; // 값이 발견되면 인덱스 반환
        }
    }
    return -1; // 값이 없으면 -1 반환
}

int main() {
    int arr[] = {2, 7, 11, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 11; // 탐색할 값
    int result = linearSearch(arr, n, x);
    
    if (result != -1) {
        cout << "값 " << x << "가 배열의 인덱스 " << result << "에 있습니다." << endl;
    } else {
        cout << "값 " << x << "는 배열에 없습니다." << endl;
    }
    return 0;
}

실행 결과:

값 11가 배열의 인덱스 2에 있습니다.

• linearSearch 함수는 배열에서 특정 값을 찾는 함수입니다.
• for 루프를 통해 배열의 모든 원소를 확인합니다.
• 값이 발견되면 해당 인덱스를 반환하고, 발견되지 않으면 -1을 반환합니다.

4. 실전 활용 예제

예제 1: 쇼핑몰 장바구니 정렬

쇼핑몰에서 장바구니에 담은 상품을 가격 순으로 정렬하여 사용자에게 보여줄 때 사용할 수 있습니다.

예제 2: 전화번호부 검색

전화번호부에서 특정 이름의 연락처를 찾을 때 선형 탐색을 사용할 수 있습니다. 사용자가 이름을 입력하면, 프로그램이 해당 이름을 가진 연락처를 반환합니다.

5. 흔한 실수와 주의사항

실수 1: 배열 크기 계산 오류

int n = sizeof(arr); // 잘못된 코드

• 올바른 코드:

int n = sizeof(arr) / sizeof(arr[0]); // 배열의 원소 개수를 정확히 계산

실수 2: 정렬 알고리즘 선택 오류

효율성이 떨어지는 정렬 알고리즘(예: 버블 정렬)을 대량의 데이터에 사용할 경우 성능이 저하됩니다.

6. 정리

• 정렬 알고리즘은 데이터를 효율적으로 정리하는 데 필수적입니다.
• 탐색 알고리즘은 데이터 집합에서 특정 값을 찾는 데 유용합니다.
• 다양한 정렬 및 탐색 알고리즘이 있으며, 상황에 맞는 알고리즘을 선택해야 합니다.
• 다음에는 더 효율적인 정렬 알고리즘인 퀵 정렬(Quick Sort)이나 이진 탐색(Binary Search)에 대해 배우는 것을 추천합니다.