Today I learned
2022/02/01
회고록
2/01
항해 99, 알고리즘 3주차
교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)
병합/퀵정렬(Sort)
1. 이론
퀵정렬
퀵 정렬(quick sort) 알고리즘의 구체적인 개념
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
퀵 정렬은 다음의 단계들로 이루어진다.
분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
병합정렬
합병 정렬(merge sort) 알고리즘의 구체적인 개념
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
합병 정렬은 다음의 단계들로 이루어진다.
분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
합병 정렬의 과정
추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.
2. 문제
문제 설명
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Input: head = [4,2,1,3]
Output: [1,2,3,4]https://leetcode.com/problems/merge-intervals/
3. MySol
- merge intervals
def mergeSort(arr):
arr = sorted(arr, key=lambda x: x[0])
result = []
i=0
while i<len(arr):
temp = []
if i==len(arr)-1:
result.append(arr[i])
break
if arr[i][1]>=arr[i+1][0]:
temp = [arr[i][0], arr[i+1][1]]
result.append(temp)
i+=1
else:
result.append(arr[i])
i+=1
return result
if __name__ == '__main__':
n = [[1,3],[2,6],[8,10],[15,18]]
result = mergeSort(n)
print(f'result: {result}')
4. 배운 점
- 구간 병합문제
- 일찍이 풀고 좀 쉬운가..? 훗 했다가, 해당 블로그를 정리하면서 리트코드에 넣었더니 통과가 되지 않는다... 하
5. 총평
퀵소트, 머지소트 구현 및 이해
