문제를 풀기 위한 아이디어 1. 직전까지의 부분합 + 현재 가리키고 있는 수 2. 현재 가리키고 있는 수 를 비교하여 더 큰 값을 부분합으로 저장한다. 즉, 지금까지 연속해서 더한 부분합+현재 가리키고 있는 수와 그냥 현재 가리키고 있는 수를 비교했는데 현재 가리키고 있는 수가 더 크다면 미련없이 이전 수들을 버리고 새롭게 시작하여도 OK라는 것이다. 예제 1을 가지고 예를 들어보면, [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]에서 dp[7]까지는 쭉 더하다가 8번째 수인 12를 만났을 때 -14 + 12 vs 12를 비교해서 12가 더 크기 때문에 이전 값을 다 버리고 12부터 시작하는 것이다. 그렇게 해서 구한 모든 dp 값 중 최댓값을 출력하면 된다. 내가 구현한 코드 (자바..

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 이번 시간에는 LCS(Longest Common Subsequence, 최장 공통 부분 수열)에 대해 알아보겠습니다. 지난 시간에 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)에 대한 문제를 백준에서 풀어보았는데요. (이전 포스팅 참조) 이번 에는 LCS에 대해 알아보겠습니다. LCS, 최장 공통 부분 수열이란 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다. 예를 들어, CAPCAK와 ACAYKP의 LCS는 ACAK가 됩니다. (이 때 꼭 문자열이 연속해야 할 필요는 없습니다.) 이 문제를 풀어보는 방법은 다음과 같습니다. 우선 ACAYKP와..

문제를 풀기 위한 아이디어 앞선 문제 [11053. 가장 긴 증가하는 부분 수열] 에서 조금만 창의적으로 생각하면 풀 수 있는 문제이다. 이 문제는 가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열의 합을 구해서 최댓값을 구하면 되는 문제이다. 나는 최대한 헷갈리지 않기 위해서 가장 긴 증가하는 부분 수열을 구해서 값을 저장할 공간을 increaseDP라는 배열을 만들어 값을 저장했고, 가장 긴 감소하는 부분 수열을 구해서 값을 저장할 공간은 decreaseDP라는 배열을 만들어 값을 저장했다. increaseDP[1] = 1 decreaseDP[N] = 1을 저장한다. 주어진 수열은 numbers라는 배열에 저장한다. (나는 numbers의 0번째 인덱스에 값을 추가해주었다. 뒤에서 반복문에..

문제를 풀기 위한 아이디어 일단 "가장 긴 증가하는 부분 수열" 이라는 것은 주어진 수열 내에서 공차, 공비 이런 것은 신경쓰지 않고 단순히 증가하는 양상만 보았을 때 어떤 부분 수열(쉽게 말해서 부분 집합)이 가장 긴 가를 따지는 것이다. 우선 dp값을 저장할 배열을 주어진 수의 길이인 N 사이즈에 맞게 만들고 초기 값을 모두 1로 채워준다. dp[N]에는 N까지의 배열에서 가장 긴 증가하는 부분 수열의 길이가 저장될 것이다. 이 때 초기값을 1로 채워주는 이유는, 최소한 자기 자신은 다 가지고 있기 때문에 1로 채워주는 것이다. 그리고 문제에서 주어진 수열을 numbers라는 배열에 저장하고, 각 numbers를 반복문을 돌며 자기 자신보다 작은 값을 세야 한다. numbers = [100, 200,..

문제를 풀기 위한 아이디어 dp 배열을 만든다. dp[N]에는 포도주의 개수가 N개일 때 최댓값이 저장될 것이다. dp[1] = wine[1] (포도주가 1개밖에 없을 때에는 무조건 1개의 포도주를 마시는게 최댓값이다.) dp[2] = wine[1] + wine[2] (포도주가 2개밖에 없을 때에는 무조건 2개의 포도주를 모두 마시는게 최댓값이다.) dp[3] = (wine[1] + wine[2] , wine[2] + wine[3] , wine[1] + wine[3]) 이 3가지 경우에서 가장 큰 값이 최댓값이 된다. (연속해서 3잔을 먹을 순 없기 때문에) dp[4]부터는 dp[N]을 어떻게 구할 수 있을까? 위의 그림이 모든 것을 설명해준다. 즉 저 위의 3가지 경우 중 최댓값이 dp[N]이 된다. ..

문제를 풀기 위한 아이디어 다이나믹 프로그래밍 문제는 언제나 점화식을 세우는 것이 중요하다. 이번 문제는 dp에서 2차원 배열을 이용해서 저장하는 것을 배울 수 있었던 문제였다. 우선 0으로 시작하는 수는 없다고 했기 때문에, n=1인 경우 1,2,3,4,5,6,7,8,9 = 9가지 경우가 나온다. n=2인 경우를 생각해보자. (10,11) (21,23) .... (98)로 다 합치면 17가지 경우가 나온다. 즉 앞의 수가 0이면 뒤에 올 수 있는 수는 1밖에 존재하지 않는다. 만약 앞의 수가 1부터 8이라면 각각 두개씩 존재할 수 있다. 만약 앞의 수가 9라면 뒤에 올 수 있는 수는 8밖에 존재하지 않는다. 이를 염두해두어야 한다. dp[n][i]를 n자리수 이면서 i로 끝나는 경우라고 한다면, 우선 ..