C++ 코딩테스트 강좌, 삽입 정렬

안녕하세요! 이번 포스트에서는 C++를 이용한 코딩테스트에서 자주 출제되는 알고리즘 중 하나인 삽입 정렬에 대해 다뤄보겠습니다. 삽입 정렬은 매우 직관적인 정렬 알고리즘으로, 정렬된 배열에 새로운 데이터를 삽입하는 방식으로 동작합니다. 그럼 시작해볼까요?

문제 설명

주어진 정수를 포함한 배열이 있습니다. 이 배열을 삽입 정렬을 이용해 오름차순으로 정렬한 결과를 출력하시오.

입력 형식

첫 번째 줄에 배열의 크기 N이 주어집니다. (1 ≤ N ≤ 1000)

두 번째 줄에 N개의 정수가 공백으로 구분되어 주어집니다. (각 정수는 -1000 ≤ x ≤ 1000)

출력 형식

정렬된 배열을 한 줄에 출력하시오. 각 요소는 공백으로 구분됩니다.

예제

알고리즘 설명

삽입 정렬(Insertion Sort)은 정렬된 배열에 새로운 값을 삽입하는 방식으로 동작합니다. 알고리즘은 다음과 같은 단계로 진행됩니다:

첫 번째 원소는 정렬된 배열로 간주합니다.
두 번째 원소부터 시작하여 해당 원소를 정렬된 배열에 삽입할 위치를 찾습니다.
배열의 원소를 오른쪽으로 한 칸씩 이동시키면서 새 원소가 들어갈 위치를 찾습니다.
올바른 위치를 찾으면 새 원소를 삽입합니다.
이 과정을 배열의 모든 원소에 대해 반복합니다.

C++ 코드 구현

이제 위의 알고리즘을 C++로 구현해보겠습니다. 코드는 다음과 같습니다:

        
        #include <iostream>
        #include <vector>

        using namespace std;

        void insertionSort(vector<int>& arr) {
            int n = arr.size();
            for (int i = 1; i < n; i++) {
                int key = arr[i];
                int j = i - 1;

                // key보다 큰 원소들을 한 칸씩 이동
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = key; // key를 적절한 위치에 삽입
            }
        }

        int main() {
            int N;
            cin >> N;
            vector<int> arr(N);

            for (int i = 0; i < N; i++) {
                cin >> arr[i];
            }

            insertionSort(arr);

            for (int i = 0; i < N; i++) {
                cout << arr[i];
                if (i < N - 1) cout << " "; // 마지막 원소 뒤에 공백을 추가하지 않기 위해
            }

            return 0;
        }

코드 설명

위 코드는 삽입 정렬 알고리즘을 C++로 구현한 것입니다. 주요 부분을 살펴보겠습니다:

헤더 파일 포함: <iostream>와 <vector>를 포함하여 입력 및 출력을 수행하고 동적 배열을 사용할 수 있도록 합니다.
insertionSort 함수: 배열을 정렬하는 함수입니다. 각 원소에 대해 키를 설정하고 정렬된 배열에 삽입할 위치를 찾습니다.
메인 함수: 정렬할 배열의 크기를 입력받고, 배열을 입력받은 후 insertionSort 함수를 호출하여 정렬합니다. 최종적으로 정렬된 결과를 출력합니다.

시간 복잡도 분석

삽입 정렬의 시간 복잡도는 다음과 같습니다:

최악의 경우: O(n^2) (배열이 뒤죽박죽일 때)
평균 경우: O(n^2)
최선의 경우: O(n) (배열이 이미 정렬되어 있을 때)

이러한 시간 복잡도로 인해 삽입 정렬은 작은 배열에 대해 효율적이지만, 큰 배열에 대해서는 성능이 떨어집니다.

장단점

장점

코드 구현이 간단하고 이해하기 쉬움
작은 데이터 세트에 대해서는 매우 효율적
안정 정렬입니다 (같은 값을 가진 요소들의 순서가 유지됨)

단점

시간 복잡도가 O(n^2)로 큰 입력 데이터에 대해 효율적이지 않음
배열을 직접 수정하기 때문에 메모리 사용이 비효율적일 수 있음

이해도를 높이기 위한 추가 예제

추가적인 예제를 통해 삽입 정렬의 동작을 시각적으로 이해해보겠습니다. 다음은 삽입 정렬의 과정을 보여주는 예제입니다.

예제

        입력:
        6
        4 3 5 1 2 6
  
        과정:
        초기 배열: 4 3 5 1 2 6
        1단계: [4] [3] 5 1 2 6 → 3 4 5 1 2 6
        2단계: 3 4 [5] [1] 2 6 → 3 4 5 1 2 6
        3단계: 3 4 5 [1] [2] 6 → 1 3 4 5 2 6
        4단계: 1 3 4 5 [2] 6 → 1 2 3 4 5 6
        5단계: 1 2 3 4 5 [6] → 1 2 3 4 5 6

결론

오늘은 C++를 이용한 삽입 정렬에 대해 알아보았습니다. 삽입 정렬은 간단하면서도 유용한 알고리즘으로, 작은 데이터 세트에서는 효과적이라는 점을 기억해두세요. 다음 포스트에서는 보다 복잡한 정렬 알고리즘인 퀵 정렬에 대해 다룰 예정입니다. 질문이나 코멘트가 있으면 아래에 남겨주세요. 감사합니다!