전체 글

[백준] 가장 긴 증가하는 부분 수열 4 (14002번 JAVA) / 400 - 다이나믹 프로그래밍 1 [접근 방법] 문제에서 응용이 된 문제이다. https://notorious.tistory.com/180 [백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) [백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) 최장 증가 부분 수열 이란...? (LIS : Longest Increasing Subsequence) : 어떤 임의의 수열이 주어질 때, 이 수열에서 볓개의 notorious.tistory.com 기본적인 문제 풀이는 동일하고, LIS를 출력하는 것이 추가된 형태이다. 처음 고려한 방법..

[백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) 최장 증가 부분 수열 이란...? (LIS : Longest Increasing Subsequence) : 어떤 임의의 수열이 주어질 때, 이 수열에서 볓개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. cf) 동적 계획법으로 해결하는 유명한 알고리즘 문제 (알아놓자!) [접근 방법] 1. O(N^2) 의 시간복잡도를 가지는 방법 ★ 배열 10 20 10 30 20 50이 주어진 경우 index = 0은 원소 10이 자리하고 있다. 10 하나만 존재 하므로, 이때, LIS의 길이는 1 이다. index = ..

[백준] 400 - 다이나믹 프로그래밍 1 : 쉬운 계단 수 (!) (10844번 JAVA) [접근 방법] 메모이제이션 기법으로 사용할 배열 dp를 다음과 같은 2차원 배열로 구성해야 한다. dp[수의 길이 : N][수의 일의 자리 수] // 길이가 N 이고, 일의 자리 숫자 0 ~ 9 임을 표시 long[][] dp = new long[N+1][10]; dp[1][0] = 0; dp[1][1] = 1; // 1 dp[1][2] = 1; // 2 dp[1][3] = 1; // 3 dp[1][4] = 1; // 4 dp[1][5] = 1; // 5 dp[1][6] = 1; // 6 dp[1][7] = 1; // 7 dp[1][8] = 1; // 8 dp[1][9] = 1; // 9 N = 3인 경우를 그림..

[시리즈 접근 방법] ** [1, 2, 3 더하기] 시리즈에서 중요한 것은 N을 만들기 위해 사용할 수 있는 숫자는 1 , 2 , 3 뿐이라는 것이다. 이 당연한 말이 뭐가 중요한가 싶겠지만, 사용 가능한 숫자가 1, 2, 3 뿐이라는 것은 dp[N] 에 영향을 줄 수 있는 원소들은 dp[N - 1] , dp[N - 2], dp[N - 3] 뿐이라는 것이다. 따라서 점화식 dp[N]은 dp[N - 1] , dp[N - 2], dp[N - 3]을 이용하여 만들어진다. 9095번 - 1, 2, 3 더하기 https://notorious.tistory.com/167 [백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 (!) (9095번 JAVA) [백준] 400 - 다이나믹 프로그래밍 1 : ..

[백준] 1, 2, 3 더하기 9 (16195번 JAVA) [접근 방법] 15992번 [1, 2, 3 더하기 7] 문제와 아주 유사한 문제이다. 이전에는 각 수식이 몇개의 숫자로 이루어졌는지를 구해야했다면, 이번에는 몇개 이하의 수식 개수를 모두 더하면 된다. 15992번 [1, 2, 3 더하기 7] 문제 풀이는 다음과 같다. https://notorious.tistory.com/176 [백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 7 (15992번 JAVA) [백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 7 (15992번 JAVA) [접근 방법] 2차원 배열로 dp를 선언해야 한다. dp[n][m] = dp[수식의 합][수식의 수 개수] 로 정의한다. long..

[백준] 1, 2, 3 더하기 8 (15993번 JAVA) [접근 방법] 2차원 배열로 구성해야 한다. 수식에서 숫자가 홀수개로 구성된 것과 짝수개로 구성된 것을 따로 저장해야 한다. 정수 n이 짝수개로 구성 : dp[n][0] 정수 n이 홀수개로 구성 : dp[n][1] 와 같이 정의 하였다. 초기값은 다음과 같이 설정하였다. long[][] dp = new long[100_001][2]; // 정수 n이 짝수개로 구성 : dp[n][0] // 정수 n이 홀수개로 구성 : dp[n][1] dp[1][1] = 1; // 1 dp[2][0] = 1; // 1+1 dp[2][1] = 1; // 2 dp[3][0] = 2; // 1+2, 2+1 dp[3][1] = 2; // 1+1+1, 3 정수 n이 짝수개로..