최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 배열에서 원소들이 오름차순으로 증가하는 가장 긴 부분 수열을 찾는 고전적인 알고리즘 문제입니다. 아래는 자바로 이를 해결하는 프로그램입니다.
예제 코드
public class Demo{
static int incre_subseq(int my_arr[], int arr_len){
int seq_arr[] = new int[arr_len];
int i, j, max = 0;
for (i = 0; i < arr_len; i++)
seq_arr[i] = 1;
for (i = 1; i < arr_len; i++)
for (j = 0; j < i; j++)
if (my_arr[i] > my_arr[j] && seq_arr[i] < seq_arr[j] + 1)
seq_arr[i] = seq_arr[j] + 1;
for (i = 0; i < arr_len; i++)
if (max < seq_arr[i])
max = seq_arr[i];
return max;
}
public static void main(String args[]){
int my_arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int arr_len = my_arr.length;
System.out.println("The length of the longest increasing subsequence is " + incre_subseq(my_arr, arr_len));
}
}실행 결과
The length of the longest increasing subsequence is 5
코드 동작 원리
위 코드에서 Demo라는 클래스는 배열과 배열의 길이를 매개변수로 받는 정적(static) 메서드 incre_subseq를 포함하고 있습니다. 이 메서드 내부에서는 다음과 같은 과정이 진행됩니다.
먼저 배열 길이와 같은 크기의 새로운 배열 seq_arr를 생성합니다. 이 배열은 각 위치에서 끝나는 증가 부분 수열의 길이를 저장하는 역할을 하며, 초기에는 모든 값을 1로 설정합니다(각 원소 자체만으로도 길이 1짜리 수열이 되기 때문입니다).
그다음 이중 for 반복문을 통해 현재 원소 my_arr[i]가 이전 원소 my_arr[j]보다 큰지 확인하고, 그 경우 seq_arr[i]의 값이 seq_arr[j] + 1보다 작으면 더 긴 수열 길이로 갱신합니다. 마지막으로 seq_arr 전체를 순회하며 최댓값을 찾아 반환하면, 그것이 곧 최장 증가 부분 수열의 길이가 됩니다.
동적 계획법(Dynamic Programming) 활용
이 알고리즘은 동적 계획법을 활용한 대표적인 예시입니다. 한 번 계산한 값을 배열에 저장해 두기 때문에 재귀 방식처럼 같은 값을 반복해서 계산할 필요가 없습니다. 이후에 이미 계산된 값이 필요할 때는 배열에서 바로 가져와 사용하므로 시간 복잡도가 O(n²)로 효율적으로 개선됩니다.