[Java] LIS, LCS

1. LIS란? Longest Increasing Subsequence최장 증가 부분 수열어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만든다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 뜻한다. 2. LIS의 길이 구하기 동적 계획법으로 최장증가수열의 길이를 구하는 방법에 대하여 알아보자.  최장 증가 부분 수열최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주namu.wiki 설명 참고. 가. O(N^2) 시간복잡도는 O(N^2)이다.int lis(int[] arr) { int n = arr.length; int[] dp = new int[n]; // 배열의 i번째 요소를 마..

2024.06.13