반응형 lis2 [백준/C++] LCS 4 (No. 13711) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 LCS를 찾는 문제인데, 특이한 조건이 있다.바로 수열의 크기 N이 주어지면 1~N의 숫자를 가진 순서가 다른 수열이 2개 주어진다는 것이다. 만약 이 조건을 대충 넘기고 그냥 풀게 되면 조건으로 주어지는 N이 10만이므로 일반적인 LCS로 문제를 풀게되면 O(N^2)으로 시간초과가 나게 될 것이다. 이제 어떻게 하면 O(N^2)보다 빠르게 문제를 풀 수 있을지 생각해보자. 잘 생각해보면 1~N의 숫자가 2개의 수열에 한 번만 등장하기 때문에 하나의 수열의 i번째 index가 다른 수열의 몇 번째 자리에.. 2024. 5. 26. [백준/C++] 가장 긴 증가하는 부분 수열 5 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 예전에 풀었던 가장 긴 증가하는 부분수열(LIS) 문제와 비슷하다" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 단지 차이점이 있다면, 수열의 크기가 크다는 것과 가장 긴 증가하는 부분 수열이 무엇인지 출력을 해야한다는 것이다. 부분 수열의 길이를 구하는 것은 쉽지만, 이 부분수열이 어떻게 이루어져있는지를 구하기 위해서는 기록이 필요하다. 그러면 어떤 방식으로 기록을 해 문제를 해결했는지 아래 그림을 따라 진행하며 알아보자. 먼저 {1,3,5,2,4,5,3} 인 수열이 있다면 .. 2024. 5. 7. 이전 1 다음 반응형
