[알고스팟] Longest Increasing Sequence

Kyojun Jin·2022년 3월 6일

다이나믹 프로그래밍

다이나믹 프로그래밍 (= 동적 계획법)은 완전탐색에서 기인한다.
대부분 문제를 보면 '어떤 것들을 선택해야 최적의 경우일까?'로 설명될 수 있다.

동적 계획법은 메모이제이션을 통해 반복적인 연산을 줄인다.
반복된다는 것은 특정 조건일 때 하는 연산이 반복적으로 필요할 떄를 말한다.
그때의 결과값을 저장하면 불필요한 연산을 줄일 수 있다.

완전탐색은 현재 상태에서 필요한 값(예: 수들의 합이나 거리)을 계산한 후
가능한 경우의 수만큼 분기하며,
다음 단계에 현재 상태를 전달한다.
다음 단계에 도착하면 전달받은 상태에 따라 또 다른 경우의 수만큼 분기하며
이를 경우의 수가 없을 때까지 반복한다.

이때 상태에 따라 필요한 값이 명확히 존재하며 그 값이 오로지 상태에 영향을 받는다면,
즉 함수가 입력값(상태)으로만 결정이 될 수 있다면 이 함수를 참조적 투명성을 만족한다.
함수가 참조적 투명성을 띈다면, 특정 상태의 값은 항상 정해져 있기 때문에
내가 만약 A상태에서의 값을 계산했다면
어떤 다른 분기에서 A상태에 도달했을 때 이를 다시 계산할 필요가 없다.

특히, 여기서 이 '상태'를 간결하게 하면 할 수록 문제가 쉬워진다.
간결하게 한다는 것은 딱 필요한 것만 가져간다는 뜻이다.
예를 들어 문제에서 어떤 수 x를 부분 증가 수열에 포함시킬지 말지를 정하려고 한다면
그 부분 증가 수열의 마지막 값만 필요하지, 그 뒤의 수가 어떻게 이뤄져있는지는 알 필요가 없다.
즉 직전의 선택 결과만 중요하다

이쯤에서 다이나믹 프로그램을 적용하는 알고리즘 (알고리즘을 적용하는 알고리즘...)을 설계할 수 있다.

문제가 원하는 값(합, 경로 등)이 연속되는 선택에 따라 달라진다.
다음 선택은 오직 직전 선택에만 영향을 받는다.
특정 시점에서의 값이 중복되어 참조될 수 있다.

2번까지 만족하면 완전탐색,
3번도 만족하면 다이나믹 프로그래밍을 적용할 수 있다.

다이나믹 프로그래밍을 시작하기 위해선 먼저
시점을 어떻게 표현할지를 설계해야 한다.
그래야 캐싱을 쉽고 효율적으로 할 수 있다.
다이나믹 프로그래밍은 특정 시점에서 연산될 수 있는 값을 저장해두고 쓴다.
따라서 문제에서 어떠한 일련의 선택을 (주로 마지막 선택) 어떻게 표현할지 정해야 한다.

또한 이러한 반복을 활용해야 한다.
다이나믹 프로그래밍은 항상 초기값이 있다.
반복문 혹은 재귀가 진행될 수록 이 초기값을 이용하고,
그 값을 이용하고, 또 그 값을 이용하는 방향으로 가야 한다.

최종적으로 다이나믹 프로그래밍을 적용하는 방법은 다음과 같다.

문제에서 필요한 선택을 재정의한다.
선택을 추상화하여 간결하게 표현한다. 즉, 상태:값의 1:1 관계를 성립시킨다.
(== 프로그래밍 언어로 표현할 수 있는 방식을 정한다.)
초기값을 이용하여 점점 값을 불릴 수 있도록 방향을 정한다.

적용

문제 정의

이 문제는 수열에서 어떤 수들을 골라야 가장 큰 증가 수열이 될까?로 재정의할 수 있다.

추상화

재정의 된 문제에 따라, 수들을 선택해 나가야 한다.
-> $i$ 번째 수를 선택한다.

따라서 dp[i]는 $i$ 번째 수를 마지막으로 선택했을 때의 증가 부분 수열의 최대 길이이다.

불리기

불리려면 별 다른 과정 없이 값을 얻을 수 있을 때를 먼저 생각한다.
이 문제에선 현재 보고 있는 수열의 길이가 1일 때이다.
그때는 묻지도 따지지도 않고 무조건 길이가 1이기 때문에, 수열의 길이를 차차 늘려가야 하는 것이다.

이를 일반적으로 표현하자면,
$j$ 번째 수를 마지막으로 선택했을 때의 결과는
$j=1$ 일 때는 무조건 1이고,
다음 $k$ 번째 수를 선택한 결과를 계산할 때 이용해먹을 수 있기 때문에, $(k > i)$
$j$ 값을 점점 늘려나가야 한다.

