항해99, 4주차 구간병합

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. 총평

퀵소트, 머지소트 구현 및 이해