[Algorithm] C++/Python 백준 24051번 : 알고리즘 수업

정렬 알고리즘은 컴퓨터 과학에서 가장 기본적이고 중요한 개념 중 하나이다. 특히, 삽입 정렬은 이해하기 쉽고 직관적인 알고리즘으로, 다양한 상황에서 응용될 수 있다. 이번 글에서는 백준의 “알고리즘 수업 - 삽입 정렬 1” 문제를 통해 삽입 정렬의 동작 방식을 자세히 살펴보고, 주어진 문제를 효과적으로 해결하는 방법을 알아보고자 한다.

문제 : https://www.acmicpc.net/problem/24051

문제 설명

백준 문제 24051번 “알고리즘 수업 - 삽입 정렬 1"은 N개의 서로 다른 양의 정수가 저장된 배열 A가 주어진다. 이 배열을 삽입 정렬을 사용하여 오름차순으로 정렬할 때, 배열 A에 K번째로 저장되는 수를 구하는 문제이다.

삽입 정렬의 기본적인 동작은 배열의 두 번째 원소부터 시작하여 현재 원소를 적절한 위치에 삽입함으로써 정렬을 진행하는 것이다. 문제에서 요구하는 것은 삽입 정렬 과정에서 배열에 저장되는 모든 연산 중 K번째로 저장되는 값을 찾는 것이다. 만약 저장 횟수가 K보다 작으면 -1을 출력해야 한다.

예를 들어, 배열 A가 [4, 5, 1, 3, 2]이고 K가 7이라면, 삽입 정렬 과정을 따라가며 저장되는 값을 세어 K번째 저장된 값을 출력해야 한다. 이 경우, K번째 저장된 값은 5이다. 반면, K가 저장 횟수보다 큰 경우에는 -1을 출력해야 한다.

접근 방식

이 문제를 해결하기 위해서는 삽입 정렬의 과정을 정확히 시뮬레이션하면서 저장되는 모든 연산을 추적해야 한다. 삽입 정렬은 각 단계에서 현재 원소를 적절한 위치에 삽입하기 위해 이전 원소들을 이동시키는 과정을 포함한다. 이때, 원소를 이동시킬 때마다 배열에 저장 연산이 발생하며, 이를 카운트해야 한다.

구체적으로, 다음과 같은 접근 방식을 사용한다:

초기 설정: 배열 A와 저장 횟수 K를 입력받는다. 저장 횟수를 세기 위한 카운터를 초기화한다.
삽입 정렬 시뮬레이션: 두 번째 원소부터 시작하여 각 원소를 적절한 위치에 삽입한다.
- 현재 원소를 newItem으로 설정하고, 이전 원소들과 비교하면서 이동시킨다.
- 이전 원소가 newItem보다 크면 한 칸씩 이동시키고, 이동할 때마다 저장 연산을 카운트한다.
- 적절한 위치를 찾았을 때 newItem을 삽입하고, 이 또한 저장 연산을 카운트한다.
K번째 저장 확인: 저장 연산이 K번째에 도달하면 해당 값을 출력하고 종료한다.
결과 출력: 전체 삽입 정렬 과정이 끝났는데도 저장 횟수가 K보다 작으면 -1을 출력한다.

이러한 과정을 통해 삽입 정렬의 모든 저장 연산을 추적하고, K번째 저장된 값을 정확히 찾을 수 있다.

C++ 코드와 설명

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long K;
    cin >> N >> K;
    
    // 배열 A의 원소를 입력받는다.
    vector<int> A(N);
    for(auto &x : A) cin >> x;
    
    long long count = 0; // 저장 연산의 횟수를 세기 위한 카운터
    
    // 삽입 정렬을 수행한다.
    for(int i = 1; i < N; i++){
        int newItem = A[i]; // 현재 삽입할 원소
        int loc = i - 1; // 삽입할 위치를 찾기 위한 인덱스
        
        // newItem보다 큰 원소를 오른쪽으로 이동시킨다.
        while(loc >= 0 && A[loc] > newItem){
            A[loc + 1] = A[loc]; // 원소를 오른쪽으로 이동
            count++; // 저장 연산 카운트
            if(count == K){
                cout << A[loc];
                return 0;
            }
            loc--;
        }
        
        // newItem을 적절한 위치에 삽입한다.
        if(loc + 1 != i){
            A[loc + 1] = newItem;
            count++; // 저장 연산 카운트
            if(count == K){
                cout << newItem;
                return 0;
            }
        }
    }
    
    // 저장 횟수가 K보다 작으면 -1을 출력
    cout << "-1";
}

코드의 동작 단계별 설명

입력 처리: 먼저 배열의 크기 N과 저장 횟수 K를 입력받고, 배열 A의 원소들을 입력받는다.
삽입 정렬 시작: 두 번째 원소부터 시작하여 배열을 정렬해 나간다.
원소 이동 및 저장 연산 카운트:
- 현재 삽입할 원소 newItem을 설정하고, 이전 원소들과 비교하면서 newItem보다 큰 원소를 오른쪽으로 이동시킨다.
- 원소를 이동시킬 때마다 저장 연산이 발생하므로 count를 증가시킨다.
- 만약 count가 K와 같아지면 현재 저장된 값을 출력하고 프로그램을 종료한다.
원소 삽입: 적절한 위치를 찾았다면 newItem을 삽입하고, 이 또한 저장 연산이 발생하므로 count를 증가시킨다. K와 같아지면 값을 출력하고 종료한다.
결과 출력: 모든 삽입 정렬 과정을 마쳤음에도 count가 K보다 작으면 -1을 출력한다.