그럼 dp[j]를 구하려면?
$i$ 를 이용한다. $(j > i)$
여기서 $i$ 는 전 단계의 $j$ 들이다. $i$ 가 증가해서 $j$ 에 이르렀기 때문이다.
그래서 이 dp[j]를 사용할 수 있는 것이다.
$j$ 번째 수를 마지막으로 선택하고 나서 $i$ 번째 수를 추가하게 됐을 때의 수열의 길이를 구할 때
dp[j]를 사용할 수 있다.
arr[i]를 추가하여 dp[i]를 구할 때는 dp[j]와 arr[j]가 중요하지,
dp[j]를 그 값이 되게 하는 실제 수열이 어떻게 되는지는 중요하지 않다.

만약 $i$ 번째 수가 $j$ 번째 수보다 크다면
마지막 수로 $j$ 번째 수를 선택했을 때의 수열에 $i$ 번째 수를 추가할 수 있다.
이때의 길이는 dp[i]가 된다.

이렇게 할 수 있는 이유는 마지막 수보다 큰 수를 수열에 추가하면
수열의 구성요소에 관계 없이 항상 증가하는 수열을 얻을 수 있기 때문이다.
이는 수학적 귀납법으로 증명할 수 있다.

수열의 길이 $n = 1$ 일 때 이 수열은 증가 수열이다.
$n = k$ 일 때 이 수열은 증가 수열이다. ( $a_1 < a_2 < a_3 < ... < a_k$ )
$a_{k+1} > a_k$ 인 $a_{k+1}$ 를 추가하면 $a_1 < a_2 < a_3 < ... < a_k < a_{k+1}$ 이므로
$n = k + 1$ 일 때도 이 수열은 증가 수열이다.

결론: 마지막 수보다 큰 수를 추가하면 그 수는 항상 증가 수열이다.
이렇게 dp를 구하면서 그때마다 최대값을 갱신해주면 답을 알 수 있다.

코드

int maxLen = 0;
for (int i = 0; i < N; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j) {
        if (arr[j] < arr[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
            if (maxLen < dp[i])
                maxLen = dp[i];
        }
    }
}

또 다른 풀이

완전탐색에 기인하는 정석적인 풀이이다.
문제 정의는 위의 풀이와 같다.

$i$ 번째 수에서는 다음 $i+1$ , $i+2$ , $i+3$ ... 등의 수를 선택할 수 있다.
(물론 선택하려는 수는 $i$ 번째 수보다 커야 한다.)
즉 $i$ 에서 $i+1$ , $i+2$ ...로 분기할 수 있다.

추상화

dp[i]는 $i$ 번째 수부터 시작하는 증가 수열의 최대 길이이다.
그래야 $i$ 에서 $i+1$ , $i+2$ ...를 선택하며 분기할 수 있다.
$i$ 부터 시작하는 증가 수열의 최대 길이를 구하는 함수를 lis(i)라고 할 때,
lis(i) = max(lis(i+1), list(i+2), ...)로 구할 수 있을 것이다.

불리기

불리려면 다음 과정 없이 얻을 수 있는 시점을 알아야 한다.

dp[i]가 $i$ 번째 수부터 시작하는 증가 수열의 길이이므로
더이상 분기할 수 없는 특정 시점 $a$ dp[a]는 1이다.
( $x$ > $a$ 인 모든 $x$ 에 대해 arr[a] >= dp[x]를 만족)

마침 lis(i) = max(lis(i+1), list(i+2), ...)로 계속해서 재귀적으로 호출하다 보면 언젠가 분기하지 못하는 경우가 생길 것이다.
이때 반환값은 1이 될 것이고, 그렇게 반환된 값은 이전 재귀 함수에서 사용할 수 있을 것이다.

코드

int lis(int start) {
    if (dp[start] == -1) {
        dp[start] = 1;
        for (int i = start + 1; i <= N; ++i) {
            if (arr[start] < arr[i]) {
                dp[start] = max(dp[start], lis(i) + 1);
            }
        }
    }
    return dp[start];
}

이 함수는 start부터 시작하는 LIS를 구한다.
수열의 최소 인덱스 - 1를 x라고 했을 때,
lis(x)를 호출하면
전체 수열에 대한 LIS의 길이 + 1를 구할 수 있다. (가상의 시작점 arr[x] 포함)

단, 이때 arr[x]은 arr의 모든 원소보다 작아야 한다.

시간복잡도

두 방식 모두 i가 0부터 N까지,
거기서 j가 0부터 i까지 혹은 i부터 N까지 반복되므로
$O(N^2)$ 의 시간복잡도를 가진다.

이분탐색

