파이썬 코딩테스트 강좌, 삽입 정렬

서론

알고리즘은 코딩 시험에서 매우 중요한 주제 중 하나입니다. 알고리즘을 이해하고 구현할 수 있는 능력은 프로그래밍 및 소프트웨어 개발에 있어 필수적입니다. 본 강좌에서는 삽입 정렬(Insertion Sort) 알고리즘에 대해 심층적으로 학습하고, 관련 문제를 통해 이해도를 높일 것입니다.

삽입 정렬이란?

삽입 정렬은 간단한 정렬 알고리즘으로, 주어진 데이터 집합을 정렬된 리스트와 정렬되지 않은 리스트로 나눈 후, 정렬되지 않은 리스트에서 데이터를 하나씩 꺼내어 정렬된 리스트에 적절한 위치에 삽입하여 정렬하는 방식입니다. 이 알고리즘은 직관적이며 구현이 간단하다는 장점이 있습니다.

삽입 정렬의 작동 원리

삽입 정렬은 다음과 같은 단계를 통해 작동합니다:

두 번째 요소부터 시작하여 각 요소를 현재 요소(C)를 기준으로 비교합니다.
현재 요소(C)가 정렬된 리스트의 이전 요소(A)보다 작으면, 현재 요소(C)를 정렬된 리스트에 올바른 위치에 삽입합니다.
이 과정을 배열의 끝까지 반복하여 최종적으로 정렬된 배열을 얻습니다.

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2), 최선의 경우 O(n), 평균적으로 O(n^2)입니다. 이는 일반적으로 데이터가 거의 정렬된 경우에 효율적입니다. 하지만, 데이터가 무작위로 분포되어 있을 경우에는 성능이 저하될 수 있습니다.

문제: 삽입 정렬 구현하기

다음 문제를 해결해보겠습니다.


문제: 주어진 정수 리스트를 삽입 정렬을 사용하여 정렬하시오.

입력: [5, 2, 9, 1, 5, 6]
출력: [1, 2, 5, 5, 6, 9]

문제 풀이 과정

위 문제를 해결하기 위해 삽입 정렬 알고리즘을 구현해보겠습니다. 아래는 파이썬을 사용하여 삽입 정렬을 구현한 코드입니다.


def insertion_sort(arr):
    # 리스트의 두 번째 요소부터 시작
    for i in range(1, len(arr)):
        key = arr[i]  # 현재 요소
        j = i - 1  # 현재 요소의 이전 인덱스

        # 정렬된 리스트와 비교하여 적절한 위치 찾기
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # 요소를 오른쪽으로 이동
            j -= 1  # 인덱스 감소
        
        arr[j + 1] = key  # 현재 요소를 적절한 위치에 삽입
    return arr

# 예제 리스트
example_list = [5, 2, 9, 1, 5, 6]
sorted_list = insertion_sort(example_list)
print(sorted_list)

코드 설명

위 코드는 다음과 같은 구조로 되어 있습니다:

def insertion_sort(arr): – 삽입 정렬 함수를 정의합니다.
for i in range(1, len(arr)): – 두 번째 요소부터 반복을 시작합니다.
key = arr[i] – 현재 요소를 저장합니다.
while j >= 0 and key < arr[j]: – 정렬된 리스트에서 현재 요소보다 큰 요소를 찾습니다.
arr[j + 1] = arr[j] – 요소를 오른쪽으로 이동하여 자리를 비워줍니다.
arr[j + 1] = key – 현재 요소를 적절한 위치에 삽입합니다.
마지막으로 정렬된 배열을 반환합니다.

삽입 정렬의 장점과 단점

장점

구현이 간단하고 직관적입니다.
데이터가 거의 정렬된 경우 특히 효율적입니다.
제자리 정렬(in-place sorting) 알고리즘이기 때문에 추가 공간을 적게 사용합니다.

단점

시간 복잡도가 O(n^2)로 절대적인 성능이 좋지 않습니다.
데이터가 무작위로 분포된 경우 비효율적입니다.

결론

이번 강좌에서는 삽입 정렬 알고리즘에 대해 알아보았습니다. 삽입 정렬은 간단하면서도 유용한 정렬 알고리즘으로, 코딩 테스트에서 자주 등장할 수 있습니다. 주어진 문제를 해결하기 위해 알고리즘의 원리를 이해하고, 이를 엄밀히 구현하는 연습이 중요합니다. 다음 강좌에서는 또 다른 정렬 알고리즘에 대해 다루어보도록 하겠습니다.

서론