[TIL코테]LIS알고리즘에 대하여

2022-07-13

🚩LIS알고리즘

LIS 알고리즘은 사실 뭐 이름은 들으면 엄청 거창한 것처럼 보이는 것 같지만 사실은

가장 긴 증가하는 부분 수열의 길이!

라고 보면 된다.
이게 무슨 말인가 하면 최대한 어떤 요소를 빼서 최대한 증가하게 만드는 형태의 부분수열을 만든다 생각하면 된다

예를 들어

출처:https://techblog-history-younghunjo1.tistory.com/295

해당 그림에서 보면 10 20 30 50 으로 될 때 가장 길게 증가하는 형태의 부분수열이라 답이 4인 것을 알 수 있다.

따라서 dp테이블의 초기화는
1로 자기 자신까지의 길이를 의미하게 초기화한다

핵심 점화식은 이와 같다

복잡해보이지만 별게 아니다.증가하는 형태이므로 이전 인덱스인 j보다 크고 그 값도 j에 해당하는 값보다 크면 i번째와 j번째의 값 중 더 큰값에 대하여 업데이트를 해주면 된다
길이니까 +1를 해준다

🔑코드구현

	dp=[1]*n
    
    for i in range(1,n):
    	for j in range(0,i):
        	if array[j]<array[i]:
				dp[i]=max(dp[i],dp[j]+1)
    
    #즉 특정 인덱스 이전에 모든 원소들을 다 비교해보되
    # i에 해당하는 값보다 작다면 그 때마다 계속 길이를 늘려 와준다
    result=max(dp)
    

비슷한 응용 문제

🔑병사배치하기 문제

<아이디어>
감소하는 형태의 수열이 제공 된다 따라서.list를 reverse시켜서 진행하며 쭉 감소하는 형태의 리스트를 만들어야 할 때 병사의 수를 최소한으로 뺄려면 그만큼 쭉 감소하는 형태의 부분수열의 길이가 최댓값이 되게 하고
전체에서 해당 길이를 빼주면 된다

문제: https://www.acmicpc.net/problem/18353