[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift)

문제

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

11053번: 가장 긴 증가하는 부분 수열

풀이

수열 A = {10, 20, 10, 30, 20, 50} 경우에 가장 긴 증가하는 부분 수열을 찾아봅시다.

첫번째 요소인 10만 봤을 때, 자기 자신도 수열이기 때문에 길이는 1입니다.

두번째 요소에서 이전 요소들을 확인해봅시다.
10 보다 20이 크기 때문에 (10의 길이 + 1)이 증가하는 부분 수열의 길이입니다.
따라서 길이가 2입니다.

세번째 요소에서 이전 요소들을 확인해봅시다.
전부 자신보다 작지 않네요. 넘어갑시다

네번째 요소에서 이전 요소들을 확인해봅시다.
첫번째 요소인 10이 자기 자신보다 작으므로 {10, 30} 으로 부분수열이 가능합니다.
길이를 2로 갱신해줍시다.
두번째 요소인 20도 자기 자신보다 작네요.
두번째 요소는 부분 수열의 길이가 {10, 20}으로 2이므로, {10, 20, 30} 으로 부분수열이 가능하네요.
길이를 3으로 갱신해줍시다.

$O(n^2)$의 시간 복잡도가 소요되겠지만 이러한 방식으로 풀이 할 수 있습니다.

1 ~ n개의 요소들을 확인하면서 자신보다 이전에 나타난 요소들중 작은 요소가 나타난다면,
그 요소의 부분 수열의 길이 + 1 을 자신의 부분수열의 길이로 갱신할 수 있습니다.

정의 : $f(n)$ = n번째 요소까지의 가장 긴 증가하는 부분 수열의 길이
초기값 : $f(1...n) = 1$
점화식 : $ j \lt i \ \ \ if \ \ \ array(j) \lt array(i)$
$f(n) = max(f(n), f(j) + 1)$

소스코드

후기

이러한 부분 수열을 구하는 문제는 다이나믹 프로그래밍으로 푸는 문제들이 많은 것 같습니다.
익숙해지자..!