매일 조금씩

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전체 전깃줄 개수 - 전깃줄의 최장증가 수열 개수 = 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수 A 값의 순서로 B 값을 수열로 만들어보면 {8, 2, 9, 1, 4, 6, 7, 10} 이다. 이 수열의 최장증가수열의 개수를 구해서, 전체 전깃줄 개수에서 빼면 답을 구할 수 있다.입력이 정렬되어 들어오지 않기 때문에 A값 기준으로 정렬한 후, 이분 탐색 이용하..

LIS 알고리즘이란? LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 풀이 1. DP로 풀기 시간 복잡도 O(N^2) 이기 때문에 원소의 개수가 작은 경우에는, 해당 방법으로 문제를 풀 수 있다. {10 20 10 30 20 50} 수열 1 2 3 4 5 6 10 20 10 30 20 50 DP[i] = i번째 원소를 포함하는 증가 수열의 최대 원소 개수 N=1 1 2 3 4 5 6 1 N=2 1 2 3 4 5 6 1 2 현재 index의 원소 값과, 그 미만의 index의 원소 값을 비교 현재 원소보다 작은 원소가 있다면 해당 index의 dp값 중 최대값에 + 1을 한 것..