LIS 알고리즘은 왜 그렇게 헷갈리는 걸까?

#가장 긴 증가하는 부분 수열 문제 lis 는 어떤 수열이 주어질 때, 그 수열의 증가하는(즉, 모든 원소가 이전 원소보다 큰) (연속하지 않아도 되는) 부분수열 중 가장 긴 것을 찾는 문제입니다. 이 문제를 푸는 몇 가지 알고리즘이 알려져 있지만 알고리즘 문제풀이에서 자주 사용하는 것은 입니다.

저도 이 알고리즘을 처음 배울 때 알고리즘에서 관리하는 배열(이하 'LIS 배열')이 원래 수열의 부분수열이 아닌 것이 조금 의아하게 느껴졌고, 당시에 트친이었던 분도 같은 의문을 품는 것을 보고 글을 작성하기로 했었습니다.

수열 에 대해 이 알고리즘이 밟는 단계를 자연어로 설명하면 다음과 같습니다.

1. 빈 배열 을 만든다.
2. 의 각 원소 에 대해...
   1. 에 이분 탐색을 해서 이상인 첫 원소를 찾는다.
   2. 그런 원소가 없을 경우, 의 맨 뒤에 를 삽입한다.
   3. 그렇지 않을 경우, 그 원소를 로 교체한다.
3. 의 최종 길이가 최장 증가 부분수열의 길이이다. (왜???)

아무래도 과정이 다소 뜬금없이 느껴지는데, 구글링을 해봐도 속 시원한 답을 제시해주지는 않습니다. 그나마 영문판 위키백과에서는 알고리즘이 실행되는 GIF 이미지를 제시하고 있는데, 그 위의 설명을 보면 엄청난 수식과 텍스트의 압박이 밀려옵니다. (재밌는 사실! 글을 처음 작성할 때는 해당 페이지에 말 그대로 "(Need to make this statement clearer)"라는 내용이 있었습니다.)

직접 해 보자!

백준에 ALU^{arithmetic logic unit}에 감정이입을 하는 문제가 있었으니, 이 글에서도 LIS 알고리즘에 감정이입을 해 봅시다.

규칙은 간단합니다! 순서대로 들어오는 노드를 트리에 달아서 키우면 됩니다. 처음에는 노드가 주어지고, 원하는 노드를 누르면 새 노드를 자식으로 붙일 수 있습니다. 단, 증가 수열을 만드는 게임이기 때문에 자기 자신보다 작은 값을 가지는 노드에만 붙일 수 있습니다.

게임을 마치면 노드에서 얼마나 멀리까지 자랐는지를 기준으로 점수를 매깁니다. (루트 역할을 하는 노드를 무시한다면) 트리의 얕은 노드에서 깊은 노드로 가는 경로가 증가 부분 수열의 역할을 합니다. 최대한 깊은 트리를 키워 봅시다!

최고 점수를 달성하셨나요?

효율적인 필승 전략 짜기

게임 난이도가 어떻게 느껴졌을지 모르겠는데, 일단 무작정 최대한 깊은 노드에 붙인다는 방향을 정하고 필승 전략을 짤 수 있습니다.

1. 들어오는 노드마다...
   1. 트리를 오른쪽부터 훑으면서 들어오는 값 미만인 첫 노드에 붙인다.

LIS 게임 공략 참 쉽죠?

깊이별로 쪼개기

쉽긴 한데, 지루하다는 사실은 무시할 수 없습니다. 눈이 고생하지 않도록 머리를 써 봅시다.

잘 생각해 보면, 트리에서의 깊이만 같다면 들어오는 노드를 무슨 노드에 붙이든 앞으로의 진행에는 딱히 상관이 없고 위치만 바뀔 뿐이라는 것을 알 수 있습니다. 전략을 아주 조금만 수정해 봅시다.

1. 들어오는 노드마다...
   1. 트리를 오른쪽부터 깊이별로 훑으면서...
      1. 같은 깊이의 노드 중에 들어오는 값 미만의 노드가 있으면 그 중 아무데나 붙인다.

