yulee

🤔문제 이해 어느 한 숫자를 기준으로 왼쪽에는 감소하는 숫자들이, 오른쪽에는 증가하는 숫자들이 오는 부분 수열을 찾는 문제이다. 이때, 같은 숫자가 연속적으로 나올 수 없다. 💡첫번째 아이디어 가장 긴 증가하는 부분 수열의 응용 버전이었다. 🔥풀이🔥 dp_in[i]는 i번째 수를 마지막 수로 했을 때 증가하는 수의 개수를 의미하고, dp_de[i]는 i번째 수를 첫번째 수로 했을 때 감소하는 수의 개수를 의미한다. 1. dp_in과 dp_de는 모두 1로 초기화한다. 2. 앞에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_in과 이전값 dp_in에 1을 더한 값 중에서 더 큰 값을 dp_in의 현재값에 넣어준다. 3. 뒤에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_de..

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