안녕하세요 이번 시간에는 저번 시간에 이어 DP의 두 번째 유형에 대해 알아보는 시간을 갖도록 하겠습니다.
DP 문제의 두 번째 문제 유형은 특정 조건을 만족하는 수열의 항 중 최대 혹은 최솟값을 구하는 문제입니다. 사실상 DP 문제의 가장 많은 출제 유형 중 하나로 주어진 수열 혹은 리스트를 특정 조건과 함께 탐색하면서 특정 조건을 만족하는 최대 혹은 최솟값을 출력하는 문제입니다.
백준 1912(연속합) 문제의 경우 N개의 수열 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제입니다. 문제에서 구하고자 하는 값, 즉 dp[i] : 1부터 i번째까지의 수열 중 i를 포함하는 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 최대합으로 설정한다면 현재까지 구한 연속합에 현재 수를 더한 값과 현재 수를 비교하여 더 큰 값을 dp에 저장하면 됩니다. 즉 dp[i] = Math.max(dp[i-1]+map[i], map[i])로 설정하며 합의 최댓값이 dp[N] 이전에도 나타날 수 있기 때문에 dp 배열 중의 최댓값을 출력합니다.
백준 13398(연속합 2) 문제의 경우 N개의 수열 중 연속된 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는데, 이 때 수열에서 수를 하나 제거 가능하다는 특징이 있습니다. 백트래킹으로 접근하게 되면 N이 매우 크기 때문에 시간 초과가 발생하여 dp로 풀이합니다. 하나를 제거할 수 있다는 특징을 고려하여 왼쪽과 오른쪽에서 접근하는 배열 두 개를 생성하여 dp[i] : 0에서 i까지 길이에서 “i를 포함하며” 연속으로 수를 선택하여 구할 수 있는 최대 합으로 설정해줍니다. 이렇게 하면 두 배열이 참조하지 않는 인덱스, 즉 n이 10이라고 했을 때 왼쪽에서 4개를, 오른쪽에서 5개를 참조한다면 남은 1개가 자연스럽게 제거된 수로 설정할 수 있습니다. 이 후 연속합 로직과 동일하게 dp[i] = Math.max(map[i], dp[i-1]+map[i]) 로직으로 왼쪽에서 진행하는 dp를 채워주며 dp[i] = Math.max(map[i], dp[i+1]+map[i]) 로직으로 오른쪽에서 진행하는 dp를 채웁니다. 이 후 두 인덱스 사이에 1개의 공간을 둔 합의 최댓값을 출력합니다.
백준 1932(정수 삼각형) 문제의 경우 맨 위에서 아래로 내려올 때 선택된 수의 합이 최대가 되는 경로를 구하는 문제입니다. 삼각형 구조 특성상 끝값을 조정해준다면 이차원 배열처럼 구성이 가능하기 때문에 dp[i][j] : i번 줄에서 j번 칸까지 왔을 때의 최대 합이라고 한다면 이전 줄 이전 칸의 값까지의 합과 이전 줄 현재 칸까지의 값까지의 합 중 최대값에 현재값을 더한, 즉 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j])+map[i][j]을 하되 j가 1인 경우 이전 칸이 없기 때문에 dp[i-1][j]만 진행하고 j가 줄 번호와 같을 경우 다음 칸이 없기 때문에 dp[i-1][j-1]만 진행합니다.
백준 5582(공통 부분 문자열) 문제의 경우 두 문자열의 공통 문자열 중 가장 긴 문자열을 출력하는 문제입니다. dp[i][j] : 첫 번째 문자열의 i번째 까지의 문자열과 두 번째 문자열의 j번째까지의 문자열 중 공통 부분 문자열의 길이의 최댓값로 설정한 후 첫 번째 문자열의 i번째 문자와 두 번째 문자의 j번째 문자가 같으면 최소 1자리는 일치하기 때문에 dp[i][j] = 1로 설정하고 첫 번째 문자의 i번째 문자와 두 번째 문자의 j번째 문자가 같고 i-1번째 문자와 j-1번째 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]+1로 이전값에서 1씩 더해줍니다. 이렇게 한다면 i와 j가 증가함에 따라 이전 값과 연속된 비교를 진행하기 때문에 연속된 문자열을 체크 가능합니다,
백준 9252(LCS 2) 문제의 경우 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 구하는 문제입니다. 공통 부분 문자열과 다른 점은 "문자열을 점프"하는게 가능하다는 점입니다. dp[i][j] : 첫 번째 수열의 i번째 까지의 부분 수열과 두 번째 수열의 j번째까지의 부분 수열 중 공통 부분 수열의 가장 긴 수열의 길이로 설정한 후 첫 번째 수열의 i번째 자리의 수와 두 번째 수열의 j번째 자리의 수가 같을 경우 dp[i][j] = dp[i-1][j-1]+1로 설정하며 값이 다르다면 지금까지의 수열 중 가장 긴 값을 출력합니다. dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) dp 값 추가가 완료되면 가장 마지막 위치에서 아래쪽으로 이동하여 두 값이 같다면 정답 문자열에 추가하고 두 값이 다르다면 이전 값 중 더 큰 값으로 이동합니다.
