섹션 10 Dynamic Programming - 3. 최대 부분 증가수열(LIS)

문제 설명

N개의 자연수로 이루어진 수열이 주어질 때 그 중에서 가장 길게 증가하는 부분 수열을 찾는 문제이다. 단, 이 부분 수열은 반드시 원래 수열의 순서를 유지해야 하며 연속되지 않아도 된다.

예시

 

입력
8
5 3 7 8 6 2 9 4

출력
4

• 위 예제에서 가능한 최대 증가 수열은 3 → 7 → 8 → 9이며 길이는 4이다.

---

입력

• 첫 줄에 수열의 길이 N이 주어진다. (3 ≤ N ≤ 1,000)
• 둘째 줄에 N개의 자연수가 주어진다.

출력

• 부분 증가 수열 중 가장 긴 수열의 길이를 출력다.

---

코드 구현

import java.util.*;

public class Main {
	static int[] dy;

	public int solution(int[] arr) {
		int answer = 0;
		dy = new int[arr.length];
		dy[0] = 1;

		for (int i = 1; i < arr.length; i++) {
			int max = 0;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] < arr[i] && dy[j] > max) {
					max = dy[j];
				}
			}
			dy[i] = max + 1;
			answer = Math.max(answer, dy[i]);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		System.out.print(T.solution(arr));
		sc.close();
	}
}

---

코드 설명

• dy[i]: i번째 수를 마지막 원소로 하는 최대 부분 증가 수열의 길이
• 처음 수는 자기 자신만으로 수열이 되므로 dy[0] = 1
• 이후 각 수에 대해 자신보다 앞에 있는 수들 중 작은 값을 찾고, 그 중 가장 긴 증가 수열의 길이에 1을 더해 저장
• 그 중 가장 큰 값을 최종 답으로 출력

---

시간 복잡도

• O(N²) : 이중 for문을 통해 각 원소마다 그 이전까지 비교하므로 최악의 경우 1,000 * 1,000 = 1,000,000회 연산

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런