[알고리즘] 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.
[c++ STL]vector sort() 함수와 compare 함수
vector sort() 함수 vector vec sort(vec.begin(),vec.end()); #include 헤더파일을 추가하면 사용 할 수있다. 기본적으로 vector에서 sort() 함수는 다음과 같이 사용된다. 디폴트로 오름차순으로 정렬이 된다 (1,2,3,4,5) vector sort() 내림차순 sort(vec.begin(),vec.end(),greater()); 다음과 같이 greater()을 추가해주면 내림차순으로 정렬 할 수있다.(5,4,3,2,1) compare 인자 sort(vec.begin(), vec.end(), compare); greater()과 같이 compare를 추가해주면 sort 함수를 변형 할 수 있다.(compare()이 아닌 compare 이다.) 예시 ve..
2023. 4. 11.
