![]()
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 증가하는 수열 -> 감소하는 수열 형태로 나오기때문에 lis 알고리즘을 일단 떠올려야 한다. 왼쪽에서 출발하여 증가하는 수열을 DP로 접근하여 뽑은 결과를 DP1 오른쪽에서 출발하여 증가하는 수열을 DP로 접근하여 뽑은 결과를 DP2 for 문으로 0~수열의길이 까지 순회하여 DP1[i]+DP2[i]-1 이 가장 큰 값이 정답 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..
![]()
https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 문제 풀이 전깃줄이 서로 꼬여야 하지 않아야 하므로 가령 , 4 -> 1 번 전봇대로 가는 선을 제거해야 꼬이지 않는다. 즉 , 반대쪽의 전봇대의 번호가 증가하는 수열의 형태면 꼬이지 않으므로 LIS 알고리즘을 통해 해결해야한다. LIS에 대한 이전 포스팅에서 해결방법이 3가지가 있다고 했는데 , 문제에서 조건을보면 N의 갯수가 10만개가 넘어간다. N^2 이상의 시간복잡도를 가지는..
