Devvy-Is-Free

🎵오늘의 띵곡🎵 After LIKE 아티스트 IVE (아이브) 앨범 After LIKE 발매일 2022.08.22 최장 증가 부분 수열(LIS : Longest Increasing Subsequence) - 동적 계획법 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만듦 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열 첫 번째 방법 시간 복잡도 : O(N^2) 원본 배열 A, 새로운 배열 B 선언 int A[8] = {3, 5, 7, 9, 2, 1, 4, 8}; B[i] : A [i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이 i = 0 A[0] = 0 , B[0] = 0 i 0 1 2 3 4 5 6 7 8 A 0 3 5 7..