처음 세운 전략에서 표현 빼고 아무것도 바뀐 것은 없습니다. 그런데 '아무데나' 대신 규칙을 세워서 순서를 정하면 조금 더 효율적으로 게임을 할 수 있을 것 같지 않나요?

최솟값 구하기

위의 규칙에서 '들어오는 노드의 값이 누른 노드의 값보다 크다면'에 집중해 봅시다. 들어오는 노드 를 어떤 노드 에 붙일 수 있다면, 보다 더 작은 노드 에는 당연히 붙일 수 있습니다(이고 이면 이므로). 즉, 같은 깊이에 큰 노드와 작은 노드가 있다면 큰 노드는 아예 볼 필요가 없고 작은 노드만 확인하면 되겠습니다!

1. 들어오는 노드마다...
   1. 트리를 오른쪽부터 깊이별로 훑으면서...
      1. 같은 깊이의 노드 중 최솟값을 구한다.
      2. 그 노드가 들어오는 값보다 작으면 거기에 붙인다.

그런데 트리를 훑을 때마다 깊이별로 최솟값을 매번 구해야 한다면 이것도 처음 전략보다 나을 바가 없습니다. 노드를 붙이지만 않는다면 최솟값은 바뀔 일이 없으니 깊이별로 최솟값을 메모해 봅시다.

1. 트리의 깊이별 최소 노드를 메모할 배열을 준비한다.
2. 들어오는 노드마다...
   1. 트리를 오른쪽부터 깊이별로 훑으면서...
      1. 그 깊이에 메모해둔 최소 노드를 찾는다.
      2. 그 노드가 들어오는 값보다 작으면...
         1. 거기에 들어오는 노드를 붙인다.
         2. 새로 붙인 노드에 해당하는 깊이의 최소 노드를 새로 계산한다.

물론 최소 노드를 새로 계산할 때도 같은 깊이의 모든 노드를 확인할 필요가 없고, 기존 노드(있을 경우)와 새 노드만 비교하면 됩니다.

1. 트리의 깊이별 최소 노드를 메모할 배열을 준비한다.
2. 들어오는 노드마다...
   1. 트리를 오른쪽부터 깊이별로 훑으면서...
      1. 그 깊이에 메모해둔 최소 노드를 찾는다.
      2. 그 노드가 들어오는 값보다 작으면...
         1. 거기에 들어오는 노드를 붙인다.
         2. 새로 붙인 노드가 깊이 기록을 경신했을 경우, 그 노드가 자동으로 최소 노드가 된다.
         3. 그렇지 않을 경우, 기존의 최소 노드와 새로 붙인 노드를 비교하고 최소 노드를 둘 중 작은 것으로 교체한다.

효율적으로 찾기

이 전략대로 게임을 해보셨다면 왠지 모르게 최소 노드 배열이 증가 수열을 유지하는 것처럼 느껴질 수 있습니다. 사실입니다! 증명은 수학적 귀납법으로 할 수 있습니다. (역시 노드를 무시하겠습니다.)

게임을 처음 시작할 때는 배열이 비어 있습니다. 빈 배열은 공허^vacuous1하게 증가 수열에 해당합니다.

최소 노드 배열이 증가 수열이면 어떤 노드를 추가로 붙여도 증가 수열을 이룬다는 것 역시 보일 수 있습니다. 노드의 값이 라고 하면, 증가 수열이므로 미만인 접두사와 이상인 접미사의 두 조각으로 나눌 수 있습니다. 이때 위의 전략에 의해 새로운 노드는 접두사의 마지막 원소(2.1.2) 다음 원소(2.1.2.1), 즉 접미사의 첫 원소와 같은 깊이를 가집니다. 를 이 위치의 양옆 원소(있을 경우)와 비교해 봅시다.

• 이전 원소: 접두사의 마지막 원소이므로 당연히 보다 작습니다.
• 다음 원소: 접미사의 두 번째 원소입니다. 첫 번째 원소는 일 수도 있지만, 증가 수열이므로 두 번째 원소는 반드시 보다 큽니다.

