Chap 2. Divide and Conquer

- Divide and Conquer의 기본은 Binary search를 예로 들 수 있다(시간복잡도와 call-by-value)

- Merge sort 또한 Divide and conquer(계속 반으로 갈라서 한 개가 되면 크기 비교하며 합치기)

- online은 실시간으로 넣는것(hash), offline은 input 다 넣고 처리

- inplace sort는 배열 제자리에서 처리하는가, stable은 같은 값들을 위치 조정하지 않는가

- stable은 특히 주의 깊게 보기(stable이 좋긴 하지만 실제 제약과 소모값이 있어서 unstable이 빠르긴함)

- quick sort 또한 Divide and conquer(pivot 기준으로 ++와 -- 하면서 비교하기)

- quick sort가 빠른 이유는 register에 피벗 하나만 올리고 다음 값들과 비교하기 때문이다

- quick의 함수 stack이 많이 쌓이는 문제 해결하기 위해 범위가 작은 피벗 부분부터 먼저 처리(random 처리도 가능)

- Strassen's Matrix Multiplication 은 기존 mult 8/ add 4 에서 mult 7/ add 18 로 mult를 줄일 수 있었다

- arithmatic with large integers 문제