문제 정의
지금까지 배워왔던 브루트 포스, 분할 정복, 일반 DP, 최적화 DP 모두 문제 해결 과정에서 가장 어려우면서 핵심적인 부분이 큰 문제를 적절한 부분 문제로 나누는 작업이다.
단순 LIS 문제는 수열이 한 개만 주어져서 부분 문제와 상위 문제들 사이의 관계가 비교적 명확하게 드러났는데, JLIS의 경우 수열이 두 개이기 때문에 그 과정이 머릿속으로 떠올리기에 훨씬 복잡했다.
결국 부분 문제사이의 관계를 확실하게 정의하면, 함수의 인자를 결정하고 재귀 호출하는 과정에서의 플로우만 떠올리면 되서 남은 과정은 무척 간단해진다.
문제 풀이
JLIS의 부분 문제 구조는 다음과 같다.
jlis(a,b)에 대해 생각해보자면, a다음에 오는 인덱스가 가르키는 값이 a와 b가가르키는 값 중 큰값보다 크면 그 값에 대해 jlis(x,b) , b다음에 오는 인덱스가 가르키는 값이 클 경우 jlis(a,y)와 같은 식으로 for문을 통해 재귀 함수를 호출해준다.
jlis(a,b)가 뜻하는 건 a,b가 각각 A수열 B수열에서 하나씩 선택됐을 때 나머지 a,b 이후의 인덱스에서 나머지 원소들을 선택하는 경우의 최대 길이이다. 따라서 a,b 이후 조건에 부합하는 어떤 원소를 수열에 추가하고 위 문단에서 얘기한 방식으로 재귀 호출을 시행하고 그 반환값에 1을 더하게 되면, 완벽하게 부분 문제로 나눌 수 있게 되는 것이다.
또한 jlis의 원소로 들어올 수 있는 인덱스는 두 수열의 최대 길이 이하이기 때문에 그 수가 많지 않아 중복이 발생하게 되어 동적 계획법을 통한 효율성 증대가 확실해진다.
느낀 점
결국 어떤 값을 구하는 문제이든 최적화를 하는 문제이든 완전 탐색으로 분석이 가능한 문제는 부분 문제로 나누어 생각할 수 있는 사고 역량이 필수적인 것 같다. 커다란 기계를 보고 그 기계가 동작하는 과정이 그 기계와 유사한 작은 기계들의 수 많은 집합이라는 것을 느끼는 것은 이러한 알고리즘 문제 뿐만 아니라 공학적인 설계를 함에 있어서 정말 많이 사용될 것 같다. 이런 사고력은 알고리즘을 설계하는 프로그래머로서 반드시 갖춰야 한다고 생각한다.
