컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 해결 알고리즘 LIS알고리즘에서 길이와 수열을 구하는 문제이다. 좀 달랐다면 여기서는 제거해야할 원소의 갯수와 위치를 출력한다는 점인데, 그 부분은 record 배열에서 LIS가 아닌 부분을 출력하면 그만인 문제이다. 아래의 링크에 자세한 설명이 있다. https://kimmessi.tistory.com/191 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력..

최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 수열을 최장 증가 부분 수열이라고 한다. 이 최장 증가 부분 수열 알고리즘을 간단하게 구현하는 방법은 DP를 사용하는 것이다. 다이나믹 프로그래밍을 이용한 최장 증가 부분 수열 for(int i=1;i dp[i]) dp[i] = dp[j] + 1; } result = max(result, dp[i]); } 각 수열의 원소까지의 최장 증가 부분 수열의 크기를 dp배열에 입력을 해주는 알고리즘이다. 처음 원소부터 해당 원소까지 for문을 돌리는데 이때, for문에서 돌리는 원소의 크기보다 해당 원소의 크기가 크고 최장 증가 부분 수열의 크기는 ..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 해결 알고리즘 이분 탐색을 이용한 LIS알고리즘을 이용한다. https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 이용해 푼 LIS알고리즘 https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (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 문제 해결 알고리즘 똑같이 이분탐색을 쓴 LIS 알고리즘을 이용해주는데 이 때, 진짜 LIS 수열을 출력해주는 것이 어려운 문제였다. https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제 해결 알고리즘 LIS알고리즘 (최장 증가 부분 수열 알고리즘)을 써준다. 이 때, $O(n \mathrm{log} n)$ 알고리즘을 사용한다 (이분 탐색). https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 이용해서 풀면 시간초과가 난다 (O($ \mathrm{n^2}$)) 그러므로 이분탐색 (O($ \mathrm{ nlogn}$))으로 문제를 풀어야한다. lower_bound : 해당 원소보다 큰 작은 원소를 찾음. (이분탐색) 1. 벡터(v)에 주어진 원소들을 입력받는다. 2. 벡터(vt)에 가장 작은 원소 (-1)를 넣는다. 3. 만약 v[i]의 크기가 vt의 마지막 ..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 알고리즘 1. 배열(v)과, 수열 저장 배열(dp)를 선언한다. 2. 수열 저장 배열(dp)에 처음(first)에는 처음부터의 가장 긴 증가하는 부분 수열의 원소 개수를 저장하고, 두 번째(second)에는 바로 전의 원소의 인덱스를 저장하도록 설정한다. 수열의 전에 아무 원소도 없는 원소에는 second..