알고리즘 소개

해당 알고리즘은 어떠한 긴 리스트에 증가하는 수열 중 가장 큰 수열을 찾을 때 사용되는 알고리즘이다.

아래와 같이 크게 2가지 방식으로 구현한다.

1. DP
2. BinarySearch

DP

이번 포스팅에서는 3가지 방식을 통해 구현하고자 한다.

가장 간단한 방법은 arr[i]값이 최대 몇번째인지 알기 위해 arr[0]부터 arr[i-1]까지 값을 비교해가며 값이 증가하는 순서대로 몇번째인지 찾는 방법이다.

말로는 이해하기 힘드니, 아래의 예제를 보도록 하자.

위의 표에서 idx는 인덱스, arr는 우리가 최장 증가 수열을 구하기 위한 전체 리스트, dp는 최장 증가 수열을 담기 위한 리스트이다.

먼저 0번째 인덱스부터 보면, 첫번째이기 때문에 dp[0] = 1이 된다.

1번째 인덱스에서는 arr[1] > arr[0]이기 때문에, dp[1] = dp[0] + 1 = 2가 된다.

2번째 인덱스에서는 arr[2] > arr[0]이지만 arr[2] < arr[1]이기 때문에 dp[2] = dp[0] + 1 = 2가 된다.

3번째 인덱스에서는 arr[3] > arr[0] 이지만 arr[3] < arr[1], arr[3] < arr[2]이기 때문에 아래와 같이 dp[3] = dp[0] + 1가 된다.

4번째 인덱스에서는 arr[0] < arr[2] < arr[4] or arr[0] < arr[3] < arr[4]이 되기에 dp[4] = dp[2] + 1 or dp[3] + 1 = 3이 된다.

그리고 이와 같은 방식으로 진행하면 아래와 같이 결과가 나온다.

정리하자면, 어떠한 인덱스가 최대 몇번째인지 알기위해 그 인덱스보다 전 인덱스들의 값들을 증가순으로 살펴보면서 어떠한 인덱스가 전 인덱스보다 높을 경우 해당 인덱스값을 더하여 몇번째인지 업데이트한다.

def lisWithDp(arr):
    dp = [1 for _ in range(M)]
    for i in range(M):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j]+1)
    return dp

BinarySearch

dp방식에는 i번째 인덱스에 해당하는 순위를 알기위해 0~i-1번째 인덱스들을 탐색하여 알았다면, 이분탐색을 사용하는 방법의 핵심은 0부터 i-1번째 인덱스를 탐색하는게 아니라 이분탐색을 통해 해당 수가 들어갈 자리를 찾고 그 자리에 삽입하는 방법이다.

마찬가지로 예를 통해 알아보자.

이러한 리스트가 있을 때, 우선 0번째 인덱스부터 살펴볼것이다. 당연히 첫번째 임으로 dp = [1]이 될것이다.

그 다음 1번째 인덱스의 값이 7이기 때문에 dp[-1] = 1보다 크기 때문에 dp에 append해준다.

2번째 인덱스의 값은 3임으로 dp[-1] = 7보다 작기 때문에, dp 리스트에 이분탐색을 통해 들어갈 자리를 찾고 변경해야 한다. 이분탐색을 직접 구현할 수 있지만, 파이썬에서 bitsect이라는 라이브러리를 사용하면 쉽게 구현할 수 있다.

그럼으로 arr[2] = 3이 dp[1]자리에 들어가서 아래와 같아진다.

그 다음 단계는 아래와 같이 진행된다.

결과적으로 arr = [1,7,3,2,5,10,3]에서 dp = [1,2,3,10]가 도출되어 결과적으로 최장 증가 수열의 크기는 4임을 알 수 있다.

def lisWithBinarySearch1(arr):
    dp = [arr[0]]
    for i in range(M):
        if arr[i] > dp[-1]:
            dp.append(arr[i])
        else:
            dp[bisect.bisect_left(dp,arr[i])] = arr[i]
        print(dp)
    return dp

문제점

최장 증가 수열의 크기는 알 수 있지만, 정작 어떠한 원소로 진행되는지는 위의 코드로는 알 수 없다. 왜냐하면 계속 새로운 값으로 변경되기 때문이다.

어떠한 원소로 이뤄졌는지 알아내기 위해 먼저 dp방법을 통해 순서를 알 수 있는 리스트 dp를 알아낸 다음, 해당 dp에서 최대값을 찾아낸다. 왜냐하면 순서가 최대값을 기준으로 1부터 해당 최대값으로 최장 수열이 이뤄져있기 때문에, 최대값 이상은 탐색할 필요가 없다.

아래의 코드를 보면 이해하기 쉬울 것이다.

def listWithBinarySearch2(arr):
    dp = [1 for _ in range(M)]
    for i in range(M):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j]+1)
    maxDp = max(dp)
    print("max_dp : ",maxDp)

    maxIdx = dp.index(maxDp)
    lis = []
    while maxIdx >= 0:
        if dp[maxIdx] == maxDp:
            lis.append(arr[maxIdx])
            maxDp -= 1
        maxIdx -= 1
    lis.reverse()
    return lis

위의 코드에서 reverse를 한 이유는 최대 순서값을 먼저 받았기 때문에 증가순으로 정리하기 위해 리스트를 역순으로 바꾸었다.

결론 및 정리

1. Lis는 증가하는 수열 중 가장 큰 수열을 찾을 때 사용되는 알고리즘
2. DP방식은 dp[i]을 알아내기 위해, arr[0]부터 arr[i-1]까지 값과 arr[i]를 비교하며 dp[i]을 알아낸다.
3. BinarySearch방식은 이분탐색을 사용하여 dp의 원소들을 업데이트하여 정확히 어떠한 원소로 최장 증가 수열이 만들어지지는 모르지만, 개수는 알 수 있다.
4. 이를 개선하고자 DP방식에서 dp리스트에서 최대값을 찾고 최대값에서 하나씩 빼가며 어떠한 원소들로 이뤄질수 있는지 찾아낸다.