C++ without library 코드와 설명

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long K;
    cin >> N >> K;
    
    // 배열 동적 할당
    int* A = new int[N];
    for(int i = 0; i < N; i++) cin >> A[i];
    
    long long count = 0; // 저장 연산의 횟수를 세기 위한 카운터
    
    // 삽입 정렬을 수행한다.
    for(int i = 1; i < N; i++){
        int newItem = A[i]; // 현재 삽입할 원소
        int loc = i - 1; // 삽입할 위치를 찾기 위한 인덱스
        
        // newItem보다 큰 원소를 오른쪽으로 이동시킨다.
        while(loc >= 0 && A[loc] > newItem){
            A[loc + 1] = A[loc]; // 원소를 오른쪽으로 이동
            count++; // 저장 연산 카운트
            if(count == K){
                cout << A[loc];
                delete[] A;
                return 0;
            }
            loc--;
        }
        
        // newItem을 적절한 위치에 삽입한다.
        if(loc + 1 != i){
            A[loc + 1] = newItem;
            count++; // 저장 연산 카운트
            if(count == K){
                cout << newItem;
                delete[] A;
                return 0;
            }
        }
    }
    
    // 저장 횟수가 K보다 작으면 -1을 출력
    cout << "-1";
    delete[] A;
}

코드의 동작 단계별 설명

입력 처리: 배열의 크기 N과 저장 횟수 K를 입력받고, 배열 A의 원소들을 동적 할당을 통해 입력받는다.
삽입 정렬 시작: 두 번째 원소부터 시작하여 배열을 정렬해 나간다.
원소 이동 및 저장 연산 카운트:
- 현재 삽입할 원소 newItem을 설정하고, 이전 원소들과 비교하면서 newItem보다 큰 원소를 오른쪽으로 이동시킨다.
- 원소를 이동시킬 때마다 저장 연산이 발생하므로 count를 증가시킨다.
- 만약 count가 K와 같아지면 현재 저장된 값을 출력하고 동적 할당된 메모리를 해제한 후 프로그램을 종료한다.
원소 삽입: 적절한 위치를 찾았다면 newItem을 삽입하고, 이 또한 저장 연산이 발생하므로 count를 증가시킨다. K와 같아지면 값을 출력하고 동적 할당된 메모리를 해제한 후 종료한다.
결과 출력: 모든 삽입 정렬 과정을 마쳤음에도 count가 K보다 작으면 -1을 출력하고 메모리를 해제한다.

Python 코드와 설명

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    count = 0 # 저장 연산의 횟수를 세기 위한 카운터
    
    # 삽입 정렬을 수행한다.
    for i in range(1, N):
        newItem = A[i] # 현재 삽입할 원소
        loc = i - 1 # 삽입할 위치를 찾기 위한 인덱스
        
        # newItem보다 큰 원소를 오른쪽으로 이동시킨다.
        while loc >= 0 and A[loc] > newItem:
            A[loc + 1] = A[loc] # 원소를 오른쪽으로 이동
            count += 1 # 저장 연산 카운트
            if count == K:
                print(A[loc])
                return
            loc -= 1
        
        # newItem을 적절한 위치에 삽입한다.
        if loc + 1 != i:
            A[loc + 1] = newItem
            count += 1 # 저장 연산 카운트
            if count == K:
                print(newItem)
                return
    
    # 저장 횟수가 K보다 작으면 -1을 출력
    print(-1)

if __name__ == "__main__":
    main()

코드의 동작 단계별 설명

입력 처리: 표준 입력을 통해 배열의 크기 N과 저장 횟수 K를 입력받고, 배열 A의 원소들을 리스트로 저장한다.
삽입 정렬 시작: 두 번째 원소부터 시작하여 배열을 정렬해 나간다.
원소 이동 및 저장 연산 카운트:
- 현재 삽입할 원소 newItem을 설정하고, 이전 원소들과 비교하면서 newItem보다 큰 원소를 오른쪽으로 이동시킨다.
- 원소를 이동시킬 때마다 저장 연산이 발생하므로 count를 증가시킨다.
- 만약 count가 K와 같아지면 현재 저장된 값을 출력하고 프로그램을 종료한다.
원소 삽입: 적절한 위치를 찾았다면 newItem을 삽입하고, 이 또한 저장 연산이 발생하므로 count를 증가시킨다. K와 같아지면 값을 출력하고 종료한다.
결과 출력: 모든 삽입 정렬 과정을 마쳤음에도 count가 K보다 작으면 -1을 출력한다.

결론

백준의 “알고리즘 수업 - 삽입 정렬 1” 문제는 삽입 정렬의 기본적인 동작 방식을 이해하고, 이를 정확히 시뮬레이션할 수 있는지를 평가하는 문제였다. 삽입 정렬의 각 단계에서 발생하는 저장 연산을 세는 과정을 통해 문제를 해결할 수 있었으며, 이를 통해 정렬 알고리즘의 세부 동작을 더욱 명확히 이해할 수 있었다.

이번 문제를 풀면서 시뮬레이션을 정확히 구현하는 것이 중요함을 다시 한 번 깨달았다. 또한, 효율적인 코드 작성을 통해 시간 복잡도를 관리하는 것도 중요한 요소임을 확인할 수 있었다. 추가적인 최적화 방안으로는 불필요한 조건 검사나 반복을 줄이는 방법을 고려할 수 있으며, 특히 큰 입력에 대해서도 안정적으로 동작할 수 있도록 코드를 작성하는 것이 필요하다.

삽입 정렬은 비록 시간 복잡도가 O(N²)이지만, 작은 크기의 데이터나 거의 정렬된 데이터에 대해서는 효율적으로 동작할 수 있는 유용한 알고리즘임을 재확인할 수 있었다. 앞으로도 다양한 정렬 알고리즘을 학습하고, 상황에 맞는 최적의 알고리즘을 선택하여 문제를 해결하는 능력을 키워나가야겠다.