섹션 10. dynamic programming(동적계획법) 3. 최대 부분 증가수열(LIS)

문제

• N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
• 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

입력

• 첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,
• 둘째 줄은 N개의 입력데이터들이 주어진다.

출력

• 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다.

동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이렇게 나누어진 작은 문제들을 메모이제이션을 사용해서 최종적으로 본래 문제의 해결방안을 찾는 것을 말한다.

---

설계과정

1. arr[ ] 에 입력값을 넣고 dy[ ] 배열에 i 번째 숫자를 마지막 항으로 하는 최대 증가수열의 길이를 넣는다.

2. 1번째부터 arr.length 까지 돌면서 max 값을 찾는다.

3. i-1 부터 0까지 감소하면서 j 번째 항이 i 번째 항 바로 앞이고, j 번째 항이 max보다 큰 경우에 max에 dy[i] 값을 넣는다.

4. 그 후 dy[i]에 max + 1을 넣어준다.

5. 마지막으로 result와 dy[i]중 큰 값을 찾아서 result에 넣고, result를 출력한다.

---

풀이과정

1.  각 변수들을 선언한다.

• arr[ ] : 입력받을 값들을 저장한다. 
• dy[ ] : i 번째 숫자를 마지막 항으로 하는 최대 증가수열의 길이를 저장한다.
• max : 최대 길이를 저장한다.

2. dy[ ] 배열을 선언하고 0번째에 1을 넣어준다.

• 맨 처음 항에 가는 최대 길이는 무조건 1이기 때문이다.

3. 이중 for문을 사용해서 i-1부터 0까지 감소하는 for문을 작성한다. 

 

4. j 번째 항이 i 번째 항 바로 앞이고, j 번째 항이 max보다 큰 경우에 max에 dy[i] 값을 넣는다.

 

5. 그 후 dy[i]에 max + 1을 넣어준다.

• 문제 예시를 통해 자세한 과정을 알아보자.
• 아래는 입력받은 arr 배열이다.

• 코드를 전부 수행하면 dy 배열에는 다음과 같은 배열이 완성된다.

• 그 이유에 대해 알아보자.
• 먼저 dy[0]은 5이다. 5 앞에 아무런 숫자도 없으므로 5까지의 길이인 1을 넣는다.
• dy[1] 은 3이다. 3 앞에 있는 숫자는 5인데, 이는 3보다 작지 않으므로 3 하나의 길이인 1을 넣는다.
• dy[2] 은 7이다. 앞에 있는 숫자는 각각 3과 5이다. 기존에 두 숫자까지 가는 길이는 각각 1이므로 여기에 7까지 가는 길이 1을 더하면 [3, 7] 과 [5, 7] 모두 최대 길이가 2가 된다.
• dy[3] 은 8이다. 앞에는 5, 3, 7 세 숫자가 있다. 7이면 까지의 거리인 2에 1을 더해서 3이 된다. 3과 5는 최대 길이가 1이므로 7까지의 거리보다 작으니 넘어간다.
• 해당 과정을 반복한다.
• 좀 더 보자면 dy[6] 은 9이다. 9보다 작으며 최대 길이를 가지고 있는 dy[3]에 있는 3에서 1을 더해서 최대 길이가 4가 된다.

6. Math.max() 를 사용해서 result와 dy[i] 중 더 큰 값을 result에 넣고, result를 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.