[BOJ] 가장 긴 증가하는 부분수열 시리즈

Jihan·2024년 12월 1일
DP경로복원백준알고리즘 문제이진탐색
1

알고리즘

목록 보기
6/6
post-thumbnail

가장 긴 증가하는 부분 수열(LIS) 시리즈를 풀어보자.

가장 긴 증가하는 부분 수열
가장 긴 증가하는 부분 수열 2
가장 긴 증가하는 부분 수열 3
가장 긴 증가하는 부분 수열 4
가장 긴 증가하는 부분 수열 5

시리즈물은 항상 재밌습니다. 저는 시리즈물을 볼 때면 항상 첫 편부터 보는 걸 선호하는데요. 이전에 신비한 동물사전이 개봉했을 때 해리포터 시리즈랑 같은 세계관인 걸 알고, 해리포터 시리즈를 정주행하고 신비한 동물사전을 봤던 기억이 나네요. 여러 이어지는 이야기 중 한 순간도 그 나름의 재미가 있지만, overview를 보는 건 또 다른 새로운 재미를 주는 것 같아요. 갑자기 무슨 얘기냐고요? 오늘은 유명한 유형의 알고리즘 문제 시리즈를 풀이해보려고 해요.

바로 가장 긴 증가하는 부분 수열(Longest Incresing Subsequence, LIS) 시리즈입니다.

백준에는 여러 LIS 문제가 있어요. 이 이후에도 몇 문제 더 있지만, 일단 오늘의 목표는 LIS 5까지 풀이하기입니다. 목표로 하고 있는 LIS 5까지 문제 유형이 어떤지 살펴봅시다. 백준에는 문제, 입력, 출력으로 문제 페이지가 나뉘어지는데, LIS 시리즈는 문제 부분이 모두 동일합니다. LIS에 대한 정의를 알려주는 부분이에요.

그리고 입력과 출력은 조금씩 다릅니다. 입력의 형식은 같은데, 값의 범위가 다르고, 출력의 형식은 LIS의 길이를 출력하거나, LIS를 직접 출력하도록 합니다. 아래는 백준의 문제들을 정리한 내용이에요.

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 AA의 크기 NN이 주어진다.
둘째 줄에는 수열 AA를 이루고 있는 AiAi가 주어진다.

출력

  1. LIS의 길이
    첫째 줄에 수열 AA의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

  2. LIS
    둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

문제별 입/출력

분류LIS 1LIS 2LIS 3LIS 4LIS 5
입력(1≤N≤103)(1 ≤ N ≤ 10^3), (1≤Ai≤103)(1 ≤ Ai ≤ 10^3)(1≤N≤106)(1 ≤ N ≤ 10^6), (1≤Ai≤106)(1 ≤ Ai ≤ 10^6)(1≤N≤106)(1 ≤ N ≤ 10^6), (−109≤Ai≤109)(-10^9 ≤ Ai ≤ 10^9)(1≤N≤103)(1 ≤ N ≤ 10^3), (1≤Ai≤103)(1 ≤ Ai ≤ 10^3)(1≤N≤106)(1 ≤ N ≤ 10^6), (−109≤Ai≤109)(-10^9 ≤ Ai ≤ 10^9)
출력LIS의 길이LIS의 길이LIS의 길이LIS의 길이, LISLIS의 길이, LIS

1번, 4번과 3번, 5번은 입력 범위가 동일하고,
1번, 2번, 3번은 순차적으로 입력의 범위가 늘어납니다.
1번은 짧은 길이의 수열이었다가, 2번은 더 긴 길이의 수열이 됩니다.
그리고 3번에서는 수열의 항들에 대해 음수 범위까지 확장됩니다.

그러니까, 3번을 풀면 사실상 1번과 2번은 모두 풀리고, 5번을 풀면 4번도 풀리는 겁니다. 음. 아주 좋네요. 한 번에 다섯 문제를 해결해봅시다.

풀이 과정

