[DP, Binary Search] Longest Increasing Subsequence

무작위로 정렬되어 있는 정수를 원소로 가진 배열에 대해, 오름차순으로 정렬된 원소의 갯수를 구하라는 문제이다.

DP와 Binary Search를 써서 풀 수 있는 문제

 

DP의 경우는 간단하다. nums의 길이만큼 1로 채운 dp 배열을 만든다

이때 dp [ i ]는 nums의 i번째 원소의 longest Increasing Subsquence이다.

원소가 하나만 들어오면 longest Increasing Subsquence는 1개이므로 초깃값은 모두 1로 설정한다

nums의 원소를 하나씩 Loop하면서 i보다 작은 j를 모두 검사한다.

nums[ j ]가 nums[ i ]보다 작다면 오름차순으로 정렬이 되어 있다는 뜻이다.

i보다 작은 j번째 원소를 기준으로  longest Increasing Subsquence가 n개라면, i번째 원소를 기준으로는 n+1개가 된다.

 

여기서 주의할점은 최종적으로 dp[nums.length]이 아닌 dp중 max를 리턴한다는것이다.

실제로 dp를 콘솔로 찍어보면 오름차순 원소가 나오지 않는다

왜냐하면 dp[i]는 i원소를 반드시 포함시키는 조건이기 때문이다.

예를들어 i가 4인경우, 실제 longest Increasing Subsquence는 1-3-6-7-9가 되지만, dp[i]는 4를 포함해야하므로 1-3-4가 최댓값일것이기 때문이다. 따라서 이 경우는 3이 된다.

dp[i]는 nums[i]를 반드시 포함한다고 생각해야 한다

 

하지만 위의 방식으로 풀이하면 모든 nums[i]에 대해 일일이 Loop를 돌려야한다는 문제가 있다

따라서 binary search를 이용해 루프를 줄일것이다

 

이 binary search는 일반적인 이진탐색과 달리 target을 middle에서 찾지 않고 조건에 따라 start를 리턴한다

array는 항상 오름차순으로 정렬되어 있다.

n이라는 타겟이 들어오는 경우 그 타겟의 위치를 찾아서, 가장 큰 값보다 크다면 array의 길이+1의 위치를, 그것이 아니라면 n이 들어갈 위치를 리턴한다.

if로직이 target이 원소보다 작을때만 일반적인 이진트리 처리가 진행되고, 크다면 +1을 해서 리턴하기 때문이다

이렇게 하면 n이 c보다 큰 경우에만 length가 늘어나게 된다.

 

사실 이러한 문제는 LIS라는 하나의 케이스로 알고 있어야 한다.

기준 배열을(예시의 경우 memo) 하나두고, Binary Search는 memo의 마지막 element보다 작다면 해당 위치를 업데이트하고, 크다면 push한다.

즉 마지막 element보다 큰 element가 들어올때만 답이 1씩 추가되는 것이다.

 

이때 [1,1,1,1,1,1]처럼 같은 숫자가 들어오는 경우 정답은 1이지만, elem을 그대로 찾으면 1의 갯수만큼이 답으로 나온다

조건이 target이 middle보다 작은경우와 아닌 경우로만 나눠져 있으므로, elem에서 1을 빼더라도 middle보다 작은 경우에 속하지 않는다.

 

결과 length를 리턴하면 답이 된다.