[엘카데미 챌린지] 19일차 파이썬 알고리즘 (6)

1. 개요

오늘은 병합 정렬 알고리즘과 퀵 정렬 알고리즘 문제를 풀이하였다.

알고리즘을 이제 막 입문하다보니 생각보다 시간이 꽤 걸린 것 같다.

알면 알수록 고려해야할 부분이 굉장히 많은 것 같다.

---

2. 문제

1) 쉽게 설명한 병합 정렬 알고리즘

리스트 a를 매개 변수로 받아 병합 정렬을 하여 리스트 result에 저장해 반환하는 함수 merge_sort를 작성하세요.

 

풀이

병합 정렬을 사용하여 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 알고리즘을 생각해 보면,

1. 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없다.
2. 전체 리스트를 절반으로 나눠 각각 재귀 호출을 통해 병합 정렬을 한다.
3. 두 그룹의 첫 번째 값을 비교하여 작은 값을 빼내 결과 리스트에 넣는 과정을 반복한다.

4. 하나의 리스트의 자료가 모두 사라지면 나머지 리스트의 자료를 모두 결과 리스트에 옮긴다.

def merge_sort(a):
    # 입력 리스트의 길이가 1보다 작거나 같으면 정렬할 필요가 없으므로 그대로 반환
    if len(a) <= 1:
        return a

    # 리스트를 반으로 나누기
    mid = len(a) // 2
    left_half = a[:mid]
    right_half = a[mid:]

    # 반으로 나눈 리스트들을 재귀적으로 병합 정렬
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # 두 정렬된 리스트를 병합하여 결과 리스트를 생성
    return merge(left_sorted, right_sorted)

def merge(left, right):
    # 두 리스트를 병합하여 정렬된 결과 리스트를 생성
    merged = []
    left_idx, right_idx = 0, 0

    # 두 리스트의 원소를 비교하면서 작은 값을 결과 리스트에 추가
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1

    # 남은 나머지 원소들을 결과 리스트에 추가
    merged.extend(left[left_idx:])
    merged.extend(right[right_idx:])
    return merged

# 테스트를 위한 리스트
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(merge_sort(d))

---

2) 쉽게 설명한 퀵 정렬 알고리즘

리스트 a를 매개변수로 받아 퀵 정렬을 하여 정렬된 리스트의 합을 반환하는 함수 quick_sort를 작성하세요.

 

풀이

주어진 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 퀵 정렬 알고리즘을 구현하려면,
1. 리스트에서 기준 값을 하나 정한다.(편의상 정렬할 리스트의 맨 마지막을 기준 값으로)
2. 기준 값보다 작은 값을 저장할 리스트와 큰 값을 저장할 리스트를 만든다.
3. 리스트에 있는 자료들을 기준 값과 차례로 비교하여 작은 값 저장 리스트와 큰 값 저장 리스트로 분리하여 넣는다.
4. 재귀 호출을 이용하여 두 리스트를 정렬하고 작은 값 저장 리스트와 기준 값, 큰 값 저장 리스트 순서대로 붙이면 정렬이 완료 된다.

def quick_sort(a):
    # 기저 조건: 리스트의 길이가 0 또는 1인 경우 정렬할 필요 없음
    if len(a) <= 1:
        return a

    pivot = a[-1]  # 기준 값은 편의상 리스트의 맨 마지막 값으로 설정
    left = []      # 기준 값보다 작은 값을 저장할 리스트
    right = []     # 기준 값보다 큰 값을 저장할 리스트

    # 기준 값과 나머지 값을 비교하여 작은 값은 left에, 큰 값은 right에 넣기
    for num in a[:-1]:
        if num <= pivot:
            left.append(num)
        else:
            right.append(num)

    # 재귀 호출을 이용하여 left와 right를 각각 정렬하고, 기준 값과 함께 합쳐서 정렬된 리스트 반환
    return quick_sort(left) + [pivot] + quick_sort(right)

# 테스트를 위한 리스트 생성
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
sorted_d = quick_sort(d)
print(sorted_d)  # 출력: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

---

3. 후기

19일차 챌린지를 완료하였고, 챌린지 종료까지도 이제 이틀밖에 안남았지만 종료되더라도 이 공부 습관을 이어가고 싶다.

블로그를 방치한 지 꽤 되었지만, 앞으로는 이 기세를 몰아 꾸준히 자료구조 또는 알고리즘 공부한 내용을 포스팅하려고 한다. 프로젝트같은 경우는 깃허브에 올리게 되겠지만. 알고리즘을 제대로 입문한 것은 처음인데, 수학 문제를 풀듯이 풀었을 때 쾌감이 있어서 재밌는 것 같다. 물론 알고리즘에만 매몰되어서는 안되겠지만 백준 골드를 목표로 차근차근 풀어나가려고 한다.