기록방

👉 문제링크🔸 문제 분석 🔸전형적인 최장 증가 부분 수열 (LIS) 문제이다.LIS의 DP 풀이는 O(n^2) 이고, 이분탐색 풀이는 O(nlogn)이다.여기서는 n이 1000이므로, DP 풀이를 사용했다.🔸 문제 풀이 🔸DP 배열을 만들어 사용한다.DP 배열에는 현재 인덱스를 포함해서 만들어지는 가장 긴 증가하는 부분 수열의 길이를 저장한다.배열을 순회하며, 이전 인덱스들 중 DP 배열 값의 최대값 + 1을 저장한다.dp[i] = max(dp[i], dp[j] + 1)🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;..

👉 문제링크 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 🔸 문제 분석 🔸 주어진 수열 A의 가장 긴 증가하는 부분 수열 (LIS)의 길이를 출력한다. 🔸 문제 풀이 🔸 n이 100만이므로 LIS의 간단한 풀이 법인 DP를 사용하면, O(n^2)으로 1조로 시간을 초과한다. LIS의 두 번째 풀이법인 이분 탐색을 이용해 O(nlogn)으로 풀이한다. (600만) LIS 배열을 입력 배열 원소를 하나씩 골라 채워간다. 입력 배열의 원소를 채울 자리는 이분 탐색으로 구한다. 🔸 코드 🔸 import java.i..

최장 증가 부분 수열(LIS: Longest Increasing Subsequence)은 원소 n개의 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 말한다. ex) 수열 A = {10, 20, 10, 30, 20, 50} 의 경우 LIS = {10, 20, 30, 50} 이고, 길이는 4이다. LIS의 풀이 알고리즘은 대표적으로 DP와 이분 탐색이 있다. DP를 활용한 LIS 구현dp[ i ] = max( dp[ i ] , dp[ i - 1] + 1 )dp 배열에 각 인덱스의 원소를 포함 한 LIS의 최대 길이를 저장한다.(현재 인덱스의 앞쪽 dp 배열을 확인해 최대값 + 1. 혹은 현재 dp 배열 값 중 큰 것을 저장한다.)..