99클럽 코테 스터디 27일차 TIL: LIS

문제

https://www.acmicpc.net/problem/11722

풀이

이 문제는 LIS 라는 유명한 알고리즘이다.
이미 알고있는 알고리즘이였는데 문제를 풀어본 건 엄청 오랜만이였다.

dp로 구하는 방법이랑 이분탐색으로 구하는 방법이 있었던 것 정도만 기억이 났고..
dp로 구하는 방식은 어렴풋이 기억이 나는데 이분탐색방식은 기억이 잘 나지 않았다.

일단 dp로 풀어보고 이분탐색 방식을 학습하고자 했다.

dp로 푸는 방법은 간단하다.
먼저 dp 배열을 선언하고 dp[n]은 n까지의 수열 중에서 가장 긴 감소하는 부분 수열의 길이를 의미한다.

일단, 첫 항은 $a1 = 1$ 이다. 왜냐하면 자기 자신의 원소도 부분 수열이기 때문이다.

[3, 2, 4, 1] 라는 수열이 있을때를 한번 살펴보자
dp[1]일 때, 즉 [3] 만 봐보자, 길이는 1이다. (dp[1] = 1)

dp[2]일 때, [3, 2] 때는 3 < 2 이므로 길이가 2가 된다. (dp[2] = 2)

dp[3]일 때, [3, 2, 4] 를 살펴보자.
[3, 2, 4] 일 때, 우선 4를 고정해서 보자..! 4와 첫항을 비교해보자.
3 < 4이다. dp[1]일 때, 길이가 1인데 3 < 4이기 때문에 해당 부분수열에 4를 붙일 수 없다. (3보다 커서 감소하지 않으므로)

4와 두번째항 (2)를 비교해보자.
3 < 4이다. dp[2] = 2 이고, 첫항때와 마찬가지로 뒤에 4를 붙일 수 없다. dp[3] = 2가 되겠다.

dp[4] 일 때. 위 동작과 동일하게 체크해보자
3 > 1, dp[1] = 1, dp[4] = dp[1] + 1 이다.

이 말을 조금 풀어쓰면 dp[1]은 1인데 dp[1]일 때 부분수열은 [3]이고, 여기 뒤에 1을 붙여서 [3, 1]을 만들 수 있다.
따라서 dp[4] = dp[1] + 1 이 된다. = 2

두번째항.. 세번째 항 전부 비교해보자.

점화식은 다음과 같을 것이다. (이렇게 쓰는게 맞는지 모르겠다..)
$if\ (i \gt j,\ \ array(i) \lt array(j))\ dp(i) = max(dp(i), dp(j) + 1)$

이를 이중for문을 사용하여 $O(n^2)$ 시간복잡도를 소요하는 코드로 짜서 풀 수 있다.

소스코드

후기

오랜만에 풀어본 LIS 알고리즘 이였다.
담에 이분탐색으로도 풀어봐야징..