yulee

🤔문제 이해 LCS(longest common sequence)문제로 11053번과 유사하지만 n과 Ai의 크기가 훨씬 큰 버전의 문제이다. 🔥풀이🔥 lower_bound를 이용하면 되는 문제이다. 수열이 저장되어 있는 arr과 가장 긴 부분 수열을 찾아 넣어줄 벡터 v를 선언해주었다 가장 먼저 v에 arr[0] 원소를 넣어주고 arr의 1번째 원소부터 마지막까지 for문을 돌려주었다. for문에서는 v의 가장 마지막 원소보다 arr[i]번째 원소가 더 큰 경우엔 v.push_back(arr[i])를 해주었다. 그렇지 않은 경우는 v에서 arr[i]보다 크거나 같은 원소 중에서 index가 가장 작은 원소의 iterator를 탐색하고 그 위치에 arr[i]를 넣어주었다. 이 부분이 조금 이해가 안되었는데..

🤔문제 이해 i+1번째 수가 i번째 수보다 큰 부분 수열 중에서 가장 긴 수열의 길이를 출력하는 문제이다. 💡첫번째 아이디어 처음엔 부르트 포스가 생각났다. 그냥 눈으로 계산해봐도 모든 조합을 생각해봐야 풀린다고 생각했기 때문이다. 근데 저걸 처음부터 모든 조합을 다 계산하게 되면 1초는 거뜬히 넘기게 된다... 💡두번째 아이디어 멘토님에게 LCS(longest increasing subsequence)를 푸는 방법을 전수받았다! 풀이에 자세히 설명하겠다. 🔥풀이🔥 입력받은 수열은 arr에 순서대로 저장해놓고 dp 배열을 arr값으로 초기화해준다. 수열의 두번째 수부터 n번째 수까지를 나타내는 인덱스 i와 첫번째 수부터 i번째 수까지를 나타내는 인덱스 j가 있다고 하자. 만약 arr[j]가 arr[i]보..