백준

[백준] 제곱수의 합(1699번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1 [접근 방법] 배열 DP 는 해당 인덱스를 제곱수의 합으로 나타낼 때, 그 제곱수 항의 최소 개수를 저장한다. 13을 예로 들겠다. 13 = 3^2 + 2^2 인 경우 항이 개로 최소 개수는 '2' 가 된다. (13 - 1^2) , (13 - 2^2) , (13 - 3^2) 중 제곱수 항의 최소 개수 + 1 과 같다. 12 의 제곱수 식에 (+ 1^2) 를 하는 경우 9 의 제곱수 식에 (+ 2^2)를 하는 경우 4 의 제곱수 식에 (+3^2)를 하는 경우 중 최소항의 개수를 가진 것을 고르면 된다. (4^2 > 13 이므로 제외된다.) [JAVA 코드] import java.io.BufferedReader; impo..

[백준] 연속합 (1912번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1 [접근 방법] 문제 고민에 굉장히 많은 시간을 소요하였다. "DP 문제는 모든 것을 내가 구현할 필요는 없다." 라는 것을 다시끔 일깨워 준 문제 였다. 즉, 예제 1번 처럼 [10, -4, -3, 1, 5, 6, -35, 12, 21, -1] 이 주어지는 경우 직접 프로그래밍으로 어느 지점의 연속된 수의 합이 최대값 인지를 구할 필요가 없다는 것이다. '음수가 나오는 경우' , '음수 뒤에 양수가 나와서, 둘다 더하는 것이 이득인지 아닌지' 등 복잡한 경우들을 직접 고려하여 해결할 필요는 없는 것이다. 그냥 방법만 알려주고, 놓고 온다는 표현이 적절할 것 같다. for(int i=1; i

[백준] 가장 긴 증가하는 부분 수열 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 : ..