www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 4번 문제와 똑같이 풀면 된다. 이번에는 q에 초기 숫자를 하나 넣어주는 대신 비어있거나 현재 원소가 q의 마지막 원소보다 크면 추가해주는 방식으로 했다. n의 범위만 달라지므로 초기값을 넣어줬었다면 이 부분만 주의하면 된다. temp 배열을 출력하면 이렇게 나오고 [(0, 10), (1, 20), (0, 10), (2, 30), (1, 20), (3, 50)] ans 배열에 넣을..
www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1,2,3 까지는 쉬웠는데 4부터 난이도 급상승 ㅠ O(n^2)으로 푼 사람이 많은데 n이 커진 문제인 경우 못풀걸 알아서 더 줄여서 풀고 싶었다 혼자서 시도해보다가 다른 사람 풀이 참고해서 풀었다. 아직 알고리즘 머리가 부족하군.. 이전 문제들에서 이전보다 더 작은 수가 등장했을 때 위치를 갱신하는 것은 익숙할 것이다. 여기서는..
www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1과 다른 점은 배열 원소의 최소값이 -10^9이기 때문이다. 따라서 q의 처음 최소값을 그 수보다 작은 수로 하면 된다 import sys from bisect import bisect_left n=int(sys.stdin.readline()) arr=list(map(int,sys.stdin.readline().split())) #마지막 길이 출력 때 1을 빼준다 q=[-1000..
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 부분 수열의 길이만 구하는 문제고 실제 어떤 원소가 부분 수열을 이루고 있는지나 해당 원소의 인덱스를 구하는 문제가 아니라서 쉽게 구할 수 있다. 심지어 이 문제는 O(N*2)을 해도 풀리기 때문에 (1초= 10^9를 넘어가지 않으면 된다) 이중 반복문을 돌며 해당 원소 위치에서 가장 긴 부분 수열의 길이를 구하는 방식으로 구해도 되..