문제 유형은 크게 두 가지로 나뉩니다. LIS의 길이를 출력하거나, LIS의 길이와 LIS를 함께 출력하는 유형입니다. 일단은 우리 LIS를 찾아내는 것보다는 LIS의 길이만 구하는 데에 집중해봅시다.

1. 브루트포스(Brute Force)

처음에는 브루트포스를 통해 풀이를 해볼 겁니다.

문제의 조건은 가장 긴, 증가하는, 부분 수열로 크게 세 가지로 나눌 수 있습니다.

문제에서 입력으로 주어지는 수열의 항들만 사용한다면, 부분 수열임은 보장된 채로 연산할 수 있을 것입니다. 그럼 두 가지 방향의 풀이를 생각할 수 있는데요.

1-1. 가장 긴 부분 수열이 증가하는 지 검사한다.

  1. 가장 긴 부분 수열을 찾는다.
  2. 수열이 증가수열인지 검사한다.
    2-1. 증가수열일 경우 이 수열이 LIS가 된다.
    2-2. 증가수열이 아닐 경우 항을 차례대로 제거해가면서 2번으로 재귀한다.

1-1의 경우, 한 번의 시도 안에 LIS를 찾을 수도 있을 것입니다. 하지만 worst case의 경우 모든 부분 수열을 탐색하고 길이가 1인 수열이 LIS가 될 수도 있겠지요. 길이가 1 이상인 모든 부분 수열을 검사할 수 있으므로 부분수열을 모두 구하는 방식과 시간복잡도가 동일합니다. O(2N)O(2^N)입니다.

1-2. 증가하는 부분 수열 (IS) 중 가장 긴 수열을 찾는다.

  1. 주어진 수열에서 항을 한 개씩 선택해서, 현재 부분 수열에 추가한다.
  2. 만들어진 부분 수열이 증가하는 지 판별한다.
    2-1. 증가수열일 경우 현재까지 그 길이를 확인해, 지금까지 찾은 증가하는 부분 수열보다 길 경우 이를 유지한 채 1로 재귀한다.
    2-2. 증가수열이 아닐 경우, 그 항을 버리고 1로 재귀한다.
  3. 추가할 항이 더 이상 없을 경우, 현재까지 만든 부분수열이 LIS가 된다.

1-2는 일종의 DFS 형태로 동작합니다. 이 경우에도 첫 번째 싸이클(전체 수열의 모든 항들이 포함되는 한 싸이클)에서 LIS를 구할 수도 있지만, worst case의 경우 최대 길이 수열이 LIS가 될 수 있으므로 모든 부분 수열을 탐색하는 방식과 시간복잡도가 동일합니다. 마찬가지로 O(2N)O(2^N)입니다.

어쨋든 브루트포스로 구현된 알고리즘은 O(2N)O(2^N)보다 빨라지도록 할 수 없을 것 같습니다. 하지만 문제에서 주어진 수열의 길이 중 가장 작은 조건은 10310^3입니다. 이 정도의 시간복잡도로는 풀이가 불가능해보입니다. 음. 브루트포스가 아닌 다른 방법으로 가야겠지요.

2. DP: O(N²)

이 문제는 DP(Dynamic Programming) 풀이로 유명한 문제입니다. DP는 알고리즘 문제풀이에서 각 연산에서 휘발되는 연산결과를 메모이제이션(memoization)해서 다음 연산에 반영하도록 해 이미 시행된 연산을 생략할 수 있도록 하는 기법입니다. 일종의 시간복잡도와 공간복잡도를 트레이드 오프하는 전략이라고 볼 수 있습니다.

DP도 모든 문제에 적용할 수 있는 것은 아닙니다. DP를 적용하기 위한 조건은 크게 두 가지로 이해할 수 있습니다. 문제가 최적해를 갖는 부분 문제로 나뉘어질 수 있어야 한다는 최적 부분 구조이여야 한다는 것과, 그 부분 문제들이 대개 같은 관계식으로 표현될 수 있어야 한다는 중복되는 부분 문제 구조여야 한다는 점입니다.

