회전 정렬된 벡터의 최소값 찾기

소개

이 랩에서는 회전된 정렬된 벡터에서 최소값을 찾는 C++ 프로그램을 만들 것입니다. 정렬된 벡터는 미리 알 수 없는 피벗 요소에서 회전될 수 있습니다.

필요한 라이브러리 포함 및 네임스페이스 선언

먼저, 필요한 라이브러리를 포함하고 네임스페이스를 선언해야 합니다. 이 코드는 ~/project/main.cpp 파일에 작성됩니다. 1 단계의 전체 코드는 다음과 같습니다.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

최소값을 찾는 함수 생성

회전된 정렬된 벡터에서 최소값을 찾기 위해 findMin이라는 함수를 만들 것입니다. 이 함수에서 벡터의 각 요소를 반복하고 해당 요소가 최소값인지 확인합니다. 요소가 최소값인지 확인하는 로직은 코드 블록의 주석에서 설명합니다. 2 단계의 전체 코드는 다음과 같습니다.

int findMin(vector<int> &m)
{
    int i;
    int n = m.size();
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            // check the first element
            if (m[i] < m[n - 1] && m[i] < m[1])
                break;
        }
        else
        {
            // check all other elements
            if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
                break;
        }
    }
    return m[i % n];
}

코드 테스트를 위한 메인 함수 작성

메인 함수에서 v라는 벡터를 생성하고 일부 요소로 초기화합니다. 그런 다음 findMin 함수를 호출하여 벡터에서 최소값을 찾습니다. 마지막으로 최소값을 출력합니다. 3 단계의 전체 코드는 다음과 같습니다.

int main()
{
    vector<int> v = {4, 5, 6, 7, 1, 3, 2};
    int n = v.size();
    int minimum = 0;
    cout << "The elements of the given vector are: ";
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    minimum = findMin(v);
    cout << "\n\nThe Minimum element in the given vector is: " << minimum << endl;
    return 0;
}

코드 컴파일 및 실행

터미널 창에서 cd 명령을 사용하여 main.cpp 파일이 있는 디렉토리로 이동합니다. 그런 다음 다음 명령을 사용하여 코드를 컴파일합니다.

g++ main.cpp -o main

오류가 없으면 다음 명령을 사용하여 실행 파일을 실행합니다.

./main

다음 출력을 볼 수 있습니다.

The elements of the given vector are: 4 5 6 7 1 3 2
The Minimum element in the given vector is: 1

이 출력은 코드가 벡터에서 올바른 최소값을 찾았음을 확인합니다.

요약

이 랩에서는 회전된 정렬된 벡터에서 최소값을 찾는 C++ 프로그램을 만들었습니다. 벡터의 각 요소를 반복하고 해당 요소가 최소값인지 확인하여 이를 달성했습니다. 마지막으로 최소값을 콘솔에 출력했습니다. 이 랩이 프로그래밍 학습 여정에 도움이 되었기를 바랍니다.