작심 24/7

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net O(NlogN) LIS 알고리즘으로 풀어야 하는 문제이다. arr 배열엔 입력 값을 저장한다. tmp 배열의 인덱스는 수열의 길이를 나타내고 각 값은 현재 길이를 가진 수열의 마지막 원소 중 가장 작은 값의 위치를 저장한다. dp 배열엔 각 인덱스가 연결하고 있는 인덱스를 저장한다. 변수 len엔 지금까지 가장 긴 수열의 길이를 저장한다. 계산이 모두 끝나면 tmp[len]이 LIS의 마지막 원소의 위치를 가리키고 있으므로 dp[tm..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 기본적으로 DP로 길이만 저장하는 LIS를 구하는 방법에서 조금 변화를 주어 arr 배열엔 입력 값을 저장하고 len 배열엔 길이를 저장하고 dp 배열엔 현재 위치까지에서 가장 긴 수열을 가진 위치를 저장하였다. 그러고 출력할 땐 수열의 길이가 가장 길었던 위치부터 재귀 호출하여 그 수열의 처음까지 들어간 다음 출력하면서 빠져나왔다. #include using namespace st..

11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net LIS 변형 문제이다. LIS는 DP 배열에 증가 부분 수열의 길이를 갱신하는 반면 이 문제는 같은 증가 부분 수열 내의 원소들의 합을 갱신시키고 각 증가 수열이 끝날 때마다 최댓값을 갱신시켜준 뒤 최종 최댓값을 출력시키면 된다. #include #include using namespace std; int main() { int N, Max = -1; int A[1001], dp[1001]; cin >>..