상자를 넣을 수 있는 조건은 앞 상자 넣을 수 있는 상자의 개수가 최대가 되려면 뒤에 있는 상자 크기는 점점 늘어나야 한다.예제 입력 1 : 1, 2, 3, 5, 6 -> 5예제 입력 2 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 -> 10문제에 주어진 수열에서 최장 증가 부분 수열(LIS)을 구하고 그 개수를 반환해야 한다.최장 증가 부분 수열 (Longest Increasing Subsequence)어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.최장 증가 부분 수열을 구현하는 방법으로는 DP와 이분 탐색이 있다. 구현 1 - DPimport ja..

파도반 수열이라 하니 비슷한 피포나치 수열이 생각난다. 억지피보나치수열에는 패턴이 존재하는데, 파도반 수열 문제에 나열된 숫자들도 어떤 패턴을 가지고 있을 것 같다. 피보나치 수열N = 10 조건을 가지는 피보나치수열을 구한다면 1 + 1 + 2 + 3 + 5 + 8 + 13 + 22 + 35 + 55이다.F(1) = F(2) = 1의 초기값을 가지며 점화식으로 F(n) = F(n-1) + F(n-2)가 된다. 파도반 수열먼저 변의 길이는 생각하지 말고(?) 규칙을 찾기 위한 삼각형을 그려보자.여러 방식으로 그림을 그려봤지만 이 그림에서 규칙을 찾게 되었다.문제의 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 수열에서 보면 4번 삼각형을 그렸을 때 변의 길이가 늘어나기 시작하고,6번 삼각형을 그릴 ..

LDS와 반대인 LIS 알고리즘을 사용하여 푸는 문제이다.LIS - 최장 증가 부분 수열어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.-- 나무위키문제는 가장 긴 부분 수열이 아닌, 증가 부분 수열 중 가장 크게 증가하는 부분 수열의 합을 출력해야 한다. 이전 글인 LDS 문제에서는 최대 길이를 저장했다면, 이번 문제는 최대 합을 저장해야 한다.수열 A11002506035678최대 합1101353113611172432구현import java.io.*;import java.util.StringTokenizer;public class Main { public st..

LDS - 최장 감소 부분 수열주어진 수열에서 요소들이 감소하는 순서대로 선택되는 가장 긴 부분 수열을 말한다.수열의 원래 순서를 유지하면서 순서대로 감소하는 숫자들을 선택하여 만들 수 있는 가장 긴 부분 수열을 찾아야 한다.DP반복문을 돌면서 감소하는 부분 수열의 최대 길이를 배열에 저장하는 메모이제이션 방식으로 문제를 풀어야 한다. 최대 길이가 저장되는 배열을 dp라고 할 때, dp는 모두 1로 초기화한다.감소하는 부분 수열이 없다면 자기 자신만 가지게 되기 때문이다. 감소하는 부분 수열이기 때문에 자신보다 왼쪽에 있는 값이 더 커야 한다.먼저 기준 값(A [I])을 정하고, 왼쪽의 값(A [J])들을 모두 비교한다.A [J]가 A[I] 보다 크다면 A [J]가 가진 길이에서 +1 하여 A [I]의 ..