최적 부분 구조란
앞서 살펴 보았던 동적 계획법 문제는 어떠한 값을 계산하거나, 경로가 존재하는 지에 대한 문제에 사용되었던 방식이다. 최적화 문제는 그러한 계산값이나 경로 중 어떤 것이 최적인지를 계산하는 문제인데, 이 때 설계하는 재귀 함수의 파라미터로 가장 필수적인 값만 넘겨주는 부분 문제의 구조가 최적 부분 구조이다. 이 때 불필요한 값까지 넘겨주게 되면, 메모이제이션에 필요한 컨테이너의 크기가 너무 커지거나, 하나의 값으로 처리할 수 있는 문제들에 대해서 중복해서 계산하게 되기 때문에 비효율적인 알고리즘이 만들어지게 된다.
예시
최대 증가 부분 수열(LIS)를 찾는 문제는 이러한 구조를 생각해 볼 수 있는 적절한 문제이다. 이 문제는 수열에서 하나의 원소를 결정하고 그 원소보다 큰 값들로 이루어진 수열들에 대해서 같은 문제를 재귀적으로 해결하는 방식으로 풀 수 있는데, 이 때 재귀 함수의 파라미터로 지금까지 선택한 원소를 배열로 전달해주게 되면 메모이제이션에 필요한 자료 구조를 결정하는 것이 어려워진다. 이 문제를 해결할 수 있는 좋은 방법은, 어차피 파라미터로 전달될 배열은 새롭게 선택된 시작 원소의 인덱스와 일대일 매칭이 되므로, 그 원소의 인덱스를 파라미터로 재귀함수를 호출하고 메모이제이션에 필요한 자료 구조를 만들면 된다. 즉 이 문제를 해결하기 위한 최적 부분 구조는 부분 문제에 대해 선택된 첫 번째 원소의 인덱스만을 전달해 주면 되는 것이다.
이 문제의 시간복잡도는 n^2인데 문제를 해결하기 위해 필요한 부분 문제의 개수가 각 원소별로 하나씩 있기 때문에 n, 거기에 각 부분 문제 당 다음 원소를 결정하기 위해 사용되는 for문이 한 번 돌아가기 때문에 n*n이 되어 n^2이 된다.
이 문제는 n*log n의 시간 복잡도로 해결 하는 알고리즘도 존재하는데, 그 알고리즘은 매번 배열의 길이를 1씩 늘려가면서 그 길이로 만들 수 있는 부분 수열 중 마지막 원소가 가장 작은 수열을 기억하는 방식으로 이루어진다. 마지막 원소가 가장 작은 수열이 다음으로 선택할 수 있는 원소의 범위가 가장 크기 때문에, 가장 긴 수열을 만들기 위한 수열이 되기 때문이다.
최적화 문제의 해결 과정
- 완전 탐색 알고리즘을 설계한다.
- 최적 부분 구조를 설계한다
- 입력이 배열이거나 문자열인 경우 변환할 수 있다면 변환해준다.
- 메모이제이션을 적용한다.
