[BOJ_11053 | DP] 가장 긴 증가하는 부분 수열

풀이 가장 긴 증가하는 부분 수열을 구하는 문제는 다이나믹 프로그래밍을 이용하여 해결해야 한다.arr 배열에는 입력받은 input data의 값, 즉 수열의 값들을 저장하고dp 배열에는 그 숫자보다 작은 증가하는 부분 수열의 최대 길이를 저장한다. 예를들어 n = 9 인 데이터가 다음과 같이 들어온다고 가정하자. 10, 15, 40, 20, 15, 50, 35, 80, 100 이 상황에서 arr[0] ~ arr[8]까지의 값은 각각 위의 값을 순서대로 저장할 것이다.그리고 이중 포문을 돌면서 (데이터의 개수가 더 클 때에는 O(NlogN)의 시간복잡도를 갖는 알고리즘을 사용해도 된다.)각각의 인덱스에서 그 인덱스보다 작은 최장 부분 수열의 길이+1 의 값을 dp 배열의 값으로 저장하는 것이다. 10의 d..

2019.02.01