Smallsoft

문제링크문제요약특정 수를 기준으로 왼쪽에 위치한 숫자는 증가하고 오른쪽에 위치한 숫자는 감소하는 형태를 띤 부분 수열을 바이토닉 수열이라고 부른다. 문제에서 수열이 주어질때, 가장 긴 바이토닉 수열을 찾는 문제이다. 풀이LIS를 두번 적용시킴으로써 해결 가능한 문제이다.바이토닉 수열은 처음에는 증가하다 특정수를 기준으로 감소하는 형태이다.LIS를 통해 증가하는 수열에 대한 정보를 dp[]에 담는다.이 배열을 다시 감소하는 수열을 구하는 LIS를 구하면 dp[]에는 증가이후 감소하는 형태의 수열에 대한 길이를 구할 수 있다.소스코드#include using namespace std;/*증가 또는 감소세의 방향이 일직선이 수열을 바이토닉 수열이라고한다.바이토닉 수열을 찾으시오*/int n, ans;int a..

문제링크문제요약n개의 수열(아이들)이 정렬되어있지않은 상태이다.이 수열을 정렬하기위해서 수를 옮겨야하는데 이때 최소한으로 옮기는 수를 출력하는 문제이다.풀이3개의 수열을 여러가지 형태로 가정해보겠다.[1, 2, 3] 이 수열은 0번 움직이면 정렬된다.[1, 3, 2] 이 수열은 3을 뒤로 보내서 1번에 정렬된다.[3, 2, 1] 이 수열은 총 2번을 움직여야 정렬된다.이 규칙을보면 LIS를 구하는것과 연관이 있어 보인다.[1, 2, 3]은 최장 증가 부분 수열이 [1, 2, 3]이고,[1, 3, 2]은 [1, 2]가 나온다.[3, 2, 1]은 [1] 하나만 나오게된다.풀이를 정리하면위치를 옮기지 않아도 되는 아이들은 이미 오른차순을 만족하는 부분 수열이다.이 중 가장 긴 오름차순 부분 수열을 찾고, 이를..

문제링크문제요약이 문제는 최장 증가 부분 수열 알고리즘에 관한 문제이다.해당 알고리즘의 대표적인 예시이기 때문에 따로 이 문제를 못풀겠다면 해당 알고리즘을 공부해야한다.소스코드#include #include using namespace std;int n;int board[1005];int dp[1005];int ans;int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i > board[i]; dp[i] = 1; for (int j = 0; j board[j]) dp[i] = max(dp[i], dp[j] + 1); } a..