[엘카데미 챌린지] 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일차 챌린지를 완료하였고, 챌린지 종료까지도 이제 이틀밖에 안남았지만 종료되더라도 이 공부 습관을 이어가고 싶다.
블로그를 방치한 지 꽤 되었지만, 앞으로는 이 기세를 몰아 꾸준히 자료구조 또는 알고리즘 공부한 내용을 포스팅하려고 한다. 프로젝트같은 경우는 깃허브에 올리게 되겠지만. 알고리즘을 제대로 입문한 것은 처음인데, 수학 문제를 풀듯이 풀었을 때 쾌감이 있어서 재밌는 것 같다. 물론 알고리즘에만 매몰되어서는 안되겠지만 백준 골드를 목표로 차근차근 풀어나가려고 한다.