C++ 코딩테스트 강좌, 원하는 정수 찾기

안녕하세요! 여러분과 함께하는 C++ 코딩 테스트 강좌입니다. 오늘의 주제는 ‘원하는 정수 찾기’입니다. 이 강좌는 C++로 코딩 테스트를 준비하는 여러분에게 도움이 될 것입니다. 문제를 이해하고 올바른 해결 방법을 찾는 과정을 자세히 설명하겠습니다. 본 강좌는 총 20,000자 이상으로 설계되어 있습니다.

문제 설명

주어진 정수 배열 arr와 하나의 정수 target이 있습니다. arr에서 target을 찾아 그 인덱스를 반환하는 프로그램을 작성하세요. arr에 target이 존재하지 않을 경우 -1을 반환합니다. 배열의 길이는 최대 10^6입니다. 배열은 정렬되어 있지 않을 수도 있습니다.

입력

arr = [2, 3, 4, 7, 11, 15, 20]
target = 7

출력

결과: 3

문제 분석

이 문제는 배열에서 특정 값을 찾는 문제로, 다양한 방식으로 해결할 수 있습니다. 일반적인 방식으로는 선형 탐색과 이진 탐색이 있습니다. 하지만 배열이 정렬되어 있는 경우에는 이진 탐색이 더 효율적입니다. 하지만 주어진 문제에서는 배열이 정렬되어 있지 않아 선형 탐색을 사용해 문제를 해결하겠습니다.

알고리즘 선택

문제에서 정렬되지 않은 배열을 주기 때문에 선형 탐색(linear search)을 사용할 것입니다. 선형 탐색은 배열의 각 요소를 하나씩 확인하여 찾고자 하는 값을 찾는 단순한 알고리즘입니다. 시간 복잡도는 O(n)입니다.

선형 탐색 알고리즘

선형 탐색의 기본 아이디어는 다음과 같습니다:

배열의 첫 번째 요소부터 시작합니다.
원하는 정수를 찾을 때까지 배열의 각 요소를 순차적으로 비교합니다.
찾으면 해당 요소의 인덱스를 반환합니다.
배열 끝에 도달할 때까지 찾지 못하면 -1을 반환합니다.

코드 구현

이제 C++로 선형 탐색 알고리즘을 구현해 보겠습니다. 아래에 코드를 작성하였습니다:

#include <iostream>
#include <vector>

int findTarget(const std::vector<int> &arr, int target) {
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            return i; // Target found, return index
        }
    }
    return -1; // Target not found
}

int main() {
    std::vector<int> arr = {2, 3, 4, 7, 11, 15, 20};
    int target = 7;

    int index = findTarget(arr, target);
    if (index != -1) {
        std::cout << "결과: " << index << std::endl;
    } else {
        std::cout << "결과: -1" << std::endl;
    }

    return 0;
}

코드 설명

위의 코드에서 findTarget 함수는 배열과 찾고자 하는 값을 입력으로 받아서 해당 값을 배열에서 찾아 반환합니다.

for 루프를 통해 배열의 각 요소에 접근합니다.
현재 요소가 target과 같은지 확인합니다. 같다면 해당 인덱스를 반환합니다.
모든 요소를 확인한 후에도 찾지 못했다면 -1을 반환하여 ‘찾지 못했다’는 의미를 명시합니다.

성능 분석

위의 선형 탐색 알고리즘의 시간 복잡도는 O(n)입니다. 최악의 경우에는 배열의 모든 요소를 확인해야 하므로, n이 배열의 크기일 때 이런 성능을 보입니다. 메모리 복잡도는 O(1)입니다.

테스트

이제 몇 가지 테스트 케이스를 만들어 알고리즘의 유효성을 검증해 보겠습니다.

테스트 케이스

arr = [1, 2, 3, 4, 5], target = 3 -> 결과: 2
arr = [10, 20, 30, 40, 50], target = 25 -> 결과: -1
arr = [5, 1, 9, 3], target = 1 -> 결과: 1

결론

오늘은 C++을 사용하여 원하는 정수를 찾는 문제를 해결했습니다. 우리는 선형 탐색 알고리즘을 사용하여 배열에서 특정 숫자를 찾는 방법을 배웠습니다. 이런 문제는 실제 인터뷰에서도 자주 출제되므로, 충분한 연습을 통해 능숙해져야 합니다. 다음 강좌에서는 다른 알고리즘과 더 복잡한 문제를 다룰 예정이니 많은 기대 바랍니다!

참고자료

자세한 내용은 다음 자료를 참조하시기 바랍니다: