다이나믹 프로그래밍

[백준] 13398. 연속합 2 (Java)

문제 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 다이나믹 프로그래밍 (DP) 풀이 [2][n+1] 크기의 2차원 배열 dp를 선언하고 다음과 같이 값을 저장한다. dp[0][i] = 값을 제거한 적 없는 i번째 수까지의 최대 연속합 dp[1][i] = 값을 제거한 적 있는 i번째 수까지의 최대 연속합 i 번째 수를 num이라고 할 때, dp[0][i] 는 dp[0][i-1] 가 0보다 작다면 이전까지의 연속합을 버리고, num 부터 새로 시작하는 것이 더 큰 값을 만들 수 있다. dp[0][i] = ..

[백준] 11722. 가장 긴 감소하는 부분 수열 (Java)

문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 알고리즘 다이나믹 프로그래밍 (DP) 풀이 11053. 가장 긴 증가하는 부분 수열 문제와 사실상 동일한 문제이다. N+1 크기의 1차원 배열 dp를 선언하고 다음과 같이 값을 저장한다. dp[i] = i번째 원소로 끝나는 가장 긴 감소하는 부분 수열의 길이 즉 dp[i]는 i보다 이전에 있던 원소를 모두 탐색하며 i보다 큰 값 중 dp에 저장된 값이 가장 큰 값을 찾고, 그 dp 값..

[백준] 2156. 포도주 시식 (Java)

문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 알고리즘 다이나믹 프로그래밍 (DP) 풀이 연속으로 최대 2잔의 포도주만 마실 수 있기 때문에 특정 포도주를 마실 수 있어도 안마시는 것이 더 나은 경우가 있다. 따라서 연속으로 마신 포도주의 잔 수에 대한 최댓값을 기록한다. [n + 1][3] 크기의 2차원 배열 dp를 선언하여 다음과 같이 저장하였다. dp[i][j] = i 번째 포도주까지 연속 j 잔 마셨을 때 최대로 마실 수 있는 포도주의 양 dp[i][0] 은 i번째 포도주를 마시지 않은 경우이다...

[백준] 11057. 오르막 수 (Java)

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 [N + 1][10] 크기의 2차원 배열를 선언하여 다음과 같이 저장하였다. dp[i][j] = 길이 i의 j로 끝나는 숫자 중 오르막 수의 개수 만약 j로 끝나는 오르막 수라면 그 전에는 j보다 작거나 같은 수가 올 수 있다. 따라서 점화식은 다음과 같다. dp[i][j] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j] 위 방..

[백준] 1309. 동물원 (Java)

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 [N+2][3] 크기의 2차원 배열을 dp를 선언하여 다음과 같이 저장하였다. dp[i][0] = i 번째 행에 사자를 배치하지 않는 경우의 수 dp[i][1] = i 번째 행 왼쪽 우리에 사자를 배치하는 경우의 수 dp[i][2] = i 번째 행 오른쪽 우리에 사자를 배치하는 경우의 수 dp[i][0]는 사자를 배치하지 않기 때문에 이전 행에 사자가 배치되지 않거나, 왼쪽이나 오른쪽 우리 어디에 배치되어도 상관없다. dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] dp[i][1]는 사자를 왼쪽 우리에 배치하는 ..

[백준] 2225. 합분해 (Java)

문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 다이나믹 프로그래밍 (DP) 풀이 [K + 1][N + 1] 크기의 2차원 배열을 이용하여 dp[a][b] 에 a개의 정수를 이용하여 합 b를 만든 경우의 수를 저장한다. 이때 점화식은 다음과 같다. dp[k][N] = dp[k-1][0] + ... + dp[k-1][N] 예제 입력 1대로 0부터 20까지 정수 2개를 더해서 합 20을 만든다고 가정하자. 1개의 원소를 이용하면 자기 자신만 만들 수 있으므로 경우의 수는 각각 1이다. (dp[1][0] ~ dp[1][20] = 1) 2개의 원소를 이용하여 합 20을 만들려면 다음과 같이 21개의 경우의 수가 생긴다 0 + 2..

[백준] 15990. 1, 2, 3 더하기 5 (Java)

문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 테스트 케이스가 여러 개 올 수 있으므로 미리 n=100000까지의 정답을 계산해두고 출력한다. 연속해서 같은 수가 올 수 없다는 조건이 있으므로 마지막에 무슨 수가 왔었는지가 중요하다. 마지막 수가 1이라면 뒤에 2, 3이 올 수 있고 마지막 수가 2이라면 뒤에 1, 3이 올 수 있고 마지막 수가 3이라면 뒤에 1, 2가 올 수 있다. 따라서 수 n을 만드는 경우 중 마지막이 i로 끝나는 경우의 수를 dp[n][i] 형태로 저장할 dp[100001][4] 배열을 만든..

[백준] 1699. 제곱수의 합 (Java)

문제 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 최악의 경우 i 는 1이 n번 더해졌을 수 있으므로 dp[i] = i 로 초기화한다. dp[i] 는 자기보다 작은 어떤 제곱수 j * j 에 대해 dp[i - j * j] + 1 이 될 수 있고 그 중 최솟값이 된다. 예를 들어 i 가 22라면 dp[22] 는 다음 네 값 중 최솟값이다. dp[22 - 1] + 1 (1^2) dp[22 - 4] + 1 (2^2) dp[22 - ..

[프로그래머스] 피보나치 수 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 다이나믹 프로그래밍(DP) 풀이 반복되는 계산이 많기 때문에 피보나치 값을 저장해두어 연산 횟수를 줄인다. 코드 class Solution { public int solution(int n) { int[] fibo = new int[n+1]; fibo[1] = 1; for(int i=2; i

[프로그래머스] 땅따먹기 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 다이나믹 프로그래밍(DP) 풀이 i행 j열을 밟았을 때 점수의 최댓값은 i-1행에서 j열을 제외한 세 행을 밟았을 때 점수의 최댓값 + i행 j열의 점수이다. 예를 들여 3행 2열을 밟았을 때 점수의 최댓값은 2행 1열, 2행 3열, 2행 4열을 밟았을 때 점수의 최댓값 + 3행 2열의 점수이다. 따라서 다이나믹 프로그래밍으로 각 칸까지 얻을 수 있는 최댓값을 구하고, 마지막 행의 네 열 중 최댓값을 반환한다. 코드 class Solution { int solution(int[][] land) ..