간단하게 이야기하자면 재귀적으로 표현이 가능하면서, 점화식으로 표현이 가능해야 합니다.

앞서 살펴본 브루트포스 풀이 방식에서 시간복잡도를 낮춰야되었고, 메모이제이션을 통해 시간복잡도를 줄일 수 있는 형태이기 때문에 우리는 DP로 이 문제를 풀어볼 것인데요. 연산을 재활용한다는 컨셉을 최대한 활용해서 생각해본다면, 일종의 재귀 형태로 다음과 같이 작성해볼 수 있을 것 같습니다.

  1. 전체 항을 순회하면서(for i in range(N))
  2. 현재 항(i)보다 앞선 항들(for j in range(i)) 중
  3. 현재 항(i)보다 작은 항(j (A[j] < A[i]))들에 대해
  4. j항을 마지막 항으로 하는 IS의 길이를 구하고,
  5. 그 중에서 가장 큰 값에 1을 더해 i항을 마지막 항으로 하는 IS의 길이로 한다.
  6. 순회를 마친 뒤 i항을 마지막 항으로 하는 IS의 길이중 가장 긴 값이 LIS의 길이가 된다.

L[i] = i항까지에 대한 IS의 길이라고 해보겠습니다. 위의 과정에서 L[i]는 계속 i항까지에 대한 IS의 길이라는 조건을 만족하게 되는데, 그 이유는 다음과 같습니다.

  1. j는 항상 i보다 작다.
  2. A[j]가 A[i]보다 작다면, L[j] 수열의 맨 뒤에 A[i]가 추가되면 증가 부분 수열이다.
  3. A[i]보다 A[j]를 작게 만드는 j에 대해 L[j] 중 가장 큰 값에 1을 더하면 L[i]가 된다.

자, 이제 코드로 작성해봅시다. 반복문을 활용하면 어렵지 않게 아래와 같이 작성할 수 있습니다.

N = int(input())
A = list(map(int,input().split()))

L = [1 for _ in range(N)]
for i in range(N):
    a = A[i]
    for j in range(i):
        b = A[j]
        if b < a and L[i] <= L[j]:
            L[i] = L[j] + 1

print(max(L))

시간복잡도를 이야기해보자면 전체 항을 순회해야하므로 O(N)O(N), 각 항에 대해 모든 앞선 항에 대해 연산하므로 O(N)O(N), 앞선 항을 마지막 항으로 하는 IS의 길이를 구하는 연산을 메모이제이션을 통해 O(1)O(1)로 만들어 총 O(N2)O(N^2)의 시간복잡도를 갖게 됩니다.

자, 이제 1≤N≤1031 ≤ N ≤ 10^3인 1번, 4번 문제에 대해서는 충분히 통과가 가능한 형태가 되었습니다. 그런데, 다른 문제들은 1≤N≤1061 ≤ N ≤ 10^6의 범위를 갖습니다. NN이 가장 큰 엣지케이스에서는, O(N2)O(N^2)의 경우 총 101210^{12}회의 연산이 필요하므로, 1~2초로는 시간이 부족하게 됩니다. 시간복잡도를 더 줄여야 합니다.

3. DP: O(NlogN)

앞서 O(N2)O(N^2)의 시간복잡도를 가지는 DP 풀이는 다음과 같이 두 지점에서 시간복잡도가 발생합니다.

  1. 전체 항을 순회하는 데에 O(N)O(N): for i in range(N)
  2. 현재 항(i)보다 앞선 항(j)에 대해 순회하는 데에 O(N)O(N): for j in range(N)

만약 기존의 방식을 유지하면서 시간복잡도를 줄이고 싶다고 하면, 위의 두 부분에서 줄일 수 밖에 없을 것입니다. 그런데, 전체 항을 순회한다는 특징은 증가하는 수열을 찾아야 한다는 부분에서 빼놓을 수 없습니다.

