LIS 알고리즘

BOJ의 11053번 가장 긴 증가하는 부분 수열을 풀기 위해선 LIS를 알아야 합니다.
LIS에 대해서 정리하기 위해 글을 씁니다.

LIS ?

LIS는 Longest Increasing Subsequence 의 약자로 주어진 배열에 대해 증가하는 부분수열을 찾기 위한 알고리즘입니다.
LIS 알고리즘에는 두 가지의 시간복잡도에 대한 풀이 방법이 존재합니다.

  1. O(N^2) - 이중 반복문을 이용한 방식
  2. O(N∙logN) - 반복문과 이진탐색을 이용한 방식

BOJ의 11053번 문제를 가지고 두 가지 풀이 방식을 모두 알아보겠습니다.

O(N^2) 풀이

11053번 문제에서 주어진 다음과 같은 수열에서 최장 부분 수열의 길이를 구하기 위해서는 길이 배열을 하나 만들어서 하나씩 체크하면서 길이 배열을 채워나갑니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = { }

처음 선택되는 10은 시작이므로 부분 수열의 첫번째 값이 됩니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = {1, }

두번째부터 이전값들의 부분수열을 비교해서 길이를 측정해야합니다. 20은 10보다 크기 때문에 증가하는 부분 수열을 만족하므로 첫번째 10의 부분 수열 길이 + 1을 해줍니다

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = {1, 2}

세번째 값인 10을 선택하면 이전의 10, 20과 비교해야합니다.
첫번째 값인 10과 같으므로 증가하는 수열을 만족하지 않기 때문에 그대로 길이는 1입니다.
두번째 값인 20보다는 작으므로 길이는 1이 됩니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = {1, 2, 1}

네번째값인 30을 선택하면 이전의 10, 20, 10과 비교해야합니다.
첫번째 10과 비교하게 되면 값이 더 크므로 첫번째 10의 부분 수열 길이 + 1을 해줍니다. -> 2
두번째 20보다도 크기 때문에 두번째 20의 부분 수열 길이 + 1를 합니다. -> 3
세번째 10보다도 크기 때문에 세번째 10의 부분 수열의 길이 + 1을 해준 값이 되어야하나, 현재 30의 부분 수열 길이가 더 크기 때문에 (3 > 2) 저장하지 않습니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = {1, 2, 1, 3}

다섯번째 값인 20을 이전의 10, 20, 10, 30과 비교해야합니다.
첫번째 10보다 크기 때문에 첫번째 10의 부분 수열 길이 + 1을 해줍니다. -> 2
두번째 20과 같기 때문에 길이는 그대로입니다.
세번째 10보다 크기 때문에 세번째 10의 부분 수열 길이 + 1을 해야하나, 저장된 값이 이미 2이기 때문에 그대로 2입니다.
네번째 30보다 작기 때문에 길이는 그대로입니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = {1, 2, 1, 3, 2}

마지막 50을 비교합니다. 첫번째 10과 비교하게 되면 값이 더 크므로 첫번째 10의 부분 수열 길이 + 1을 해줍니다. -> 2
두번째 20보다도 크기 때문에 두번째 20의 부분 수열 길이 + 1를 합니다. -> 3
세번째 10보다도 크기 때문에 세번째 10의 부분 수열의 길이 + 1을 해준 값이 되어야하나, 현재 30의 부분 수열 길이가 더 크기 때문에 (3 > 2) 저장하지 않습니다.
네번째 30보다 크기 때문에 네번째 30의 부분 수열 길이 + 1를 합니다. -> 4
다섯번째 20보다 크기 때문에 길이를 증가시켜야하나 현재 저장하고 있는 길이의 값이 더 크기 떄문에 저장하지 않습니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
길이 배열 = {1, 2, 1, 3, 2, 4}

길이를 배열에서 Max 길이를 구하게 되면 최장 증가 부분 수열의 길이를 구할 수 있습니다.

풀이 코드


O(N∙logN) 풀이

해당 풀이의 경우 이전의 이중 반복문 방식과 다르게 반복문을 한 번(N)만 돌면서 이진 탐색(logN)을 통해 부분 수열을 구해나갑니다.
해결하기 위해 부분 수열을 저장할 배열, 현재 길이를 저장할 변수가 필요합니다.

수열 배열 = {10, 20, 10, 30, 20, 50}
부분 수열 배열 = {10}
길이 = 1

위와 같이 필요한 내용을 정의한 후, 반복문을 시작합니다.
부분 수열을 만족하기 위해 비교 해야할 것은 현재 선택된 수열의 값과 이전에 저장된 부분 수열의 값을 비교해야합니다.

  • 현재 선택된 수열의 값 > 이전에 저장된 부분 수열의 값이면, 부분 수열 배열에 저장하고 길이 + 1
  • 현재 선택된 수열의 값 <= 이전에 저장된 부분 수열의 값이면, 부분 수열 배열을 이진 탐색하여 교체할 위치를 찾는다.

두번째 20의 경우, 부분 수열 배열의 마지막에 저장된 값보다 크므로 부분 수열 배열에 저장하고, 길이를 증가시킨다.

수열 배열 = {10, 20, 10, 30, 20, 50}
부분 수열 배열 = {10, 20}
길이 = 2

세번째 10의 경우, 부분 수열 배열의 마지막에 저장된 값보다 작으므로 이진탐색을 교체할 위치를 찾아서 변경한다. 첫번째 저장된 10과 같으므로 변경사항이 없다.

수열 배열 = {10, 20, 10, 30, 20, 50}
부분 수열 배열 = {10, 20}
길이 = 2

네번째 30의 경우, 부분 수열 배열의 마지막에 저장된 값보다 크므로 부분 수열 배열에 저장하고, 길이를 증가시킨다.

수열 배열 = {10, 20, 10, 30, 20, 50}
부분 수열 배열 = {10, 20, 30}
길이 = 3

다섯번쨰 20의 경우, 부분 수열 배열의 마지막에 저장된 값보다 작으므로 이진탐색을 교체할 위치를 찾아서 변경한다. 20은 이미 저장되어 있으므로 변경사항이 없다.

수열 배열 = {10, 20, 10, 30, 20, 50}
부분 수열 배열 = {10, 20, 30}
길이 = 3

마지막 50의 경우, 부분 수열 배열의 마지막에 저장된 값보다 크므로 부분 수열 배열에 저장하고, 길이를 증가시킨다.

수열 배열 = {10, 20, 10, 30, 20, 50}
부분 수열 배열 = {10, 20, 30, 50}
길이 = 4

최종적으로 길이는 4인 것을 알 수가 있다.

풀이 코드



참고문서