[C++] 배열 내의 원소 위치 찾기 with C++

배열 내의 원소 위치 찾기

개요

　이번 글에서는 C++로 구현할 수 있는 배열 내의 원소 위치 찾는 방법들에 대해 알아보겠다. 먼저, 가장 기본적인 방식인 순차적인 탐색으로 원소를 비교하는 방법을 살펴본다. 그다음으로는 표준 라이브러리에서 제공하는 std::find와 std::distance 함수를 활용하는 방법을 공부해 보자. 각 방법의 특성을 분석하고, 특정 상황에서 어떤 방법이 최적인지에 대해 이해하도록 하겠다.

---

본문

　먼저 일반적으로 배열에서 원소의 위치를 찾기 위해 for문과 if문을 활용한 방법이다.

 

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

int main() 
{
    vector<int> v = { 1,2,3,4,5,6,7 };
    int target = 5;

    for (int i = 0; i < v.size(); ++i) 
    {
        if (v[i] == target) 
        {
            cout << " Found " << target << " at position: " << i << "\n";
            return 0;
        }
    }

    cout << " Did not find " << target << "\n";
    return 0;
}

출력 결과

 

　위의 코드는 배열의 모든 원소를 처음부터 끝까지 검사하여 원하는 값을 찾는다. 따라서 이 방법의 시간 복잡도는 O(n)이다. 하지만 더 효율적인 방법도 있다.

 

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

int main() 
{
    vector<int> v = { 1,2,3,4,5,6,7 };
    int target = 5;
    
    auto it = std::find(v.begin(), v.end(), target);

    if (it != v.end())
        cout << " Found: " << target << " at position: " << distance(v.begin(), it) << "\n";

    else
        cout << " Did not find " << target << "\n";

    return 0;
}

출력 결과

 

　위의 코드는 std::find 함수를 사용하여 원하는 값을 찾은 후, std::distance 함수를 사용하여 그 위치를 계산한다. 이 방법의 시간 복잡도 역시 O(n)이다. 

 

출처: cpp reference

 

　여기서 std::distance() 함수는 두 반복자 사이의 거리를 계산한다. 따라서 배열의 시작점과 반복자 사이의 거리가 곧 특정 원소의 위치가 되는 것이다.

 

　그럼에도 불구하고 std::find 함수를 사용하는 것이 직접 순회하는 것보다 권장된다. 그 이유는, 코드가 간결하며 표준 라이브러리의 최적화를 활용할 수 있기 때문이다. 또한 std::find 함수는 다양한 종류의 컨테이너에 사용할 수 있어 코드의 재사용성이 높아진다. 

---

요약

배열 내 원소 위치 찾기
- std::find() 함수로 값을 찾아내어 반복자에 초기화시킨 후, std::distance() 함수를 이용해 두 인자 사이의 거리 반환