컴퓨터하는 kimmessi

최장 증가 부분 수열 (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/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)이란? 어떤 수열에서..

분할정복(Divide and Conquer) 알고리즘이란? 문제의 입력사례를 두 개 이상 작은 입력사례로 분할한다. 계속 분할 하다가 바로 답을 얻을 수 있으면 원래 문제의 답은 얻은 답들을 통합해 구하는 알고리즘 하향식(top - down) 문제풀이 방식이다. 상위 입력사례의 해답은 하위의 작은 입력사례들의 해답을 가지고 구한다. 재귀함수의 작동원리가 이런데, 문제 풀이 중심으로 재귀함수를 작성한다. 이분 탐색(binary search) 재귀함수의 재귀 호출은 분할정복의 하향식 문제풀이 방식과 원리가 같다. 1. [분할(divide)] 배열을 정 가운데 원소를 기준으로 반으로 분할한다(divide). $x$가 가운데 원소보다 작으면 왼쪽 배열을 선택, $x$가 가운데 원소보다 크면 오른쪽 배열을 선택한..

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의 마지막 ..