주어진 수열 내에서 증가하는 부분수열 LIS 중 최대길이를 구하기 - 주어진 수열 a[]와 수열의 i번째 수까지의 LIS 최대길이를 저장하는 d[]를 생성 - 부분수열이 존재하지 않을 때의 기본값인 1로 d[]를 초기화함 - 2부터 수열의 길이 n까지 반복하여 d[]에 값을 저장한다. - 인덱스 i 이하인 수 j 중에서 a[i]보다 크면서, d[i]-1보다 큰 d[j]를 찾으면 d[i]=d[j]+1 로 업데이트한다. - 저장된 d[] 에서 최대값이 존재하는 LIS의 최대길이이다. import java.util.Scanner; public class BOJ11053 { public static void main(String[] args) { Scanner sc = new Scanner(System.in);..
Coding Test(Algorithms)
2*n짜리 직사각형을 1*2, 2*1짜리로 채우는 방법의 갯수를 구하기 가장 끝에 1*2, 2*1를 두는 각각의 방법을 d[n-2], d[n-1] 라고 한다. d[n]=d[n-2]+d[n-1]이다. n=1일 때 1(2*1짜리 하나)로 재귀를 빠져나온다. n=2일 때 2(1*2짜리 두 개)로 재귀를 빠져나온다. import java.util.Scanner; public class BOJ11726 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int x=sc.nextInt(); int[] d=new int[x+1]; System.out.println(operate(x, d)); } static int operate(..
2*n짜리 직사각형을 1*2, 2*1, 2*2 짜리로 채우는 방법의 갯수를 구하기 가장 끝에 1*2, 2*1를 두는 각각의 방법을 d[n-2], d[n-1] 라고 한다. 이때, 끝이 1*2를 두개 두는 것은 2*2를 하나 두는 것과 같다. 즉, d[n-2]에 대해 2가지 경우가 있는 것이므로 d[n]=d[n-2]*2 + d[n-1] 이다. n=1일 때 1(2*1짜리 하나)로 재귀를 빠져나온다. n=2일 때 3(1*2짜리 두 개, 2*2짜리 하나)로 재귀를 빠져나온다. import java.util.Scanner; public class BOJ11727 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int x=sc..
주어진 수열 내에서 증가하는 부분수열 LIS 중 최대길이와 그 수열 구하기 - 주어진 수열 a[]와 수열의 i번째 수까지의 LIS 최대길이를 저장하는 d[]를 생성 - i번째 수가 LIS가 성립하도록 영향을 준 수열의 인덱스를 v[i]에 저장함 - 부분수열이 존재하지 않을 때의 기본값인 1로 d[]를 초기화함 - 2부터 수열의 길이 n까지 반복하여 d[]에 값을 저장한다. - 인덱스 i 이하인 수 j 중에서 a[i]보다 크면서, d[i]-1보다 큰 d[j]를 찾으면 d[i]=d[j]+1 로 업데이트한다. - 이때, v[i]에 인덱스 j를 저장한다. - 저장된 d[] 에서 최대값이 존재하는 LIS의 최대길이이다. - d[]의 최대값을 가진 수의 인덱스를 ansIndex에 저장하고, a[ansIndex]를 ..
1,2,3의 합으로 연속하지 않고 주어진 수를 표현하는 방법 출력하기 - 입력될 수 있는 모든 경우의 수를 저장하기 위해, 2차원 배열 d[100001][4] 로 메모이제이션을 한다. - d[i][j]는 합해서 i 가 되는 방법 중, 마지막으로 더해지는 수가 j 이다. - 즉, 합해서 i 가 되는 방법의 수는 d[i][1]+d[i][2]+d[i][3] 이다. - d[1][1], d[2][2], d[3][3]는 예외로 처리하기 위해 if(i == j)일 때는 1을 저장하도록 처리한다. - d[i][1]를 구하려면, 마지막에 더해지는 수 1을 제외하고 (i-1)에 대한 방법의 수를 구하면 된다. - 이때, 1과 연속이 되지 않기 위해 (i-1)에 대한 방법은 d[i-1][2], d[i-1][3] 두 가지만 ..
N개의 카드를 1~N개짜리 카드팩으로 고를 때 가장 싸게 사는 가격을 찾기 - 1~n개의 카드가 들어있는 카드팩의 가격을 p[1]~p[n] 배열에 저장한다. - 1~n개의 카드를 고를 때 가장 싸게 가격을 d[1]~d[n] 배열에 저장한다. - 모든 d[ ] 배열에 초기값은 최대가격을 초과한 10,001로 설정한다. - if(d[x] < 10,001)으로, 메모리제이션을 확인한다. - x개를 고를 때, x-1개를 가장 싸게 사고, 1개짜리 카드팩을 사는 경우, x-2개를 가장 싸게 사고, 2개짜리 카드팩을 사는 경우, ... 0개를 가장 싸게 사고, x개짜리 카드팩을 사는 경우까지 가격을 반복문으로 비교하며 최저 가격을 d[x]에 저장한다. import java.util.Scanner; public cl..
