[BOJ] 가장 긴 증가하는 수열 (LIS) 시리즈; 그리디, DP, 이진탐색 (JavaScript)

 

회고

역시나 DP는 점화식이 가장 큰 관건인 것 같다

구현한 코드 자체는 매우 간단하지만 점화식 구하는 것이 어려웠다

점화식을 제대로 못 구하면 몇 시간을 붙잡고 있어도 코드가 산으로 가고

제대로 된 답을 구하기 어려워진다는 걸 다시 한번 느꼈다..😖

 

---

문제 풀이

 

완전 탐색으로 모든 부분 수열을 구하는 방식으로 구현하면

시간복잡도가 O(N^3) ~ O(2^N)까지 증가하기 때문에 매우 비효율적이다

가장 첫번째 문제인 11053번 문제만해도 최대 입력값이 1,000인데,

시간복잡도가 2^1000이 되면 당연히 시간 내 답을 구할 수 없다

 

최장 증가 부분 수열의 길이; 그리디한 방법

수열의 '길이'만 구하는 경우에는 그리디한 방법으로 해결할 수 있다

최장 길이를 구할 때 실제 부분 수열을 가지고 구하는 것이 아니라는 것이다

그래서  해당 부분수열까지 출력해야하는 아래 14002번 문제에서 동일한 방식으로 구현하게 되면 첫 케이스부터 틀리게 된다

 

1D array DP로 시간 복잡도 O(N^2)에 해결하는 풀이

백준 11053번 가장 긴 증가하는 부분 수열 : www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

위에서도 잠시 언급했듯이, 이 문제는 최대 입력 값이 1,000이기 때문에 O(N^2)로 구현해도 충분히 답을 구할 수 있다.

 

점화식 찾기

1. 특정 원소가 어떤 부분 수열의 마지막 원소로 추가된다고 할 때,
2. 그 원소가 앞의 원소들보다 가장 큰 원소라면 새로운 최장 증가 부분 수열이 생성되는 것으로 볼 수 있다
3. 그러면 이전까지의 최장 증가 부분 수열 길이에 1을 더한 것이 그 수열의 최장 증가 부분 수열 길이가 된다

위 과정을 코드로 구현하면 2중 for문 형태 코드로 구현할 수 있고,

따라서 시간 복잡도는 O(N^2)가 된다

 

풀이 코드

위 코드에서 모든 비교 과정을 출력해보면 위와 같다

max 값 구하는 과정을 DP 중간에 넣나(216ms) 마지막에 Math.max 함수로 구하나(220ms) 시간 상 큰 차이는 없었다

정렬 후 최댓값을 구한다면 O(logN)에 가능하지만 DP 과정에서 구한다면 O(N) + 대입연산 시간 이기 때문이지 않을까

 

---

이진 탐색으로 시간복잡도 O(NlogN) 에 해결하는 풀이

백준 12015번 가장 긴 증가하는 부분 수열2 : www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

백준 12738번 가장 긴 증가하는 부분 수열3 : www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

이 문제들은 풀이법이 쉽게 이해되지 않아서 여러 자료를 참고했다..

 

여기서는 최대 입력이 100만~200만이기 때문에 O(N^2) 코드로는 당연히 시간 초과 에러가 난다

위 코드와는 좀 다른 로직과 이진 탐색 중 lower_bound를 활용해 O(NlogN)으로 해결할 수 있다

C++에는 lower_bound 함수가 내장 라이브러리에 구현되어 있어 편하게 가져다 쓰기만 하면 되지만,

JavaScript나 Python 사용자는 직접 구현해야 한다.

이진 탐색 코드도 모양은 만만해보이지만 > - >=, +1 같은 세부 조건을 잘 지정하지 않으면 엉뚱한 답이 나오기 때문에

많은 연습이 필요해 보인다

 

여기서도 실제 부분 수열을 구해서 답을 구하는 것이 아니라,

임의의 배열(memo)을 하나 생성하고 nums에서 하나씩 값을 가져와서 정렬된 배열로 계속해서 업데이트 한다

이때 memo의 최대값보다 현재 비교 대상인 값이 큰 경우에만 memo에 추가하고, 

그렇지 않은 경우에는 memo에서 lower_bound 인덱스를 구해 해당 인덱스 값으로 대입한다

 

증가 부분 수열이 좀더 길어지기 위해선 최대값은 좀더 커지고 최소값, 중간값들은 적어지는 것이 좋기 때문에,

이를 위해 lower_bound 함수를 사용하게 된다

좀더 자세한 설명은 아래 geekforgeeks 설명을 참고하자..

 

풀이 코드

12738번은 입력 범위가 -100만~100만으로 범위만 2배로 늘어나고 코드는 동일하다

C++왕국에 깃발을 꽂을 수 있어 감격..런타임도 3배 밖에(??) 차이 안나..

 

---

최장 증가 부분 수열의 길이와 해당 부분 수열; 부분 수열 구하는 로직을 추가

최장 연속 부분 수열의 길이은 물론 해당 수열도 구하는 문제

 

시간 복잡도 O(N^2)에 해결하는 풀이

백준 14002번 가장 긴 증가하는 부분 수열4 : www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

부분 수열 길이를 구하는 로직 자체가 단순히 이전 최대값에서 1을 더해가는 것이기 때문에

실제 부분 수열임을 보장해 주지 않는다

따라서 1번 문제 로직이 끝난 후,

뒤에서부터 subMax를 하나씩 줄이면서 subMax와 memo[i]의 값이 같은 경우 nums[i]를 배열에 추가하여

부분 수열을 구한다

증가 부분 수열이라면 memo[i] 값이 1부터 max까지 1씩 증가하기 때문이다

 

풀이 코드

 

LIS 2, 3번에 수열 출력이 더해진 문제

to be continued..

백준 14003번 가장 긴 증가하는 부분 수열5 : www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

---

참고

geeksforgeeks LIS SizeO(NlogN) 풀이 : www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Longest Increasing Subsequence Size (N log N) - GeeksforGeeks

 

아인트라세님 백준 11053, 12015번 풀이 eine.tistory.com/entry/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-Longest-Increasing-Subsequence

[백준 11053 / 백준 12015] 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence) - 1

 

hooongs tech note 님 백준 12015번 풀이 hooongs.tistory.com/129

[백준12015번] 가장 긴 증가하는 부분 수열 2 / Python3

 

승지니어님 LeetCode LIS 문제풀이 www.youtube.com/watch?v=Hq7VjlZRT2Y

 

Tushar Roy님 LIS O(NlogN) 풀이 www.youtube.com/watch?v=S9oUiVYEq7E