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

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

문제 링크 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. 이분 탐색 LIS [Java] import j...

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

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

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

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

문제 링크 1. 문제 풀이 서로 다른 세 점이 주어졌을 때, 적절한 점 $D$ 로 평행사변형을 만들 수 없으면 $-1$ 을 출력하고, 만들 수 있으면 만들 수 있는 평행사변형 중 가장 큰 둘레의 길이와 가장 작은 둘레의 길이의 차를 출력해야 하는 문제다. 평행사변형을 만들 수 없는 경우는 세 점이 일직선 상에 위치하는 경우로 세 점의 좌표가 ...

문제 링크 1. 문제 풀이 주어진 수가 완전수인지 판단하는 문제로 완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 수이다. 약수는 $1$ 부터 주어진 수보다 작은 수까지 모든 수로 나누어서 나머지가 $0$ 이 되는지 판단하면 된다. 2. 코드 1. 구현 [Java] String 을 타입 매개변수로 갖는 리스트를 활용해서 약수...