이제 최소 노드 배열이 항상 증가 수열임을 알았으니, 미만과 이상이 어디서 나뉘는지 더 빨리 확인할 수 있습니다. 이분 탐색을 하면 됩니다!

1. 트리의 깊이별 최소 노드를 메모할 배열을 준비한다.
2. 들어오는 노드마다...
   1. 최소 노드 배열에 이분 탐색을 해서 들어오는 값 미만인 가장 깊은 노드를 찾는다.
   2. 거기에 들어오는 노드를 붙인다.
   3. 새로 붙인 노드가 깊이 기록을 경신했을 경우, 그 노드가 자동으로 최소 노드가 된다.
   4. 그렇지 않을 경우, 기존의 최소 노드와 새로 붙인 노드를 비교하고 최소 노드를 둘 중 작은 것으로 교체한다.

들여쓰기도 많이 줄어들었네요.

조건 없애기

혹시 2.4에서 두 노드를 비교할 때마다 매번 새로 붙인 노드로 교체하기만 하는 것 같다면, 그것도 사실입니다! 기존 원소는 이상인데 들어온 값은 정확히 이므로 들어온 값이 항상 최솟값이 됩니다.

1. 트리의 깊이별 최소 노드를 메모할 배열을 준비한다.
2. 들어오는 노드마다...
   1. 최소 노드 배열에 이분 탐색을 해서 들어오는 값 미만인 가장 깊은 노드를 찾는다.
   2. 거기에 들어오는 노드를 붙인다.
   3. 새로 붙인 노드가 깊이 기록을 경신했을 경우, 그 노드가 자동으로 최소 노드가 된다.
   4. 그렇지 않을 경우, 최소 노드를 새로 붙인 값으로 교체한다.

이제는 더 이상 개선할 점이 없습니다. 그런데 완성된 필승 전략이 어딘가 낯익지 않나요?

1. 빈 배열 을 만든다.
2. 의 각 원소 에 대해...
   1. 에 이분 탐색을 해서 이상인 첫 원소를 찾는다.
   2. 그런 원소가 없을 경우, 의 맨 뒤에 를 삽입한다.
   3. 그렇지 않을 경우, 그 원소를 로 교체한다.
3. 의 최종 길이가 최장 증가 부분수열의 길이이다. (헉!)

지금까지 관리한 최소 노드 배열이 다름아닌 이었습니다!

아래의 인터랙티브 애니메이션에서 이 필승 전략을 따라 게임을 자동으로 클리어하는 과정을 확인해볼 수 있습니다. 눈으로 따라가기 쉽도록 최소 노드 배열에 속하는 노드는 하늘색으로 강조되어 있습니다.

결론: LIS 배열은 그림자다

저는 개인적으로 이 게임에서 키운 트리를 'LIS 트리'라고 부르고 있습니다. LIS 트리에 최솟값이라는 빛을 비추면 LIS 배열이라는 그림자는 자연스럽게 모습을 드러냅니다. 제가 생각하는 LIS 알고리즘이 이해하기 어려운 이유는, 직관적으로 조작할 수 있는 대상인 LIS 트리를 가린 채 그림자만 보고 알고리즘을 이해하려고 했기 때문이 아닐까 싶습니다. LIS 트리가 눈에 들어오기 시작했다면 LIS의 실제 값을 역추적하는 과정도 쉽게 유도할 수 있습니다.

이 글을 처음 썼을 때부터 들었던 생각인데, LIS 알고리즘을 다루는 기존 자료에서는 LIS 트리를 거의 언급하지 않는 게 아쉽습니다. (있는데 제가 모르는 거였다면 꼭 알려주세요.) 앞으로는 LIS 트리를 자주 볼 수 있었으면 좋겠네요.

1 ↑

전건과 후건으로 이루어진 명제에 대해, 전건이 성립하지 않기 때문에 그 명제가 저절로 성립하는 경우를 이르는 말. 예를 들어, 명제 '공집합의 모든 원소는 소수이다'는 공허참^{vacuously true}이다.