분류 전체보기

바이토닉 수열은 LIS, LDS 그리고 LIS + LDS 를 모두 포함한다.예제 입력의 바이토닉 수열은 1, 2, 3, 4, 5, 2, 1 이며 총 7개로 구성된다. 구현 1 - 실패먼저 LIS의 길이 값이 담긴 배열에서 가장 큰 값을 가진 요소를 찾고,해당 요소의 인덱스를 기준으로 LDS 길이 값을 구하는 것을 생각했다. LIS : 1, 2, 3, 4, 5LDS : 5, 2, 1 각 부분 수열의 모든 길이를 구하는 것보다, LIS의 최대 길이를 가진 요소를 기준으로 구하는 것이 더 빠르다고 생각했다.하지만 특정 인덱스를 고정하게 되면, 다른 경우의 수를 놓칠 수 있다.import java.io.*;import java.util.StringTokenizer;public class Main { pub..

문제에서 옮겨진 번호는 4, 7, 1, 2번이다.3, 5, 6 번은 그대로 있는데, 문제에 주어진 수열의 최장 증가 부분 수열(LIS)로 보인다.N - (LIS 크기)를 하면 옮겨지는 아이의 최소 수를 구할 수 있다.LIS를 구할 수 있는 방법 중 이분 탐색을 사용했다. 구현 1import java.io.*;import java.util.ArrayList;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br..

상자를 넣을 수 있는 조건은 앞 상자 넣을 수 있는 상자의 개수가 최대가 되려면 뒤에 있는 상자 크기는 점점 늘어나야 한다.예제 입력 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번 삼각형을 그릴 ..