1. 퀵소트


소트돌리고 값 비교하다가 왜 틀렸지 ㅅㅂ 하다가
1 4 3 2 같은 경우가 있다는걸 깨달음. 그래서 그냥 정의에 충실하게 배열 2개 만들어서 비교했음.


2. 메모장


N^2 DP
핵심은 메모장이 있을 수 있는 경우가 2가지만 있음. 선에 걸치거나 위의 메모장에 딱 달라 붙어있거나
(참고) 기출임 https://www.acmicpc.net/problem/14752
N log N으로 줄일수도 있는데 귀찮아


3. 바이토닉


Monotonic Shortest Path라는 유명한 문제임. 설명하기 귀찮으니까 SO 링크로 대체
https://stackoverflow.com/questions/22876105/find-a-monotonic-shortest-path-in-a-graph-in-oe-logv


4. 지진


LIS


5. 히스토그램


O(N). 앞으로 나아가면서 값이 커지면 상관없고 값이 작아지면 전 그룹이랑 합쳐서 평균을 냄
잘 생각해보면 이게 최선임을 알 수 있음.