👻 다이나믹 프로그래밍 - 최대 부분 증가 수열(LIS)

⚽ 최대 부분 증가수열

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최대 부분 증가수열(최장 증가 부분 수열)이라고 한다.

• 일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 방법은 DP를 이용하는 것이다.

이 문제의 유형은 DP 문제로 자주 나오는 유형이며, O(N^2) 시간 복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다.

• 당연히 어려운 문제는 NlogN을 요구...

문제와 함께 이해해보자.

최대 부분 증가수열

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

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

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

▣ 입력예제 1
8
5 3 7 8 6 2 9 4

▣ 출력예제 1
4

import sys
# sys.stdin = open("input.text", "rt")

n = int(input())
data = list(map(int, input().split()))
data.insert(0,0) #1번 인덱스부터 확인하기 위해서 앞에 삽입
dp = [0] * (n+1)
dp[1] = 1 #객관적으로 자명한건 미리 쓰자

res = 0
for i in range(2,n+1):
    max_length = 0
    for j in range(1,i): #i보다 앞에까지 돌면서 최장 부분 증가수열 최댓값을 찾는다.
        if data[j] < data[i] and dp[j] > max_length: #data[i]의 값, 즉 i번째 숫자가 내가 만들고자 하는 증가수열의 마지막 항을 의미해
            max_length = dp[j] #dp[j]는 data[j], 즉j번째 항이 마지막 항인 증가수열의 최대 길이
    dp[i] = max_length + 1
    if dp[i] > res:
        res = dp[i]

print(res)

👻 코멘트

