백준 : https://www.acmicpc.net/problem/11053
오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.
최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.
ex) A = {10, 20, 10, 30, 20, 50} 일 떄 10,20,30,50. , 길이 4
먼저 DP[i]를 정의하자.
DP[i] = |수열의 i번째 원소를 포함하는 i번째 원소까지의 최장 증가 부분 수열 길이|
i번째 원소를 포함할 때 이전까지의 최장 증가 부분 수열의 마지막 항이 i번째 원소보다 작았어야한다. 따라서 0번부터 i-1번의 원소 중 i번째 원소보다 작고, DP값이 가장 큰 원소를 골라주면 된다.
DP[i] = max(DP[a1],DP[a2],....,DP[am]) + 1 (단, i > aj && A[i] > A[aj])
이를 코드로 구현해보자.
#include <iostream>
using namespace std;
int dp[1001],num[1001];
int main()
{
int N,mx=0;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>num[i];
}
for(int i=1;i<=N;i++)
{
for(int j=0;j<=i-1;j++)
{
if(num[i]>num[j])
{
dp[i] = max(dp[i],dp[j]+1);
}
}
if(mx < dp[i])
{
mx = dp[i];
}
}
cout<<mx;
}
시간 복잡도 : O(N^2)
'정보 > 알고리즘&자료구조' 카테고리의 다른 글
LIS 알고리즘(최장 증가 부분 수열) O(nlogn) (0) | 2024.05.26 |
---|---|
Knapsack Problem Dynamic Programming C++ (1) | 2024.02.01 |
C++ <algorithm> sort()로 배열 정렬하기 (0) | 2024.01.14 |