lis4 [백준/13711/C] LCS 4 필독 : https://eigenarea.tistory.com/58 [백준/12015/C] 가장 긴 증가하는 부분 수열 2필독 : https://eigenarea.tistory.com/52 [백준/11053/C] 가장 긴 증가하는 부분수열처음에 문제를 보고 알고리즘을 생각하면 머리가 멍할 수도 있다. 문제 태그가 dp니까 생각해볼 수 있는 알고리즘은 주어eigenarea.tistory.com 문제에 제시된 수열의 길이가 무려 100,000이다. 이는 일반적인 n차원 배열 LCS알고리즘으로는 절대 해결할 수 없음을 의미한다. 그래서 이런 아이디어를 사용해보자 : A와 B의 배열은 모두 서로 같은 원소를 가진 서로 다른 배열이다. 즉, B는 A의 재배열이다.그러므로 B의 원소들을 A에서의 인덱스들로 저장해서.. 2025. 6. 22. [백준/14003/C] 가장 긴 증가하는 부분 수열 5 필독 : https://eigenarea.tistory.com/58 [백준/12015/C] 가장 긴 증가하는 부분 수열 2필독 : https://eigenarea.tistory.com/52 [백준/11053/C] 가장 긴 증가하는 부분수열처음에 문제를 보고 알고리즘을 생각하면 머리가 멍할 수도 있다. 문제 태그가 dp니까 생각해볼 수 있는 알고리즘은 주어eigenarea.tistory.com 앞선 포스팅에서의 이분탐색에 대한 아이디어에 더해 이번에는 역추적 알고리즘을 구현해볼 것이다.일단 구해준 res는 실제 LIS가 될 수 없음은 너무 자명하다. 그저 크기만 보존해줄 수 있을 뿐, LIS의 정보를 보존해주지 못한다. 따라서 우리는 이러한 아이디어를 이용해보려고 한다 :-(length는 res리스트의 .. 2025. 6. 21. [백준/12015/C] 가장 긴 증가하는 부분 수열 2 필독 : https://eigenarea.tistory.com/52 [백준/11053/C] 가장 긴 증가하는 부분수열처음에 문제를 보고 알고리즘을 생각하면 머리가 멍할 수도 있다. 문제 태그가 dp니까 생각해볼 수 있는 알고리즘은 주어진 수열에서 1,2,3,..로 길이가 제한된 수열에서의 LIS라는 부분문제를 풀eigenarea.tistory.com 이 문제는 저번 문제와 다르게 주어지는 수열의 크기가 굉장히 크다 (O(n^2))으로는 무리가 있다.그래서 이분탐색을 진행해주어야하는데, 전반적인 알고리즘의 개요는 이러하다. res[i]는 길이가 i+1인 증가수열 중에 끝이 가장 작은 수열의 끝이다.res를 유도하기 위해서는 리스트를 순차적으로 탐색해나가면서 만약 숫자 arr[j]이 res의 가장 뒤의 숫자.. 2025. 6. 21. [백준/11053/C] 가장 긴 증가하는 부분수열 처음에 문제를 보고 알고리즘을 생각하면 머리가 멍할 수도 있다. 문제 태그가 dp니까 생각해볼 수 있는 알고리즘은 주어진 수열에서 1,2,3,..로 길이가 제한된 수열에서의 LIS라는 부분문제를 풀고, 만약에 그게 지금 위치의 전까지에서의 최선이라면 지금 위치의 값은 최선의 값+1이다. 이렇게 생각하면 시간복잡도가 O(n^2)이지만 이 문제는 수의 크기가 작기 때문에 괜찮다.+)부분문제의 수열을 초기화하는걸 까먹지 않도록하자 (절대로 내가 그거땜에 틀려서 하는말은 아니다..!) #include int main(){ int N,max=1; scanf("%d",&N); int arr[N],dp[N]; for(int i=0; iarr[j] && dp[i]max) max = dp[i]; .. 2025. 5. 30. 이전 1 다음 반응형