O(n) 시간 복잡도로 배열 뒤집기

소개

이 랩에서는 C++ 프로그래밍 언어를 사용하여 배열을 다양한 기술로 뒤집는 방법을 배우게 됩니다. 배열 뒤집기 (Array reversal) 는 배열의 순서를 변경하는 것을 의미하며, 배열의 마지막 요소가 첫 번째 요소가 되고, 첫 번째 요소가 마지막 요소가 됩니다. 이 랩에서는 for 루프, 내장 함수, 포인터, 재귀, 사용자 정의 함수를 포함한 다양한 방법을 사용하여 배열 뒤집기를 수행하는 방법을 배웁니다.

새 C++ 파일 생성

다음 명령을 실행하여 ~/project 디렉토리에 reverse_array.cpp라는 새 C++ 파일을 생성합니다.

touch ~/project/reverse_array.cpp

for 루프를 사용하여 배열 뒤집기

다음 코드는 for 루프를 사용하여 배열을 뒤집는 방법을 보여줍니다.

#include <iostream>
using namespace std;
void reverseArray(int arr[], int size){
    for(int i=0;i<size/2;i++){
        int temp = arr[i];
        arr[i] = arr[size-i-1];
        arr[size-i-1] = temp;
    }
}
int main(){
    int arr[]={1,2,3,4,5};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverseArray(arr,size);
    cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

코드를 컴파일하고 실행하려면 다음 명령을 사용하십시오.

g++ reverse_array.cpp -o reverse_array
./reverse_array

내장 함수를 사용하여 배열 뒤집기

다음 코드는 내장 C++ 함수를 사용하여 배열을 뒤집는 방법을 보여줍니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int arr[]={1,2,3,4,5};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverse(arr,arr+size);
    cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

코드를 컴파일하고 실행하려면 다음 명령을 사용하십시오.

g++ reverse_array.cpp -o reverse_array
./reverse_array

사용자 정의 함수를 사용하여 배열 뒤집기

다음 코드는 사용자 정의 함수를 정의하여 배열을 뒤집는 방법을 보여줍니다.

#include <iostream>
using namespace std;
void reverseArray(int arr[], int size){
    for(int i=0;i<size/2;i++){
        int temp = arr[i];
        arr[i] = arr[size-i-1];
        arr[size-i-1] = temp;
    }
}
int main(){
    int arr[]={1,2,3,4,5};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverseArray(arr,size);
    cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

코드를 컴파일하고 실행하려면 다음 명령을 사용하십시오.

g++ reverse_array.cpp -o reverse_array
./reverse_array

포인터를 사용하여 배열 뒤집기

다음 코드는 포인터를 사용하여 배열을 뒤집는 방법을 보여줍니다.

#include <iostream>
using namespace std;
void reverseArray(int *arr, int size){
    int *first = arr, *last = arr + size - 1;
    while(first < last){
        int temp = *first;
        *first = *last;
        *last = temp;
        first++;
        last--;
    }
}
int main(){
   int arr[] = {1, 2, 3, 4, 5};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   reverseArray(arr, size);
   cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   return 0;
}

코드를 컴파일하고 실행하려면 다음 명령을 사용하십시오.

g++ reverse_array.cpp -o reverse_array
./reverse_array

재귀를 사용하여 배열 뒤집기

다음 코드는 재귀를 사용하여 배열을 뒤집는 방법을 보여줍니다.

#include <iostream>
using namespace std;
void reverseArray(int arr[], int start, int end){
    if(start >= end)
        return;
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    reverseArray(arr,start+1,end-1);
}
int main(){
   int arr[] = {1, 2, 3, 4, 5};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   reverseArray(arr,0,size-1);
   cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   return 0;
}

코드를 컴파일하고 실행하려면 다음 명령을 사용하십시오.

g++ reverse_array.cpp -o reverse_array
./reverse_array

요약

축하합니다! O(n) 시간 복잡도로 배열 뒤집기 랩을 완료했습니다. LabEx 에서 더 많은 랩을 연습하여 실력을 향상시킬 수 있습니다.