알고리즘||코딩테스트/LIS

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 사용한 알고리즘 : LIS, 이진탐색 풀이 전략 위 문제에서 주어진 예제를 그대로 사용할 때, 앞 A 전봇대를 오름차순으로 정렬하고 B 전봇대를 기준으로 LIS를 구하면 [3,6,7,9,10] 이라는 결과가 나옵니다. 따라서 (처음 입력받은 전깃줄의 개수) - (LIS로 구한 배열의 크기)를 구해 제거해야 할 전깃줄의 개수를 구할 수 있습니다. 하지만 문제에서 제거해야할 전깃줄의 개수와 전깃줄..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 사용한 알고리즘 : LIS(Longest Increasing Subsequence), 이분 탐색 풀이전략 LIS를 구하기 위한 전략은 아래와 같다. 위 그림처럼 입력받은 수가 수열의 최우측 원소와 비교했을 때 더 작다면 기존에 입력된 수열에서 같거나 더 크지만 가장 작은 수와 교체한다. 만약 입력받은 수가 수열의 최우측 원소보다 크다면, length의 길이를 1 늘리고 수열 최우측 바로 옆 인덱스..