파이썬 코딩테스트 강좌, 선택 정렬

알고리즘 문제 해결 능력을 키우는 것은 프로그래밍 여정에서 매우 중요합니다. 특히, 취업 면접이나 코딩 테스트에서는 기초적인 알고리즘에 대한 이해가 필요합니다. 이번 글에서는 선택 정렬(Selection Sort) 알고리즘에 대해 알아보고, 이를 활용한 문제를 해결하는 과정을 상세히 설명하겠습니다.

선택 정렬이란?

선택 정렬은 주어진 리스트에서 가장 작은(또는 가장 큰) 값을 찾아 맨 앞에 위치시키고, 그 다음 위치에서 같은 과정을 반복하는 단순한 정렬 알고리즘입니다. 선택 정렬은 다음과 같은 과정으로 진행됩니다:

리스트에서 가장 작은 요소를 찾습니다.
그 요소를 리스트의 첫 번째와 바꿉니다.
첫 번째 요소를 제외한 나머지 요소에 대해 위의 과정을 반복합니다.

선택 정렬의 시간 복잡도는 O(n²)로, n은 리스트의 길이를 의미합니다. 이 알고리즘은 list가 작을 때는 잘 작동하지만, 큰 데이터셋에서는 성능이 저하될 수 있습니다.

문제 설명

다음과 같은 문제를 풀어보겠습니다:

문제: 정수로 구성된 리스트가 주어질 때, 선택 정렬 알고리즘을 이용하여 이 리스트를 오름차순으로 정렬하시오.

입력:

정수 n (1 ≤ n ≤ 1000): 리스트의 길이
리스트: 공백으로 구분된 n개의 정수

출력:

오름차순으로 정렬된 리스트를 출력한다.

문제 해결 과정

1단계: 입력 및 초기화

문제를 해결하기 위해 필요한 입력을 받아야 합니다. 파이썬에서는 input() 함수를 사용하여 입력을 받을 수 있습니다. 이후 입력받은 값을 리스트 형태로 변환합니다.

n = int(input("리스트의 길이를 입력하세요: "))
arr = list(map(int, input("정수 리스트를 입력하세요: ").split()))

2단계: 선택 정렬 구현

선택 정렬 알고리즘을 구현하기 위해 두 개의 반복문을 사용합니다. 첫 번째 반복문은 정렬되지 않은 부분의 시작을 나타내고, 두 번째 반복문은 그 구역 내에서 가장 작은 요소를 찾습니다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 현재 위치에서 가장 작은 요소의 인덱스 초기화
        min_index = i
        # 현재 위치 이후의 요소 중에서 최솟값 찾기
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 찾은 최솟값을 현재 위치와 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

3단계: 결과 출력

정렬이 완료된 리스트를 출력합니다. 방법은 print() 함수를 사용하여 간단히 구현할 수 있습니다.

sorted_arr = selection_sort(arr)
print("오름차순으로 정렬된 리스트는 다음과 같습니다:")
print(sorted_arr)

전체 코드

def selection_sort(arr):
    n = len(arr)
    # 리스트의 각 요소에 대해 반복
    for i in range(n):
        # 현재 위치에서 가장 작은 요소의 인덱스 초기화
        min_index = i
        # 현재 위치 이후의 요소 중에서 최솟값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 찾은 최솟값을 현재 위치와 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 리스트의 길이를 입력받고, 리스트 요소를 입력받기
n = int(input("리스트의 길이를 입력하세요: "))
arr = list(map(int, input("정수 리스트를 입력하세요: ").split()))

# 선택 정렬 수행
sorted_arr = selection_sort(arr)

# 결과 출력
print("오름차순으로 정렬된 리스트는 다음과 같습니다:")
print(sorted_arr)

복잡도 분석

선택 정렬의 시간 복잡도는 O(n²)입니다. 이 때문에 큰 데이터셋에서 선택 정렬을 사용하는 것은 비효율적일 수 있습니다. 하지만 선택 정렬은 구현이 간단하고 초기 교육 목적으로는 유용할 수 있습니다.

결론

이번 글에서는 선택 정렬 알고리즘을 기반으로 한 문제를 해결하는 과정을 자세히 살펴보았습니다. 선택 정렬을 이해하고 구현함으로써 알고리즘에 대한 기초적인 이해를 높이는 데 도움이 되셨기를 바랍니다. 다음 글에서도 유익한 알고리즘 주제를 다룰 예정이니 많은 기대 부탁드립니다!