최장 증가 부분 수열(LIS, Longest Increasing Subsequence)최장 증가 부분 수열은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘이다.예를 들어 주어진 수열이 위와 같을 때 만들어 질 수 있는 증가하는 부분 수열은 위와 같이 같은 색으로 묶인 {2, 4}, {1, 2, 3}, {1, 5, 6} 등 여러가지가 있을 수 있지만위 그림과 같이 원소 5개로 이루어진 {1, 2, 3, 5, 6}이 수열 A에서 가장 긴 증가하는 부분 수열이다. 이렇게 최장 증가 부분수열을 구하는 알고리즘에 대해 알아보자.풀이방법LIS 길이 구하기 - DP: O(n^2)LIS 길이 구하기 - 이분탐색: O(n log n)DP를 이용하여 구할 경우 구현이 간단하지만 시간복잡도가 O(n^..

백준 BOJ 11053 가장 긴 증가하는 부분 수열 - JAVA - 실버2문제https://www.acmicpc.net/problem/11053문제 분석조건첫째 줄에 수열의 크기, 둘째 줄에 수열이 주어짐가장 긴 증가하는 부분 수열의 길이 출력풀이방법LIS 알고리즘을 활용하여 풀이코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Bu..