분할정복

0. Intro- 이번 7 챕터에서는 quicksort, 퀵정렬에 대해서 알아보고자 한다. 1. Quicksort(퀵정렬)- quicksort(퀵정렬)은 2-3에서 배웠던 mergesort(병합정렬)과 비슷하다.- divide-and-conquer(분할정복)알고리즘을 이용한다.- 평균적으로 매우 빠른 수행 속도를 보여주기 때문에 quicksort 라고 불린다. 2. Quicksort의 알고리즘 - QuickSort의 핵심은 분할(divide)하는 과정이다. - QuickSort는 배열을 작은 부분으로 쪼개서 정렬하는 방식으로 작동하며, 다음과 같은 과정을 거친다. i) Pivot 선택- 배열에서 임의의 기준이 되는 Pivot 요소를 선택한다.- Pivot을 선택하는 방식은 크게 4가지가 존재한다. a) ..

1. Review- 분할 정복(Divide & Conquer)중 하나인 Strassen Algorithm에 대해서 알아보자.- 우리는 앞서 4-1 에서 행렬곱을 계산하는 알고리즘에 대해서 알아보았다.- 이때 코드를 다시한번 바라봐보자.A = [[1,2],[3,4]]B = [[5,6],[7,8]]C = [[0,0],[0,0]]for i in range(2): for j in range(2): for k in range(2): C[i][j] += A[i][k]*B[k][j]C------------------------------------------------------[[19, 22], [43, 50]]- 이를 시간 복잡도로 표현하면 O(n^3)과 같다.- 그 이유는 ..