[파이썬] 백준 24051 알고리즘 수업 삽입 정렬 1

이번 글에서는 삽입 정렬(Insertion Sort) 알고리즘을 배우고,

이를 활용하여 백준 24051번 문제를 Python으로 해결해본다. 🚀

 

1. 삽입 정렬(Insertion Sort) 이란?

 

삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘이다.

 

🔹 삽입 정렬의 특징

• 선택 정렬(Selection Sort), **버블 정렬(Bubble Sort)**보다 빠르고 안정적인 정렬 알고리즘

• 최선의 경우 O(n), 최악의 경우 O(n²)

• 데이터가 거의 정렬되어 있을 경우 매우 효율적

 

🔹 삽입 정렬 과정

예제 배열: [4, 5, 1, 3, 2]

 

1️⃣ 1을 정렬된 부분과 비교하여 삽입

[4, 5, 1, 3, 2]  →  1을 0번 인덱스에 삽입  
[1, 4, 5, 3, 2]

 

2️⃣ 3을 정렬된 부분과 비교하여 삽입

[1, 4, 5, 3, 2]  →  3을 적절한 위치에 삽입  
[1, 3, 4, 5, 2]

 

3️⃣ 2를 정렬된 부분과 비교하여 삽입

[1, 3, 4, 5, 2]  →  2를 적절한 위치에 삽입  
[1, 2, 3, 4, 5]

 

✅ 정렬 완료

 

2. 백준 24051번 문제 설명

 

🔗 문제 링크: 백준 24051 - 알고리즘 수업: 삽입 정렬 1

백준 24051 삽입정렬

📌 문제 요구사항

• N: 배열 A의 크기 (5 ≤ N ≤ 10,000)
• K: 삽입 정렬 과정에서 K번째 저장되는 값을 출력 (1 ≤ K ≤ N²)
• 만약 K번째 저장이 발생하지 않으면 -1을 출력

3. 삽입 정렬 구현 및 변경 과정 분석

 

🔹 삽입 정렬 진행 과정

 

배열이 [4, 5, 1, 3, 2]일 때, 정렬 과정에서 값이 저장되는 모습을 살펴본다.

 

소스 내 값 변경 이력

 

1️⃣ newItem = 1

[4, 5, 5, 3, 2]
[4, 4, 5, 3, 2]  ← while 문 실행
[1, 4, 5, 3, 2]  ← if 문 실행

 

2️⃣ newItem = 3

[1, 4, 5, 5, 2]
[1, 4, 4, 5, 2]  ← while 문 실행
[1, 3, 4, 5, 2]  ← if 문 실행

 

3️⃣ newItem = 2

[1, 3, 4, 5, 5]
[1, 3, 4, 4, 5]
[1, 3, 3, 4, 5]  ← while 문 실행
[1, 2, 3, 4, 5]  ← if 문 실행

 

🔹 최종 결과:

[1, 2, 3, 4, 5]

 

4. Python 코드 구현

import sys

# 배열 A의 크기 N, 저장 횟수 K 입력받기
N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

def insertion_sort(lst, K):
    cnt = 0  # 저장 횟수 카운트

    # 삽입 정렬 수행
    for i in range(1, len(lst)):
        loc = i - 1
        newItem = lst[i]

        # 왼쪽 정렬된 부분과 비교하며 이동
        while loc >= 0 and newItem < lst[loc]:
            cnt += 1
            lst[loc + 1] = lst[loc]  # 값 이동
            loc -= 1

            # K번째 저장이 발생하면 출력 후 종료
            if cnt == K:
                print(lst[loc + 1])
                return

        # 새로운 위치에 삽입
        if loc + 1 != i:
            cnt += 1
            lst[loc + 1] = newItem

            # K번째 저장이 발생하면 출력 후 종료
            if cnt == K:
                print(lst[loc + 1])
                return

    # 저장 횟수가 K보다 작으면 -1 출력
    print(-1)

# 함수 실행
insertion_sort(A, K)

 

5. 예제 입력 & 출력

 

✅ 예제 1

입력:
5 7
4 5 1 3 2

출력:
5

 

✅ 예제 2

입력:
5 11
4 5 1 3 2

출력:
-1

 

6. 코드 설명

 

🔹 입력 받기

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

• N: 배열의 크기
• K: K번째 저장되는 값 출력
• A: 정렬할 배열

🔹 삽입 정렬 로직

for i in range(1, len(lst)):
    loc = i - 1
    newItem = lst[i]

• i: 현재 정렬할 원소의 인덱스
• loc: 비교할 위치 (왼쪽 정렬된 부분)
• newItem: 정렬 대상 값

🔹 왼쪽 요소와 비교하며 위치 찾기

while loc >= 0 and newItem < lst[loc]:
    cnt += 1
    lst[loc + 1] = lst[loc]  # 값 이동
    loc -= 1

• while 문을 통해 왼쪽 요소와 비교하며 자리 이동

🔹 K번째 저장 후 즉시 출력

if cnt == K:
    print(lst[loc + 1])
    return

• cnt == K이면 해당 값을 출력하고 함수 종료

 

🔹 마지막까지 K번 저장이 발생하지 않으면 -1 출력

print(-1)

 

7. 마무리

 

이번 글에서는 삽입 정렬(Insertion Sort) 알고리즘을 이해하고,

백준 24051번 문제를 Python으로 해결해 보았다. 🚀

 

📌 정리

✅ 삽입 정렬은 O(n²) 의 시간 복잡도를 가짐

✅ K번째 저장이 발생하면 즉시 해당 값 출력

✅ K번째 저장이 발생하지 않으면 -1 출력