부분 수열

부분 수열(Subsequence)은 어떤 주어진 수열에서 순서를 유지하면서 일부 또는 전체 원소를 선택하여 만들 수 있는 새로운 수열이다.

중요한 점은 선택된 원소들이 원래 수열에서의 순서를 유지해야 한다는 것이다.

 

수열이 A,B,C,D라고 할 때, 가능한 부분 수열 중 예시는 다음과 같다.

• A,B (첫 번째와 두 번째 원소 선택)
• B,D (두 번째와 네 번째 원소 선택)
• A,C,D (첫 번째, 세 번째, 네 번째 원소 선택)
• C (세 번째 원소만 선택)
• A,B,C,D (모든 원소 선택, 이 경우 원래 수열과 동일)
• [] (아무 원소도 선택하지 않음, 빈 부분 수열)

원소를 선택할 때, 원래 수열에서의 순서를 변경하거나 원소를 반복해서 사용할 수 없다.

예를 들어, B,A나 C,C는 유효한 부분 수열이 아니다.

부분 수열의 개념은 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence) 찾는 dp 활용 문제 등에서 등장할 수 있다.