문제 링크 1. 문제 풀이 교차하지 않도록 제거해야 하는 전깃줄의 최소 개수를 구해야 하는 문제로 전깃줄이 교차하지 않을 경우 $A$ 의 위치 번호가 증가할수록 연결된 $B$ 의 위치 번호도 증가한다는 점에서 LIS 를 활용하면 해결할 수 있다. $A$ 의 위치 번호와 $B$ 의 위치 번호를 쌍으로 묶고 한 쪽 위치 번호를 기준으로 오름차순...

문제 링크 1. 문제 풀이 원뿔대의 윗면의 지름($D_1$), 아랫면의 지름($D_2$), $K$ 가 주어졌을 때, 컵라면의 높이의 제곱($H^2$)을 구해야 하는 문제로 피타고라스 정리를 활용하면 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; pub...

문제 링크 1. 문제 풀이 수열 $A$ 에 대한 가장 긴 증가하는 부분 수열의 길이와 실제 수열을 구하는 문제로 전형적인 LIS 알고리즘을 활용하는 문제다. 수열의 크기 $N$ 이 최대 $1,000,000$ 이어서 2중 반복문 대신 이분 탐색을 활용한 LIS 를 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java]...

문제 링크 1. 문제 풀이 수열 $A$ 에 대한 가장 긴 증가하는 부분 수열의 길이와 실제 수열을 구하는 문제로 전형적인 LIS 알고리즘을 활용하는 문제다. 수열의 크기 $N$ 이 최대 $1,000$ 이어서 2중 반복문을 활용하면 간단하게 해결할 수 있다. 실제 수열의 경우 dp 배열을 역순 탐색해도 하나를 구할 수 있지만 일반적인 구현인...

문제 링크 1. 문제 풀이 $1$ 부터 $N$ 까지 한 번씩 등장하는 두 수열 $A$, $B$ 의 LCS를 구하는 문제로 $N$ 이 최대 $100,000$ 이어서 일반적인 $O(N^2)$ 의 시간복잡도를 갖는 LCS 알고리즘으로는 해결할 수 없다. 해당 문제는 각 자연수가 한 번씩만 등장한다는 점에서 LIS를 활용하면 해결할 수 있다. 포...

문제 링크 1. 문제 풀이 수열 $A$ 에 대한 가장 긴 증가하는 부분 수열의 길이를 구하는 문제로 전형적인 LIS 알고리즘을 활용하는 문제다. 수열의 크기 $N$ 이 최대 $1,000,000$ 이어서 2중 반복문 대신 이분 탐색을 활용한 LIS 를 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] impor...

문제 링크 1. 문제 풀이 수열 $A$ 에 대한 가장 긴 증가하는 부분 수열의 길이를 구하는 문제로 전형적인 LIS 알고리즘을 활용하는 문제다. 수열의 크기 $N$ 이 최대 $1,000,000$ 이어서 2중 반복문 대신 이분 탐색을 활용한 LIS 를 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] impor...

문제 링크 1. 문제 풀이 수열 $A$ 에 대한 가장 긴 감소하는 부분 수열의 길이를 구하는 문제로 전형적인 LIS 알고리즘을 활용하는 문제다. 수열의 크기 $N$ 이 최대 $1,000$ 이어서 2중 반복문을 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import jav...

문제 링크 1. 문제 풀이 수열 $S$ 가 $S_k$ 를 기준으로 증가하다 감소하는 경우의 최대 길이를 구하는 문제로 LIS 를 응용하면 해결할 수 있다. 수열의 앞에서 뒤로 이어지는 LIS와 뒤에서 앞으로 이어지는 LIS를 각각 구한다면 $S_k$ 를 기준으로 앞에서부터 $S_k$ 까지 증가하는 LIS는 앞에서 뒤로 이어지는 LIS에서,...

문제 링크 1. 문제 풀이 수열 $A$ 에 대한 가장 긴 증가하는 부분 수열의 길이를 구하는 문제로 전형적인 LIS 알고리즘을 활용하는 문제다. 수열의 크기 $N$ 이 최대 $1,000$ 이어서 2중 반복문을 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import jav...