Dynamic Programming with Longest Increasing Subsequence(LIS)

이전 Rosalind의 Longest Increasing Subsequence 문제를 1주일 이상 고민하다가 youtube 알고리즘 추천으로 Reducible의 영상을 보고 정리한 것

Dynamic Programming의 사고 절차는 아래 5가지로 요약이 됩니다.

1. Visualize Example
2. Find an appropriate subproblem
3. Find relationship among subproblems
4. Generalize the relationship
5. Implement by solving subproblems in order

이 Dynamic Programming 사고 방식을 LIS 문제를 푼다면 다음과 같습니다.

예를들어 다음과 같은 시퀀스가 있다고 합시다.

[ 8, 2, 1, 6, 5, 7, 4, 3, 9]

문제는 이 시퀀스에서 가장 긴 증가하는 하위시퀀스의 길이를 구하는 문제라고 했을 때, 다이나믹 사고방식을 적용해보면 다음과 같습니다.

Visualize Example.

조금 복잡하지만 위와 같은 그래프로 표현될 수 있습니다. 이 그래프를 통해 얻을 수 있는 것은 맨 뒤에서 index를 추적해 나가면 가장 긴 시퀀스를 구할 수 있을 것이라는 것입니다.

Find an Appropriate Subproblem

모든 increasing subsequence들은 전체 시퀀스의 부분집합이라는 것을 알 수 있고, 시퀀스에는 항상 시작과 끝이 있다는 것을 알 수 가 있습니다. 그러므로 LIS 함수로 하위문제를 정의할 수 있습니다.

$LIS[k] = LIS\space ending\space at \space index \space k$

LIS[k]를 위와 같이 정의 하였을 때, 위의 문제에서 LIS[3] = 2이 됩니다.

Find Relationship among Subproblems

하위문제를 정의했다면 하위문제간의 관계를 찾아야 합니다.

위의 수열에 따라 하위문제들을 정의해 보면

LIS[0] = 1

LIS[1] = 1

LIS[2] = 1

LIS[3] = 2

그러므로 LIS[4]는 자신보다 작은 문제들의 최대값 + 1이 됩니다.

$LIS[4] = 1 + max\{LIS[0], LIS[1], LIS[2], LIS[3]\}$

Generalize the Relationship

위의 식을 통해 규칙을 찾았다면, 이 규칙이 전체 시퀀스에 적용될 수 있도록 일반화를 시킵니다.

$LIS[n] = 1 + max\{LIS[k] | k < n, A[k] < A[n]\}$

Implement by Solving Subproblems in Order

def LIS(A):
	L = [1] * len(A)
	for i in range(1, len(L)):
		subproblems = [L[k] for k in range(i) if A[k] < A[i]]
		L[i] = 1 + max(subproblems, default=0)
	return max(L, default=0)

구현을 합니다.

---

Rosalind 문제를 풀때 이 방식을 이용하여 풀고, 정리하여올리겠습니다. De Brujin Graph도 정리해야 하고, 올릴건 많은데 시간은 없는 것 같습니다.ㅠㅠ