알고리즘을 좋아하는 나

N은 약수의 처음 주어진 숫자와 마지막 숫자를 곱해주면 나온다.

예를 들어 9가 N이면

3 이 약수로 있다.

그러면 3 * 3 = 9

20 이면

2 4 5 10

2 * 10 = 20 

20 은 2 * 2 * 5 로 소인수 분해가 된다.

2 와 10

Quick Sort는

최악의 경우 n^2

평균 nlgn

퀵 정렬의 내부 루프는 컴퓨터 아키텍쳐에서 효율적으로 작동되도록 설계되어 있다.

(메모리 참조가 지역화되어 있기 때문에 CPU캐시의 히트율이 높다.)

핵심만 정리하자면

pivot의 왼쪽엔 pivot보다 작은값

pivot의 오른쪽엔 큰값

do

if arr[i] > pivot && arr[j] < pivot // i와 j는 알아서 증가한다고 가정

swap arr[i++], arr[j--]

while(i <= j)

if(left < j) quickSort(arr, left, j)

if(right > i) quickSort(arr, i, right)

5
0 4
1 2
1 -1
2 2
3 3

1 -1
1 2
2 2
3 3
0 4

y를 오름차순으로 정렬하는데, y가 같으면 x의 오름차순으로 정렬하는 문제.

quick sort를 사용하면 nlgn인데,

y, x를 둘다하게되면

시간초과여서

꼼수를 부렸다.