https://www.acmicpc.net/problem/12738 풀이: 가장 긴 증가하는 부분 수열 5 참고 코드: 사용언어 : python 1 2 3 4 5 6 7 8 import bisect input() q=[] for i in map(int,input().split()): s=bisect.bisect_left(q,i) if s!=len(q):q[s]=i else:q+=[i] print(len(q))

https://www.acmicpc.net/problem/4198 풀이: 가장 긴 증가하는 부분수열 문제와 비슷하게 풀 수 있다. 가장 긴 증가하는 부분 수열 5 참고 1 ~ N 까지의 모든 차량을 살펴보면서 진행한다. 현재 차량이 i 일 때, i번째 차량을 기준으로 생각한다. i+1 ~ N 까지의 차량 중 i 번째 차량을 시작점으로 가장 긴 증가하는 부분수열의 길이를 구하고, 반대로 가장 긴 감소하는 부분수열의 길이를 구한다. 두 부분수열의 길이를 합한 값 중 가장 큰 값을 찾는다. 코드: 사용언어 : python

https://www.acmicpc.net/problem/11003 풀이: dequeue를 사용하는 문제이다. 간단하게 풀 수 있다. 0 번째 숫자부터 N번째 숫자까지 진행한다. 현재 위치가 i일 때, 큐에 마지막에 들어있는 값이 현재 위치의 값보다 크다면, pop한다. 이 것을 현재 위치의 값이 더 클 때까지 반복한다. 즉, 큐의 마지막 값이 현재 값보다 작은 값이 나올때까지 반복하게 된다. 큐의 마지막 값이 현재 값보다 작거나, 큐가 비어있다면, 큐에 마지막에 현재 값을 push해준다. 맨 앞이 가장 작은 값이기에 맨 앞의 값을 출력해줄 것이나, 맨 앞에 값이 i-L+1 ~ i 사이에 오는 값인지 확인하는 작업이 필요하다.

https://www.acmicpc.net/problem/2568 풀이: 가장 긴 증가하는 부분수열 문제이다. B번 전깃줄의 위치를 A번 전깃줄의 위치를 기준으로 정렬한 뒤, B를 기준으로 가장 긴 증가하는 부분수열을 찾으면 되는 문제이다. 예를들어 예시에서 A 1 2 3 4 6 7 9 10 B 8 2 9 1 4 6 7 10 위와 같이 정렬된다. 이렇게 정렬 되었을 때, B를 기준으로 가장 긴 증가하는 부분수열은 1, 4, 6, 7, 10 이 되고 남은 8, 2, 9 에 대응되는 A값은 1, 2, 3 3개이다.

https://www.acmicpc.net/problem/14003 풀이: 가장 긴 증가하는 부분 수열을 구하는 문제이다. 수열의 0 ~ N 번째 까지 숫자들 중 가장 길게 증가하는 부분 수열을 만들면 된다. 배열을 하나 만든 후 수열의 숫자를 배열에 하나 씩 넣는다. 넣을 때에는 규칙이 있는데, 현재 숫자가 배열의 맨 오른쪽의 숫자보다 크다면, 가장 오른쪽에 추가해 주고, 만약 배열의 숫자 중 현재 숫자가 더 작은 숫자가 있다면, 현재 숫자로 교채해 준다. 이렇게 된다면, 배열은 자동적으로 정렬되게 되고, 최종적으로 만들어진 배열의 크기가 가장 긴 증가하는 부분 수열의 길이가 된다.

https://www.acmicpc.net/problem/11000 풀이: 그리디 문제이다. 강의 시간을 시작 시간 기준으로 정렬해 놓는다. 맨 처음 우선순위 큐에 0을 넣어놓는다. 강의 시작 시간이 제일 적은 것부터 우선순위 큐의 맨 앞의 값과 비교한다. 만약, 강의 시작 시간이 큐의 맨 앞의 값보다 크다면, 큐에서 pop해준다. 강의 끝나는 시간을 우선순위 큐에 pop 해준다. 이렇게 되면, 만약, 강의를 연달아 할 수 있다면, 강의실 개수(큐의 크기)는 유지되고, 연달아 할 수 없다면, 강의실 개수는 늘어나게 된다. 마지막으로 강의실 개수를 출력하고 끝낸다.