[파이썬] 백준 23968 알고리즘 수업 버블 정렬 1

이번 글에서는 버블 정렬(Bubble Sort) 알고리즘을 학습하고,

이를 활용하여 백준 23968번 문제를 Python으로 해결하는 방법을 살펴본다. 🚀

 

1. 버블 정렬(Bubble Sort)이란?

 

📌 개념

 

버블 정렬은 서로 인접한 두 개의 값을 비교하여 정렬하는 방식이다.

정렬이 완료될 때까지 이 과정을 반복하여 배열을 정렬한다.

 

🔹 버블 정렬의 특징

• 시간 복잡도: 최선 O(n), 평균·최악 O(n²)
• 장점: 코드가 단순하여 구현이 쉬움
• 단점: 성능이 낮아 큰 데이터 정렬에는 부적합

🔹 정렬 방식

• 오름차순 정렬: a > b → swap(교환)
• 내림차순 정렬: a < b → swap(교환)

2. 버블 정렬 예제 (오름차순 정렬)

 

다음과 같은 리스트가 있다고 가정해본다.

A = [4, 6, 5, 1, 3, 2]

 

이 리스트를 버블 정렬하면 다음과 같이 진행된다.

[4, 6, 5, 1, 3, 2]  →  6과 5 비교 → swap
[4, 5, 6, 1, 3, 2]  →  6과 1 비교 → swap
[4, 5, 1, 6, 3, 2]  →  6과 3 비교 → swap
[4, 5, 1, 3, 6, 2]  →  6과 2 비교 → swap
[4, 5, 1, 3, 2, 6]  →  5와 1 비교 → swap
[4, 1, 5, 3, 2, 6]  →  5와 3 비교 → swap
[4, 1, 3, 5, 2, 6]  →  5와 2 비교 → swap
[4, 1, 3, 2, 5, 6]  →  4와 1 비교 → swap
[1, 4, 3, 2, 5, 6]  →  4와 3 비교 → swap
[1, 3, 4, 2, 5, 6]  →  4와 2 비교 → swap
[1, 3, 2, 4, 5, 6]  →  3과 2 비교 → swap
[1, 2, 3, 4, 5, 6]  →  정렬 완료 ✅

 

3. 백준 23968번 문제 설명

 

🔗 문제 링크: 백준 23968 - 알고리즘 수업: 버블 정렬 1

백준 23968

📌 문제 요구사항

• N: 배열 A의 크기 (5 ≤ N ≤ 10,000)
• K: K번째 교환된 두 개의 수를 출력 (1 ≤ K ≤ N²)
• K번째 교환이 발생하지 않으면 -1을 출력

4. 버블 정렬 구현 및 교환 과정 분석

 

🔹 정렬 진행 과정

배열 [4, 6, 5, 1, 3, 2]을 버블 정렬로 정렬하며 교환이 발생한 횟수를 확인한다.

 

소스 내 변경 이력

 

1️⃣ 10번째 교환된 두 개의 값

2 4

 

2️⃣ 12번째 교환이 발생하지 않으면 -1 출력

 

5. Python 코드 구현

import sys

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

def bubble_sort(lst, K):
    cnt = 0  # 교환 횟수 카운트

    # 버블 정렬 수행
    for i in range(len(lst), 0, -1):
        for j in range(i - 1):
            # 두 수 비교 후 정렬
            if lst[j] > lst[j + 1]:
                cnt += 1
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

                # K번째 교환이 발생하면 작은 값부터 출력
                if cnt == K:
                    print(min(lst[j], lst[j + 1]), max(lst[j], lst[j + 1]))
                    return

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

# 함수 실행
bubble_sort(A, K)

 

6. 예제 입력 & 출력

 

✅ 예제 1

입력:
6 10
4 6 5 1 3 2

출력:
2 4

 

✅ 예제 2

입력:
6 12
4 6 5 1 3 2

출력:
-1

 

7. 코드 설명

 

🔹 입력 받기

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

• N: 배열의 크기
• K: K번째 교환이 발생한 두 개의 값 출력
• A: 정렬할 배열

🔹 버블 정렬 로직

for i in range(len(lst), 0, -1):
    for j in range(i - 1):

• i: 현재 탐색하는 배열 크기 (뒤쪽 정렬된 부분 제외)
• j: 인접한 두 값 비교

🔹 값이 크면 swap + 교환 횟수 증가

if lst[j] > lst[j + 1]:
    cnt += 1
    lst[j], lst[j + 1] = lst[j + 1], lst[j]

• cnt: 교환 횟수
• lst[j] > lst[j + 1]이면 swap

🔹 K번째 교환이 발생하면 작은 값부터 출력 후 종료

if cnt == K:
    print(min(lst[j], lst[j + 1]), max(lst[j], lst[j + 1]))
    return

 

🔹 K번 교환이 일어나지 않으면 -1 출력

print(-1)

 

8. 마무리

 

이번 글에서는 버블 정렬(Bubble Sort) 알고리즘을 이해하고,

백준 23968번 문제를 Python으로 해결하는 방법을 알아봤다. 🚀

 

📌 정리

✅ 버블 정렬은 **O(n²)**의 시간 복잡도를 가짐

✅ K번째 교환된 두 개의 값을 작은 순서대로 출력

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