[패스트캠퍼스 :: 코딩테스트 인강] 7주차 ② 병합정렬

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

고급 정렬 알고리즘 - 03. 병합 정렬 - 2

고급 정렬 알고리즘 - 04.병합 정렬 - 3

고급 정렬 알고리즘 - 05.병합 정렬 - 4

---

 

2021.04.04

역대급으로 짧았던 강의

공채 시즌에 지쳐가던 중 잠시 쉬어가는 강의 느낌이었다.

 

파이팅

 

---

 

병합 정렬의 이해가 어려울 수 있는데,

이 부분은 아래 링크에서 보면 이해가 쉽다.

 

 

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

다양한 알고리즘을 시각적으로 표현해주는데, 

눈으로 잘 따라가면 이해가 훨씬 수월하다.

 

 

 

알고리즘 이해

• 데이터가 네 개 일 때 (데이터 개수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
  • 예: data_list = [1, 9, 3, 2]
    • 먼저 [1, 9], [3, 2]로 나누고
    • 다시 앞부분은 [1], [9]로 나누고
    • 다시 정렬해서 합친다. [1, 9]
    • 다음 [3, 2]는 [3], [2]로 나누고
    • 다시 정렬해서 합친다 [2, 3]
    • 이제 [1, 9]와 [2, 3]을 합친다.
      • 1 < 2이니 [1]
      • 9 > 2 이니 [1, 2]
      • 9 > 3이니 [1, 2, 3]
      • 9 밖에 없으니, [1, 2, 3, 9]

 

 

 

알고리즘 구현

• mergesplit 함수 만들기
  • 만약 리스트 개수가 한 개이면 해당 값 리턴
  • 그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기
  • left = mergesplit(앞)
  • right = mergesplit(뒤)
  • merge(left, right)
• merge 함수 만들기
  • 리스트 변수 하나 만들기 (sorted)
  • left_index, right_index = 0
  • while left_index < len(left) or right_index < len(right):
    • 만약 left_index 나 right_index 가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
    • if left [left_index] < right[right_index]:
      • sorted.append(left[left_index])
      • left_index += 1
    • else:
      • sorted.append(right[right_index])
      • right_index += 1

 

(강사님의 수업 방식이 좋은 점 중 하나는 이렇게, 로직을 이해할 수 있도록 정리하고, 각 부분에 맞는 코드를 구현하는 것이다.)

 

 

재귀 용법 활용하기

 

def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

 

 

 

알고리즘 분석

• 알고리즘 분석은 쉽지 않음, 이 부분은 참고로만 알아두자.
  • 다음을 보고 이해해보자
    • 몇 단계 깊이까지 만들어지는지를 depth라고 하고 i로 놓자. 맨 위 단계는 0으로 놓자.
      • 다음 그림에서 n/2222는 2단계 깊이라고 해보자.
      • 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/2222 가 된다.
      • 각 단계에는 2𝑖2i 개의 노드가 있다.
    • 따라서, 각 단계는 항상 2𝑖∗𝑛2𝑖=𝑂(𝑛)2i∗n2i=O(n)
    • 단계는 항상 𝑙𝑜𝑔2𝑛log2n 개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
    • 따라서, 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

 

 

 

 

 

정렬 알고리즘에 들어오고 나서는 시간 복잡도가 아주 중요하게 작용하는 느낌이다.

 

코딩 테스트뿐만 아니라 다양한 소프트웨어 개발에서도 속도는 항상 중요한 것이기 때문인 거겠지.

 

 

 

---

 

 

이제 챌린지도 어느새 절반을 지나 후반으로 달려가고 있다.

바쁜 시기가 찾아오면서 점점 강의에 지치기도 하고,

우선순위에서 밀려 주말 학습이 많아지고 있지만

그래도 끝까지 해내고 싶다.

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스