기본적인 DP문제로 "가장 긴 증가하는 수열"의 크기를 구하는 것과 똑같다.
그래서 굳이 포스팅하지 않으려고 했는데 어떤 분이 큰 폭으로 실행 시간을 단축시켜 분석하고자 포스팅하게 되었다.
먼저 DP에 대해서 생각해보면 DP는 for문이 두 개 배치되며 O(n^2)의 시간 복잡도를 가지게 된다.
단순 "구현"으로 문제를 해결한 건가?
이 코드로 문제를 해결한 근본적인 의미는? ... 구현으로 찍어 누른듯
전체적인 flow는 기존의 긴 리스트를 유지하면서 더 작은 값을 만난다면 list내에서 적절한 위치를 찾아 change한다.
이렇게 생각할 수 있는 thinking도 필요할 듯하다.
세상은 너무나도 커