이분탐색을 이용하는 것은 좀 더 기발하다.
이게 가능한 이유는,
LIS가 무조건 정렬되어 있기 때문이다.
이 생각을 왜 못했을까?
당연히 Increasing 이기 때문에 오름차순으로 정렬되어 있을 것을...
어떤 자료구조가 정렬되어 있다면, 이분탐색을 사용하는 것을 고려해보아야 한다.

풀이

LIS에 $i$ 번째 수를 계속해서 추가해나간다.
만약 $i$ 번째 수 $x$ 가 LIS 안에 있다면 바꿔준다.
없다면 $x$ 보다 작은 가장 가까운 수의 바로 오른쪽에 넣는다.
즉 $x$ 의 lower bound에 값을 꽂는다고 생각하면 된다.
(lower bound = $x$ 이상의 값이 처음 나오는 인덱스)

이는 그리디 알고리즘을 사용하는 것이기도 한데,
왜 그리디인가 하면,
마지막 값을 항상 작은 값으로 유지하기 위한 알고리즘이기 때문이다.

여기서 그리디 알고리즘의 역할은 부분 수열의 마지막 값을 최소로 유지하는 것이고
이분 탐색의 역할은 부분 수열에서 추가할 수 $x$ , 즉 arr[i]를 찾기 위함이다.

참고로 lower bound는 모든 원소가 $x$ 보다 크다면 0을, (배열에 아무것도 든 게 없어도 마찬가지)
작다면 마지막 인덱스 + 1을 반환하며
$\{...,\ a,\ b,\ ...\}$ 에서 $a < x < b$ 인 $x$ 를 찾으면 $b$ 의 인덱스를 반환한다.

목표는 LIS에 $i$ 번째 수를 추가해가는 것이므로
안심하고 lower bound의 결과값을 인덱스로 하는 곳에 수를 넣을 수 있다.

이점을 유의하며 그림을 보자.

그리디적인 측면을 생각한다면 i=3까지는 이해가 쉽다.
마지막 값이 얼마냐에 따라 다음 수열이 정해지는데
길이를 최대화하기 위해선 항상 마지막 값을 최소로 유지하는 게 좋기 때문이다.

하지만 문제는 i=4와 i=5인데,
처음에 이를 이해하느라 시간이 걸렸다.
왜 뒤에 있는 값을 LIS 중간에 넣는지 이해가 안 갔다.
이렇게 되면 LIS가 순서가 꼬여버리는 거고, 이게 LIS라면 그냥 정렬을 하면 되지 않는가?

여기서 기발한 부분이 등장한다.
분명 LIS 배열은 실제 LIS가 아닐 수도 있다.
LIS 중간에 값을 교체하는 이유는
나중에 그 수를 기점으로 하는 또 다른 LIS가 나올 수 있기 때문이다.

무슨 말이냐 하면, i=3에서 LIS가 {1, 7, 10}이었는데
i=4에서 3 이상의 수가 처음으로 나오는 지점인 5에 3을 넣은 이유는
나중에 {1, 3}으로 시작하는 LIS가 나올 수 있고
그게 최적의 결과일 수 있기 때문에 이를 준비한다는 것이다.
어차피 중간에 끼워넣는 것으로, LIS의 길이의 최대값은 변하지 않는데다
현재 중요한 건 길이지, 안의 내용이 중요한 게 아니기 때문에 이 방법이 가능하다.

이렇게 3을 넣고 i=4에서 5를 넣으니,
i=6에서 9를 넣어서 최종적으로 {1, 3, 5, 9}라는 길이 4짜리 LIS가 나올 수 있는 것이다.
지금은 이 LIS가 실제 LIS와 같지만 (눈으로만 봐도 {1, 3, 5, 9}가 LIS임을 알 수 있다.)
알고리즘의 특성 상 다를 수도 있다는 점을 알아야 한다.

만약 중간에 값을 교체하지 않았다면
그대로 {1, 7, 10}이 LIS인 줄 알았을 것이다.

시간복잡도

이 방법은 배열의 수를 하나하나 추가해가므로
배열을 다 보는데 $O(N)$ ,
추가할 위치를 찾는데 $O(logN)$ 이 걸리므로,
시간복잡도는 $O(NlogN)$ 이 된다.

실제 LIS 찾기

실제 LIS를 못 찾는 것은 아니다.
수가 추가된 LIS의 인덱스를 적어넣으면 LIS를 찾을 수 있다.
위의 예제에선 {1, 1, 2, 3, 2, 3, 4}가 될 것이다.
여기서 최대값인 4의 위치부터 역순으로 가장 가까운 3, 2, 1을 담으면
LIS가 된다.

솔직히 이게 대체 어떻게 머리에서 떠오를 수 있는지 이해가 되지 않는다.
다이나믹 프로그래밍을 이용하는 건 내가 어찌저찌 떠올릴 순 있겠으나...
정말 세상은 넓고 천재는 많다.