2의 시간을 줄여 보아야겠습니다.
현재 항(i)보다 앞선 항(j)에 대해 순회하는 이유는 A[i]보다 작으면서 A[j]들을 마지막 항으로 하는 IS 중 가장 긴 수열을 구하기 위함입니다. 어쨋든 뒤에 A[i]를 붙혀서 새로운 수열을 만들어야 하기 때문에, 그 대상이 되는 수열을 탐색하긴 해야 합니다. 그럼 현재 하고 있는 선형 탐색의 형태보다 시간복잡도를 줄이기 위해서는, 자연스럽게 이진탐색이 떠오르게 됩니다.

하지만 이진탐색을 적용하기 위해서는, 정렬된 형태로 원하는 값을 탐색하도록 자료구조를 개편할 필요가 있습니다. 그리고 우리의 전체 수열은 증가하는 부분 수열을 구해야하기 때문에 정렬할 수는 없습니다. 어떤 식으로 이진탐색을 통해 A[i]를 붙힐 증가 부분 수열을 찾을 수 있을까요?

만약 새로운 D[i]라는 Array에 L[i]를 길이로 하는 IS들의 마지막 항을 기억해놓는다면, D[i]가 가리키는 수열의 뒤에 D[i]보다 큰 값을 붙혔을 때 항상 새로운 IS가 생긴다고 보장할 수 있게 됩니다.

그리고 A[i]보다 작으면서 A[j]들을 마지막 항으로 하는 IS 중 가장 긴 수열은 여러 개가 될 수 있습니다. A[i]를 뒤에 붙힐 때는, 마지막 항이 A[i]보다 작기만 하면 되기 때문에 그 값이 몇인지는 상관 없습니다. 따라서 D[i]에 저장되는 값은 길이가 i인 IS의 마지막 항 중 가장 작은 값이 될 것입니다.

D[i]에 새로운 값이 추가되거나 값이 갱신될 때는, 그 위치가 항상 A[i]보다 작으면서 가장 큰 D[i]값의 뒤입니다. D[i]가 오름차순임이 보장된다는 의미입니다. 이제 선형 탐색을 이진 탐색으로 대체하여 시간복잡도를 낮출 수 있게 되었습니다.

한 번 정리해보겠습니다.

  1. 전체 항을 순회하면서(for i in range(N))
  2. 이진탐색으로 D에서 A[i]보다 작은 값 중 가장 큰 값을 찾는다. 이를 D[j]라 한다.
    • D[i]는 길이가 i인 IS의 마지막 항 중 가장 작은 값.
  3. D[j + 1]은 기존의 값과 A[i]중 더 작은 값이 된다.
    • D[i]가 나타내는 IS의 뒤에 A[i]를 붙혔다고 생각할 수 있다.
  4. 순회를 마치면 len(D)가 LIS의 길이가 된다.
N = int(input())
A = list(map(int,input().split()))

D = [0]
# 1. 전체 항을 순회하면서
for i in range(N):

# 2. `D`에서 `A[i]`보다 작은 값 중 가장 큰 값을 찾는다. 이를 `D[j]`라 한다.
    a = A[i]
    start, end = 0, len(D) - 1
    while start <= end:
        mid = (start + end) // 2
        if a == D[mid]:
            break
        elif a < D[mid]:
            end = mid - 1
        else:
            start = mid + 1
    
# 3. `D[j + 1]`은 기존의 값과 `A[i]`중 더 작은 값이 된다.
    if D[mid] < a:
        if mid < len(D) - 1:
            D[mid + 1] = a
        else:
            D.append(a)
    else:
        D[mid] = a

# 4. 순회를 마치면 `len(D)`가 가장 긴 LIS의 길이가 된다.
print(len(D) - 1)

이제 전체 항을 순회하는데 O(N)O(N), 현재 항을 뒤에 붙힐 IS를 탐색하는데 O(logN)O(logN)의 시간이 걸립니다. 따라서 해당 코드는 O(NlogN)O(NlogN)의 시간복잡도를 가지며, 입력이 10610^6의 범위를 가져도 충분히 시간 내에 해결할 수 있게 되었습니다.

추가 조건: 음수 항에 대한 처리

