https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 1. Logic 처음 보면 무슨 문제가 싶지만 문제를 읽으면서 예제를 보면 LIS문제인것을 알 수 있다. 문제 푸는 로직을 나열해보자면 1. 입력을 받은 수들을 vector에 pair로 저장을 하고 A를 기준으로 오름차순 정렬한다. 2. lis vector의 back값과 계속 비교하여 LIS를 이루는 값이 들어오면 lis에 넣어주고 cnt를 올려준다. 혹은 탐색값이 lis의 back보다 더 작..
LIS
https://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 1. Logic - 기본 구성은 가장 긴 증가하는 부분수열 2, 3과 똑같다. 하지만 여기서는 역추적을 통해 LIS가 어떻게 구성되었는지 경로를 출력해야한다. 경로를 갱신해 줄 때 아무값이나 막 넣어주면 안되기 때문에 첫번째로 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 1. Logic 이전 가장 긴 증가하는 부분 수열 문제에서는 DP를 사용해서 풀었다. DP를 사용하는 풀이에서는 전체를 돌면서 확인 하며 메모이제이션 했기때문에 시간복잡도가 O(N^2)이었다. 하지만 이 문제에서는 입력값이 엄청 많기 때문에 N^2으로 풀지 못하기 때문에 시간복잡도가 O(nlogn)을 가지는 이분탐색 기반으로 풀어야 한다. binary search를 구현해서 푸는 방법과 C++의 ..
https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1. Logic - 줄세우기 문제는 최장 증가 부분 수열(LIS) 를 사용해서 풀이한다. LIS로 풀이하는 이유는 이미 순서대로 서있는 가장 많은 수를 제외한 나머지의 위치를 변경해주면 되기 때문이다. 2. Code #include using namespace std; int n; vector vec; int dp[1000001]; int main() { ios_base::sync_with_stdio(f..
