궤도

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이 문제랑 똑같이 접근할 것이다. 위 문제에서는 LIS 수열을 만들고, 새로운 입력에 대해 LIS 수열의 마지막 원소부터 0번째 원소까지 이동하며 하나하나 비교하며 원소가 들어갈 위치를 찾아줬다. 이 부분에 대한 시간 복잡도는 O(n)이다. 만약 새로운 입력의 위치를 찾아주는 과정을 이분 탐색으로 하면 시간 복잡도가 O(logn)이 될 것이다. 새..