1, 2, 4번 문제는 0보다 큰 항들만 입력으로 주어집니다. 반면 3, 5번 문제는 음수 항들도 입력으로 주어지는데요. 만약 위의 코드를 3번 문제에 바로 사용해보면, 틀렸습니다가 바로 출력됩니다. 음수 입력에 대한 처리가 필요합니다.

음수 항에 대한 처리가 이루어지지 않는 이유는 D에 새로운 항이 추가될 때 적절한 위치에 추가되지 않기 때문입니다. D를 초기화할 때 0으로 이진탐색의 최소값을 잡아주었기 때문에, 음수 입력이 들어올 경우 기준으로 잡아주었던 D[0]의 0값이 그 음수값으로 갱신되면서 길이가 하나 부족하게 됩니다.

그래서 처리는 간단합니다. D를 초기화할 때 잡아주는 padding값을 0이 아니라, -inf 혹은 −109-10^9보다 작은 값으로 설정해주면 됩니다.

N = int(input())
A = list(map(int,input().split()))

# D의 기본 초기화를 입력 범위보다 작은 값으로 한다.
D = [-1000000001]
for i in range(N):

    a = A[i]
    start, end = 0, len(D) - 1
    while start <= end:
        mid = (start + end) // 2
        if a == D[mid]:
            break
        elif a < D[mid]:
            end = mid - 1
        else:
            start = mid + 1
    
    if D[mid] < a:
        if mid < len(D) - 1:
            D[mid + 1] = a
        else:
            D.append(a)
    else:
        D[mid] = a

print(len(D) - 1)

음수 항 입력이 하나라도 있을 경우 마지막 print에서 1을 빼주지 않는 방법도 가능할 것 같습니다.

추가 조건: LIS 복원

4, 5번 문제의 추가 출력 조건인 LIS 복원입니다.
4, 5번 문제의 경우 기존 1, 2, 3번 문제와 달리 LIS의 길이만을 출력하는 것이 아니라, 그 길이를 갖는 LIS도 함께 출력해주어야 합니다.

LIS의 길이를 구할 수 있는 D 수열을 그대로 출력하면, 답이 아니게 됩니다. 우리는 i의 길이를 갖는 IS 중에서 가장 작은 마지막 항을 D[i]에 저장해두었을 뿐이지, D 수열이 그대로 LIS가 되도록 저장하지 않았기 때문입니다.

O(NlogN)O(NlogN)의 DP 풀이를 다시 한 번 봅시다.

  1. 전체 항을 순회하면서(for i in range(N))
  2. 이진탐색으로 D에서 A[i]보다 작은 값 중 가장 큰 값을 찾는다. 이를 D[j]라 한다.
    • D[i]는 길이가 i인 IS의 마지막 항 중 가장 작은 값.
  3. D[j + 1]은 기존의 값과 A[i]중 더 작은 값이 된다.
    • D[i]가 나타내는 IS의 뒤에 A[i]를 붙혔다고 생각할 수 있다.
  4. 순회를 마치면 len(D)가 LIS의 길이가 된다.

3에서 A[i]가 지금까지 있었던 어느 IS의 뒤에 붙어야 했는지를 저장해놓는다면, D의 값이 새로운 최소값을 갱신되어도 A[i]가 뒤에 붙을 때 D[i]가 어떤 값이었는지 추적할 수 있을 것입니다. 이를 위해 prev라는 list를 선언해주고, A[i]를 통해 D가 갱신될 때, prev[i]에 D[j]의 A에서의 위치를 저장해줍시다. 이는 LIS에서 i의 이전 항이 A에서 어디에 위치하는지를 의미합니다.

그리고 D[j]의 A에서의 위치는 D[j]의 값만으로는 추적할 수 없기에, D[i] = 길이가 i인 IS의 마지막 항 중 가장 작은 값에서 D[i] = (길이가 i인 IS의 마지막 항 중 가장 작은 값, 그 값의 A에서의 위치(인덱스))로 수정해줍니다.

