📖 최장 증가 수열 (Longest Increasing Subsequence)

---

💬 문제 예시

---

다음과 같은 수열이 나열되있다. 이 배열의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분의 수열 길이를 구하시오. [ 3, 2, 6, 4, 5, 1 ]

• 최장 증가 수열은 2, 4, 5 이고, 길이는 3이다.

◾ 방법 1

• 해당 수열 원소들을 차례로 확인하는 방법
• 확인하려는 해당 원소input[i]의 전 원소들(범위: j = 0 ~i)과 비교함
• 자기 자신보다 작을 때 나의 현재 최장 증가 수열 길이length[i]보다 나보다 작은 수input[j]의 최장 증가 수열 길이dml +1인 값 length[j]+1 더 클 때 큰 수 갱신
• 시간 복잡도 : O(n^2)

int[] input = {3, 2, 6, 4, 5, 1};
int[] length = new int[6]; // 해당 인덱스에서 끝나는 최장 증가 부분 수열의 길이

for (int i = 0; i < 6; i++) {
	lis[i] = 1;
	
	for (int j = 0; j < i; j++) {
		// 현재 나(i)보다 이전 값(j)이 더 크면 넘어가
		if(input[j] > input[i]) continue;
		
		if(length[j] + 1 > length[i]) {
			length[i] = length[j] + 1;
			
		}
	}
}

// 이중 가장 긴 길이가 답
for (int i = 0; i < 6; i++) {
	System.out.println(length[i]);			
}

◾ 방법 2

이분 탐색을 이용한 방법

• 길이와 해당 원소들을 알 수 있음
• 시간복잡도 : O(nlogn)

public static void main(String[] args) {
	int[] input = {3, 2, 6, 4, 5, 1};
	int[] lis = new int[6]; // 최장 증가 수열 집합
		
	lis[0] = input[0];
		
	int i = 1;
	int j = 0;
	while (i < 6) {
		// input[i] 값이 더 크면, lis 배열의 가장 마지막 값 뒤에 삽입
		if (lis[j] < input[i]) {
			lis[j + 1] = input[i];
			j += 1;
		}
		// input[i] 값이 더 작으면, 이분탐색
		else {
		    // 0부터 j까지 탐색하면서 input[i]에 들어갈 위치를 찾아서 idx에 반환
			int idx = binarySearch(0, j, input[i], lis);
			lis[idx] = input[i];
		}
		i += 1;
	}
        
    // 최장 증가 수열의 원소들 출력
	for (int k = 0; k < 6; k++) {
		System.out.println(lis[k]);			
	}
	
}

static int binarySearch(int left, int right, int target, int[] lis) {
	int mid = 0;
		
	while(left < right) {
		mid = (left + right) / 2;
			
		if(lis[mid] < target) left = mid + 1;
		else right = mid;
	}
	return right;
}