[알고리즘] LIS - 최장 증가 부분 수열(dp,이진탐색,수열 복원)
LIS (최장 증가 부분 수열: Longest Increasing Subsequence)LIS란 최장 증가 부분 수열로 어떤 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 의미한다.여기서 부분 수열이란 원소의 순서를 유지한 채, 일부 원소를 골라 만든 수열이다.수열: [10, 20, 10, 30, 20, 50]LIS: [10, 20, 30, 50] → 길이 4구현 방법일반적으로 DP와 이진 탐색을 이용해서 구현할 수 있다.DP: O(n²)이진 탐색: O(n log n)DP로 구현하기int[] dp = new int[n];Arrays.fill(dp, 1); // 최소 길이 1for (int i = 0; i i 번째 까지 반복하면서 이전 인덱스 j 들을 확인한다.arr[i]가 arr..
2025. 4. 21.