마지막으로 순회가 끝난 뒤 D의 마지막 항은 LIS의 마지막항이므로, D[-1][0]을 통해 prev를 쭉 순회하면, LIS를 복원할 수 있게 됩니다.

수정된 코드는 아래와 같습니다.

N = int(input())
A = list(map(int,input().split()))

# LIS 복원을 위한 prev 배열을 선언해줍니다. 초기값은 A의 인덱스 범위를 벗어난 값으로 설정해줍니다.
prev = [-1 for _ in range(N)]

# D list를 tuple list형태로 수정합니다.
D = [(-1000000001, -1)]
for i in range(N):
    a = A[i]
    start, end = 0, len(D) - 1
    while start <= end:
        mid = (start + end) // 2
        if a == D[mid][0]:
            break
        elif a < D[mid][0]:
            end = mid - 1
        else:
            start = mid + 1
    
    if D[mid][0] < a:
        if mid < len(D) - 1:
            D[mid + 1] = (a, i)
        else:
            D.append((a, i))
        # D가 갱신될 때마다 prev에 값을 저장해줍니다.
        prev[i] = D[mid][1]
    else:
        D[mid] = (a, i)
        # D가 갱신될 때마다 prev에 값을 저장해줍니다.
        prev[i] = D[mid - 1][1]

# D의 마지막 항은 LIS의 마지막 항이기 때문에, 이를 활용하여 LIS를 복원해줍니다.
LIS = []
i = D[-1][1]
while i > -1:
    LIS.append(A[i])
    i = prev[i]

print(len(D) - 1)
print(*LIS[::-1])

이제 4, 5번 문제의 조건인 LIS 출력까지 해내는 코드가 되었습니다.

마치며

오늘은 LIS 시리즈를 함께 풀어보았습니다. 시각자료가 딱히 없어서 문장만으로는 이해가 어려울 수 있을 것 같습니다. 그럼에도 굳이 시각자료를 작성하는 데에는 큰 공을 들일 필요가 없어 보입니다. 이 글은 각 풀이가 가지고 있는 논리적 흐름 자체도 중요하지만, 같은 문제에서 점점 어려워지는 조건에 따라 추가적인 요구사항이 생기고, 그 요구사항을 만족하기 위해 알고리즘을 튜닝해나가는 과정이 핵심이기 때문입니다.

  1. 브루트포스
  2. 시간복잡도를 줄이기 위한 DP 도입
  3. 시간복잡도를 줄이기 위한 이진탐색 도입
  4. 음수 입력 처리
  5. 길이만 출력하는 기존 문제에서 수열 자체를 출력하도록 복원 기능 추가

제가 이 시리즈로 글을 쓴 이유는 이런 이유입니다.

만약 LIS 5번 문제를 처음부터 풀려고 했었어도, 위와 같은 흐름으로 문제 풀이를 해내갈 수 있었을까요?

5번 문제를 처음으로 풀었어도 위의 흐름대로 풀이를 구현하려고 했다면 정말 좋은 흐름이지만, 그런 직관을 가지기 위해서는 이렇게 진화되는 요구사항을 통해 어떤 식으로 대응해야하는지 훈련하는 것이 좋은 방법이라고 생각됩니다. 일종의 점진적 과부화...라고 할 수 있을까요?

그런 의미에서 알고리즘 공부에서 좋은 문제는 지엽적인 배경 지식이나 과도한 직관을 통해 풀이되는 것이 아닌, 분명한 논리적 흐름으로 풀이가 특정될 수 있는 문제라고 생각합니다.

아무튼 도움이 되셨길 바라며, 긴 글 읽어주셔서 감사합니다!

글의 내용뿐 아니라, 가독성 등에 대한 피드백 또한 언제나 감사드립니다.

profile
Jihan
DIVIDE AND CONQUER
이전 포스트

[BOJ] 백준 1647 도시 분할 계획

다음 포스트

위상 정렬 알고리즘 (BOJ 2252, 1005, 23754)

0개의 댓글

관련 채용 정보