알고리즘 기초 — 탐색, 정렬, 효율성

알고리즘은 주어진 문제를 해결하기 위한 명확하고 단계적인 절차입니다. 우리가 배운 순차(위에서 아래로), 조건(if), 반복(for, while) 구조를 레고 블록처럼 조합하여 '가장 빠르고 정확하게 데이터를 가공하는 방법'을 설계하는 것입니다.

선형 탐색(Linear Search)은 배열의 처음부터 끝까지 하나씩 확인하는 단순한 방법입니다. 반면, 이진 탐색(Binary Search)은 데이터가 미리 정렬되어 있다는 조건 하에 가운데를 찔러보고 절반씩 범위를 버려나가는 매우 빠른 탐색 기법입니다.

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

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

        if (arr[mid] == target) return mid;        // 찾음
        if (arr[mid] < target) left = mid + 1;  // 오른쪽 절반으로 축소
        else right = mid - 1;                     // 왼쪽 절반으로 축소
    }
    return -1; // 못 찾음
}

무작위 데이터를 순서대로(오름차순/내림차순) 나열하는 것을 정렬(Sort)이라고 합니다. 정렬이 되어 있어야 위에서 배운 강력한 '이진 탐색'을 사용할 수 있습니다.

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // 루프가 돌 때마다 제일 큰 값이 맨 뒤로 고정되므로 끝 범위를 1씩 줄임
        for (int j = 0; j < size - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) { // 오름차순 (앞이 더 크면 교환)
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

알고리즘의 성능은 "몇 초가 걸리는가?"로 측정하지 않습니다. 컴퓨터 성능에 따라 달라지기 때문입니다. 대신 "데이터 개수(n)가 늘어날 때 연산 횟수가 어떻게 증가하는가?"를 표현하는 표기법이 바로 Big-O입니다.

• O(1) : 데이터가 100만 개든 1개든 동일한 속도 (예: arr[5] 인덱스 접근)
• O(log n) : 절반씩 쪼개며 검색하여 매우 빠름 (예: 이진 탐색)
• O(n) : 데이터 개수만큼 비례해서 시간 증가 (예: 선형 탐색, for문 1번)
• O(n²) : for문이 중첩되어 최악의 경우 매우 느림 (예: 버블, 선택 정렬)