해당 문제를 보면 n개의 자연수로 이루어진 수열에서 가장 길게 증가하는 (작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하면 된다.

문제의 생각의 시작은 "기준"이 있어야 한다. 일단 조건에서 이동 안되는거 설명했음.

⚽ 처음에 바텀업 방식으로 (일단 dp문제라는 건 파악했다는 전제) 간단한 문제로 최소화 시킨 후에 점점 확장하는 방식으로 풀어야 하니깐 배열에서 가장 왼쪽에서부터 해당 숫자까지 만들 수 있는 수열 중에 증가하는 수열을 찾는 것이다.

⚽ 예를 들어 주어진 예제처럼 5 3 7 8 6 2 9 4 의 수열이 주어지면...

• 먼저 첫번째 숫자인 5가 내가 만들고자 하는 증가수열의 마지막 항이라고 생각해보자. 가장 길게 증가하는 수열을 만들면 [5] 하나이다.
• 두번째 숫자인 3이 내가 만들고자 하는 증가수열의 마지막 항이라고 생각해보자. 앞에 숫자 5는 3보다 크니깐 안돼. 그러니 두번째까지도 [3]만 가능.
• 7이 내가 만들고자 하는 증가수열의 마지막 항이라면, 이전 항 3이 될 수 있으니 3을 마지막으로 해서 만드는 증가수열이 몇개가 있었는지 확인하면 된다 !
  • 그 다음 앞으로 전진해서 5 역시 내가 만들고자 하는 증가수열 앞에 올 수 있다. 그렇기에 5를 마지막으로 하는 증가수열에 더할 수 있다. 그렇기에 [5,7], [3,7]이 존재한다.

• 다음 항인 8이 내가 만들고자 하는 증가수열의 마지막 항이라고 보면, 앞으로 가면서 7,3,5 모두 앞에 올 수 있다 ! 그렇기에 7을 마지막 항으로 하는 증가수열에 붙이거나, 3을 마지막 항으로 하는 증가수열에 붙이거나, 5를 마지막 항으로 하는 증가수열에 붙일 수 있다.

⚽ 이런 식으로 점점 작은 문제를 확장하는 방식으로 풀어나가는 문제 !! 최대 부분 증가 수열 문제이다 ! (역시 dp문제의 한 종류)

dp 테이블에 각 인덱스에 있는 값은 해당 숫자를 마지막 항으로 하는 증가수열 중 가장 긴 길이를 저장하면 됐다.

이런 식으로 전체 수열을 쭉 진행하면 된다 !!

• 그리고 저장된 리스트에서 가장 큰 값이 가장 긴 증가수열의 길이를 가지고 있는 숫자야!

for i in range(2,n+1):
    max_length = 0
    for j in range(1,i):
        if data[j] < data[i] and dp[j] > max_length: #data[i]의 값, 즉 i번째 숫자가 내가 만들고자 하는 증가수열의 마지막 항을 의미해
            max_length = dp[j] #dp[j]는 data[j], 즉j번째 항이 마지막 항인 증가수열의 최대 길이
    dp[i] = max_length + 1
    if dp[i] > res:
        res = dp[i]

⚽ 아까 말했던 대로 i번째 앞에까지 증가수열의 최대길이 + 1이므로 i-1까지 돌면서 dp의 최대값을 찾아. dp[j]는 j번째 항이 마지막 항인 증가수열의 최대길이. 그렇게 해서 찾은 값에 + 1을 해주면 i번째가 마지막 항인 증가수열의 최대 길이가 저장 돼.

• 그리고 최종 결과는 저장된 dp 리스트의 최댓값이야! 그게 만들 수 있는 가장 긴 증가수열의 길이이기 때문.

O(N^2)의 시간 복잡도

위에서 풀어본 알고리즘이 바로 O(N^2)의 시간 복잡도를 갖는 알고리즘이였다.
O(N^2)의 시간복잡도를 갖는 알고리즘은 꽤나 간단했다.

---

O(NlogN)의 시간 복잡도 - 이분 탐색 이용

위의 알고리즘은 배열의 원소를 하나씩 탐색하면서, 그 이전의 원소들을 모두 탐색하기 때문에 O(N^2)의 시간 복잡도를 갖는다. 따라서 n이 10000보다 커지면 시간이 매우 오래 걸릴 것이다...

x = int(input())
arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

max_dp = max(dp)
print(max_dp)

max_idx = dp.index(max_dp)
lis = []

while max_idx >= 0:
    if dp[max_idx] == max_dp:
        lis.append(arr[max_idx])
        max_dp -= 1
    max_idx -= 1

lis.reverse()
print(*lis)

• max_dp는 가장 긴 증가수열의 길이
• max_idx는 max_dp의 위치
• lis는 가장 긴 증가수열을 담을 배열

⚽ max_idx의 값부터 시작하여 거꾸로 순회하며 arr의 원소를 추가하면 된다.
max_dp가 4고, max_idx는 5이므로 arr[5] = 10에서부터 거꾸로 순회하면 된다. 그다음으로 올 원소는 arr[4] = 5, arr[3] = 2, arr[0] = 1이 된다.
lis = [10, 5, 2, 1]이며 이걸 뒤집어서 출력하면 원하는 정답을 얻을 수 있다.

이렇게 LIS 푸는 방법에 대해서 작성해보았다. 여기서 풀이한 문제들 말고도 관련한 문항들이 더 있으니 해당 문제들도 도전해보면 좋을 것 같다.

👻 LIS 활용한 문제

💨 최장 증가 부분 수열을 활용한 문제들을 풀어보면서 어떤 유형일 때 해당 알고리즘(dp)를 써야할지 생각해보자.

최대 선 연결하기

왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다.오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇개의 선을 연결할 수 있는 지 구하는 프로그램을 작성하세요.

위의 그림은 오른쪽 번호 정보가 4 1 2 3 9 7 5 6 10 8 로 입력되었을 때 선이 서로겹치지 않고 연결할 수 있는 최대 선을 개수 6을 구한 경우입니다.

▣ 입력설명
첫 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 1부터 N까지의 자연수 N개의 오른쪽 번호 정보가 주어집니다. 순서는 위쪽번호 부터 아래쪽번호 순으로입니다.
▣ 출력설명
첫 줄에 겹치지 않고 그을 수 있는 최대선의 개수를 출력합니다.

▣ 입력예제 1
10
4 1 2 3 9 7 5 6 10 8

▣ 출력예제 1
6

import sys
sys.stdin = open("input.text", "rt")

#최대 선 연결하기
n = int(input())
data = list(map(int, input().split()))
dp = [0] * n
dp[0] = 1
res = 0
for i in range(1,n):
    max_length = 0
    for j in range(i):
        if data[j] < data[i] and dp[j] > max_length:
            max_length = dp[j]
    dp[i] = max_length + 1 #이전까지의 최장거리 + 1
res = max(dp)
print(res)

해당 문제 코멘트

왼쪽 숫자는 오름차순으로 나열되어 있고, 오른쪽은 정렬되어 있지는 않음..

• 선이 교차되지 않도록 최대선의 개수를 구하는 문제

이 문제를 해결하기 위한 생각으로는 오른쪽에서 선택을 할 것인데 결국 왼쪽은 오름차순으로 정렬되어 있으니 오른쪽도 최대한으로 오름차순으로 되어 있으면 교차하지 않는 최대 선의 개수를 알 수 있게 된다 !

👻 결론은 최장 부분 증가수열의 길이를 구하는 문제였던 것이다.

• 이전 코드와 똑같이 짜면 됐지만, 문제를 어떻게 풀 지를 생각했어야 했다.

가장 높은 탑 쌓기

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.
(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
(조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

▣ 입력설명
입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터연속적인 번호를 가진다.

▣ 출력설명
첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

▣ 입력예제 1
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

▣ 출력예제 1
10

import sys
# sys.stdin = open("input.text", "rt")

#가장 높은 탑 쌓기
#밑면 넓이, 벽돌 무게가 조건
#위로 갈수록 넓이 좁고 무게 가벼워야 한다

n = int(input())
data = []
for _ in range(n):
    a,b,c = map(int, input().split()) #밑면 넓이, 벽돌 높이, 무게
    data.append((a,b,c))

data.sort() #밑면 넓이로 오름차순 -> 조건 하나 제외
#이제 벽돌 무게만 뒤로 갈수록 증가. 즉 최장 부분 증가수열!
dp = [0] * n #각 인덱스 값까지의 최대 세울 수 있는 개수 
dp[0] = data[0][1]

for i in range(1,n):
    h = 0
    for j in range(i):
        if data[j][2] < data[i][2] and dp[j] > h:
            h = dp[j] #이전까지의 최장높이를 저장해놓음
    dp[i] = h + data[i][1]

print(max(dp))

해당문제 코멘트

조건이 두가지였다. 벽돌의 밑면 넓이, 벽돌의 무게.
먼저 둘 중 하나의 조건을 오름차순으로 정렬해야만 했다. 조건이 두개라 하나는 고정을 시켜주고 나머지 하나를 대조하면서 풀었어야 했어

• 그리고 벽돌의 무게를 보면 위로 갈수록 가벼워야 하므로 이제 선택하는 건데 현재 위치의 벽돌이 가장 가벼운 무게라고 생각하고 최장 부분 증가수열로 접근했으면 쉽게 해결했다.