BAEKJOON_11053) 가장 긴 증가하는 부분 수열

BAEKJOON 

# 알고리즘 기초 # 2019 SW역량테스트준비-기초

# 다이나믹 프로그래밍 

11053) 가장 긴 증가하는 부분 수열 (19.03.20) (19.09.29)

* 처음에는 값 크기 생각 안하고, ans[cass-1] 을 출력해서,
* 두번째는 q=0로 두어서 틀렸었다.

* 강의 들을 때 문제가 이해가 안돼서 일단 다 듣고 넘겼는데,
* 문제 풀이를 하면서 알 수 있었다.

* i 번째에 해당하는 수가 마지막이라고 했을 때,
* 앞선 0번째부터 i-1번째 수들을 다 탐색해서 걸러내야 했다.

* 따라서
* 총 n 개 칸, 한 칸을 채울 때 n 개를 봐야 하기 때문에
* 시간복잡도는 n*O(n) = O(n^2)