[Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP)

오늘은 최장 증가 부분 수열 (LIS)에 대해 정리해보려한다.

LIS를 구하는 방법은 여러가지지만, 그 중에서도 가장 간편한 DP를 이용한 방법을 소개한다.

(DP에 대해 궁금하신 분들은 요기👇를 참고해주세요!)

2021.08.28 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 동적 계획법 (feat. Fibonacci)

[Swift Algorithm Note] 동적 계획법 (feat. Fibonacci)

 

📎  최장 증가 부분 수열 (LIS)

최장 증가 부분 수열은 말 그대로, 어떠한 수열 안에서 가장 긴! 증가하는 수열을 찾는 것이다.

하지만 짚고 넘어가야할 점은 증가하는 수들이 연속하지 않아도 된다는 점이다.💥

 

예를 들어 [1, 3, 2, 4, 6, 5] 수열에서의 LIS는 [1, 2, 4, 6]으로, 길이가 4인 수열이다.

위와같이 LIS는 연속하거나, 혹은 연속하지 않는 증가하는 수들의 수열을 말한다.

 

이 LIS를 구하기 위해서는 배열의 요소 별로 나보다 작은, 증가하는 수열이 몇 개 있는지 찾아주어야하는데

완전탐색으로도 구할 수 있지만, 시간복잡도가 너무 커지게된다.ㅜ

따라서 그 첫 번째 해결책이 바로 DP를 이용하는 것이다.

(두 번째로는 이분탐색을 이용하는 방법이 있지만, 그건 다음에 다루도록 하겠다.)

---

📎  DP로 LIS 구하기

랜덤으로 나열된 한 수열에서 LIS를 구하는 알고리즘을 작성해보았다.

아래의 예제가 DP로 LIS를 구하는 대표적인 형태이다.

 

📌 예제

import Foundation

let permu = [1, 3, 2, 5, 4, 6]
var count = [Int]()
var max = 1

for i in 0..<permu.count {
    count.append(1)
    
    for j in 0..<count.count {
        if permu[j] < permu[i] && count[i] <= count[j] { count[i] = count[j]+1 }
    }
    
    if max < count[i] { max = count[i] }
}

print(max)

변수 설명

• permu : 입력 수열
• count : 입력 수열의 요소마다 해당 요소까지의 최장 수열을 저장하기 위한 배열
• max : count 배열에 저장되는 최장 수열의 길이 중 가장 긴 길이값을 저장하기 위한 변수

코드 설명

• permu 배열의 첫 번째부터 마지막 요소까지 순서대로 검사해주기 위한 2중 for문을 사용
• 매 반복마다 먼저 count 배열에 1을 추가해주었다. 
  자기 자신 외에 증가하는 수가 없을지라도(ex. 1, 2, 7, 3), 최소한 자기 자신을 담은
  길이 1의 수열은 될 수 있기 때문에 기본으로 1을 추가해준다.
• 1을 추가한 count 배열의 길이만큼 하위 반복문을 실행해주는데,
  우선 permu 배열에서 j위치의 수가 i위치 요소보다 작은지 확인한다.
• 작다면 count에 저장해둔 j 번째 요소와 i 번째 요소를 비교하는데,
  i 번째 요소, 그러니까 count에 추가한 마지막 요소인 1이 count[j]보다 작거나 같다면
  i 번째 요소는 j 번째 요소가 가지는 최장 증가 수열 개수에 1을 더한 만큼
  최장 증가수열을 가진다는 뜻으로 해석할 수 있다.
• 위 시행을 반복해주면 최장 증가 수열을 갖는 요소와 그 길이를 확인할 수 있다.

---

👀 정리

DP를 이용하여 LIS를 구하는 알고리즘을 이해하고, 사용 방법을 공부했다.

 

공부하고 나니 쉬운 개념인듯하지만,

몰랐을 때는 정말 몇날 며칠 고민해도 떠오르질 않았다.ㅜ

관련 문제들을 많이 풀며 익혀야겠다.

 

💥 추가로, DP로 LIS를 구하는 방법을 공부하고 싶은 여러분께,, 이 문제를,,

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

1965번: 상자넣기