이번 주는 DP(Dynamic Programming)에 관한 문제를 풀었습니다. 풀었던 문제 중에 2 문제 정도만 설명하겠습니다.
📌 가장 긴 증가하는 부분 수열 4
가장 긴 증가하는 부분 수열 4 문제는 수열이 주어졌을 때, 그 수열 중에서 점차 값이 증가하고 가장 길이가 긴 부분 수열의 길이와 그 부분 수열의 값을 출력하는 문제입니다.
예를 들어 수열 A가 {10 20 10 30 20 50}로 주어졌을 때, 가장 긴 증가하는 부분 수열은 {10 20 30 50}로 길이가 4입니다.
💡 느낀점과 배운점
이 문제를 풀기 위해서는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)를 이해하면 쉽게 해결할 수 있다는 것을 알게 되었습니다.
이 LIS는 어떤 수열이 주어졌을 때, 그 수열에서 몇 개의 수들을 제거하여 부분 수열을 만들 수 있습니다. 그 중에서 오름차순으로 정렬된 가장 긴 수열을 말하는데, 딱 지금 해결하려고 하는 문제와 똑같다는 것을 알 수 있습니다.
이 LIS는 DP(Dynamic Programming)로 풀 수 있습니다.
아래는 DP를 이용한 코드입니다.
arr 배열은 입력으로 주어진 수열이 저장되며, dp 배열은 부분 수열의 길이가 저장됩니다.
// 가장 긴 증가하는 부분 수열 탐색
for(int i=1; i<n; i++){
dp[i] = 1;
for(int j=0; j<i; j++){
if(arr[i]>arr[j] && dp[i]<=dp[j]){
dp[i] = dp[j] + 1;
}
}
}
int answer = 0;
for(int value : dp){
answer = Math.max(answer, value);
}dp 배열에는 i번 째 인덱스일 때, 증가하는 가장 긴 수열의 길이가 저장됩니다.
그래서 초기에는 1을 저장해두고 0부터 현재 인덱스의 위치까지 탐색하면서 그 값을 갱신합니다.
제일 중요한 부분은 이중 for 문안에 if문 입니다.
for(int j=0; j<i; j++){
if(arr[i]>arr[j] && dp[i]<=dp[j]){
dp[i] = dp[j] + 1;
}
}이 부분은 일단 현재 위치(i)에 있는 값이 더 커야 성립합니다.
그리고 dp 배열을 확인합니다
dp 배열을 확인하는 이유는 현재 확인하려는 인덱스(i)까지 증가하는 가장 긴 부분 수열의 길이가 존재하는지 확인하기 위해서 입니다.
증가하는 가장 긴 부분 수열의 길이가 존재하면, dp의 현재 위치(i)에 탐색한 증가하는 가장 긴 부분 수열의 길이를 +1한 값으로 길이를 갱신합니다.
위의 예제로 dp 배열에 값이 채워지는 동작 과정을 설명하자면, 수열 {10 20 10 30 20 50}에서 첫 인덱스부터 확인합니다.
{10} -> dp {1 }
{10, 20} -> dp {1, 2}
{10, 20, 10} -> dp {1, 2, 1}
{10, 20, 10, 30} -> dp {1, 2, 1, 3}
{10, 20, 10, 30, 20} -> dp {1, 2, 1, 3, 2}
{10, 20, 10, 30, 20, 50} -> dp {1, 2, 1, 3, 2, 4}
그리고 문제에서 요구하는 증가하는 가장 긴 부분 수열을 출력하기 위해 List에 수열을 저장합니다.
ArrayList<Integer> list = new ArrayList<>();
// 가장 긴 증가하는 부분 수열들을 저장하기 위해 탐색
for(int i=n-1; i>=0; i--){
// 앞에서 구한 가장 긴 증가하는 부분 수열의 길이를 이용하여 부분 수열들을 list에 저장
if(answer==dp[i]){
list.add(arr[i]);
answer--;
}
}
// 부분 수열 출력
for(int i=list.size()-1; i>=0; i--)
bw.write(list.get(i)+" ");이 가장 긴 증가하는 부분 수열 문제들을 풀면서 DP에 대한 이해도가 올라간 것 같습니다.
📌 2×n 타일링 2
2×n 타일링 2 문제는 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제입니다.
예를 들어, 입력으로 2가 주어지면 2 x 2 직사각형을 1 × 2, 2 × 1과 2 × 2 타일로 채우는 방법의 수는 총 3가지 입니다.
💡 느낀점과 배운점
사실 이 문제는 쉽게 해결했습니다.
왜냐하면 그림판으로 일일이 2 X 3과 2 X 4 직사각형을 타일로 채우는 방법의 수를 그려봤는데, 규칙이 보였습니다.
그래서 그 규칙을 토대로 점화식을 세우고 예제 입력 테스트를 해보니 정상적으로 정답이 출력되어 그대로 제출하여 성공했습니다.
처음에 2 X 1은 2×1 타일만 채울 수 있으니 1가지 방법만 존재합니다.
2 X 2은 1×2 타일 2개와 2×1 타일 2개, 2×2 타일 한개로 총 3가지 방법이 존재합니다.
2 X 3은 그림판으로 그려봤을 때, 총 5가지 방법이 나오고 2 X 4는 11가지 방법이 나왔습니다.
여기서 규칙이 보였습니다.
2 X n의 직사각형을 타일로 채우는 방법의 수를 식으로 나타내면 2*(n-2) + (n-1)로 표현할 수 있습니다.
예를 들어, 2 X 4는 2 * (2 X 2 방법 수) + (2 X 3 방법 수)를 하면 최종 결과가 나오게 됩니다.
그래서 코드는 아래와 같습니다.
int[] dp = new int[n+1];
for(int i=0; i<=n; i++) {
if(i<=1)
dp[i] = i;
else if(i==2)
dp[i] = 3;
else {
dp[i] = (2*dp[i-2] + dp[i-1]) % 10007;
}
}dp의 특징인 메모이제이션을 통해 해결합니다.
