C/C++ 알고리즘

C와 C++의 선형 탐색

이 레슨에서는 선형 탐색 알고리즘으로 정렬되지 않은 배열에서 값의 위치를 찾습니다.

소개

선형 탐색은 배열의 처음부터 요소를 하나씩 확인하면서 찾는 값이 나오거나 끝에 이를 때까지 계속합니다. 가장 간단한 탐색 알고리즘이며, 데이터가 정렬되어 있지 않아도 동작합니다.

핵심 정리

빈 입력, 요소 하나, 중복 값, 이미 정렬된 데이터로 테스트하세요.
먼저 코드가 올바르게 동작하게 만든 다음 최적화하세요.
실제 코드에서는 표준 라이브러리의 이미 만들어진 함수를 우선 쓰세요.

C와 C++의 선형 탐색 시각화

O(n)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>

int find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}

실행 결과

index=3

C++

실행 →

main.cpp

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

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

실행 결과

index=3

C와 C++ 비교

두 버전 모두 최악의 경우 복잡도가 O(n)입니다. C의 find 함수는 부호 있는 int 인덱스를 돌려주므로, 값을 찾지 못했을 때 -1로 알릴 수 있습니다. C++ 버전은 반복자를 돌려주는 std::find를 씁니다. 그 반복자가 values.end()와 같으면 값이 배열에 없다는 뜻입니다.

반복문, 포인터, 길이, 임시 버퍼를 모두 명시적으로 작성합니다.

C++

반복자와 표준 알고리즘이 처리 방식과 데이터를 저장하는 방식을 분리합니다.

연습 문제

두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.

종이에 비교 과정을 하나씩 따라가 보세요.
중복 값과 아주 크거나 작은 값으로 테스트해 보세요.
직접 작성한 코드의 실행 시간을 재고 표준 라이브러리와 비교해 보세요.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

First Negative Index Find where the first negative number appears. 쉬움

모든 챌린지