부분 배열(partition)
✔️ 부분 배열은 원본 배열의 연속된 요소들로 구성됩니다.
✔️ 예를 들어, 배열 [1, 2, 3, 4, 5]의 부분 배열은 [2, 3, 4]이 될 수 있지만, [2, 4, 5]는 부분 배열이 아닙니다.
✔️ 부분 배열은 원본 배열의 연속적인 구간을 그대로 유지합니다.부분 수열(subsequence)
✔️ 부분 수열은 원본 배열에서 일부 요소를 선택하여 만들어진 수열입니다. 선택된 요소들은 원본 배열에서의 순서를 유지하지만, 반드시 연속적일 필요는 없습니다.
✔️ 예를 들어, 배열 [1, 2, 3, 4, 5]의 부분 수열은 [1, 3, 5]가 될 수 있습니다. 여기서 중요한 것은 원본 배열에서의 순서가 유지된다는 점입니다.
✔️ 부분 수열은 원본 배열의 요소들 중 일부를 선택하여 구성되며, 선택된 요소들 사이에는 간격이 있을 수 있습니다.
⭐ "부분 배열"은 항상 연속된 요소들로 구성된다는 점에서 "부분 수열"보다 좀 더 제한적인 개념입니다. 부분 수열은 연속적일 수도 있고 아닐 수도 있지만, 부분 배열은 반드시 연속적입니다.
LIS
최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 부분 수열(subsequence) 개념을 사용합니다. LIS에서의 "부분 수열"은 원본 수열에서 일부 요소를 선택하여 얻을 수 있는 수열로, 선택된 요소들은 원본 수열에서의 순서를 유지하지만 반드시 연속적일 필요는 없습니다.
LIS의 핵심은 선택된 요소들이 증가하는 순서를 유지한다는 것입니다. 이것은 원본 수열에서 임의의 위치에 있는 요소들을 선택할 수 있음을 의미하며, 이러한 선택된 요소들이 반드시 연속적일 필요는 없습니다.
예를 들어, 수열 [10, 22, 9, 33, 21, 50, 41, 60, 80]에서 최장 증가 부분 수열은 [10, 22, 33, 50, 60, 80]이 될 수 있습니다. 이 경우, 선택된 요소들은 원본 수열에서 연속적이지 않지만, 증가하는 순서를 유지합니다.
결과적으로, LIS는 부분 수열의 개념을 사용하며, 연속성보다는 선택된 요소들의 증가하는 순서가 중요합니다.
Two Pointer
투 포인터 알고리즘은 "부분 배열(Partition)" 개념을 사용합니다. 이것은 원본 배열에서 연속적인 요소들로 구성된 배열을 의미하며, 투 포인터는 이러한 연속된 부분을 찾아내는 데 사용됩니다.
예를 들어, 배열 [1, 2, 3, 4, 5, 6]에서 연속된 부분 배열은 [1, 2, 3]와 같은 형태입니다.
즉, [1, 2, 4, 6]은 연속된 부분 배열이 아닙니다. 이 경우, 요소들 사이에 건너뛴 부분이 있기 때문입니다. 투 포인터 알고리즘은 이러한 연속적인 부분 배열을 찾는 데 사용되며, 배열의 한 위치에서 시작하여 연속적으로 요소들을 포함하면서 조건에 맞는 최적의 부분 배열을 탐색합니다.
예를 들어, 배열에서 특정 합을 만족하는 최소 길이의 연속 부분 배열을 찾는 경우, 투 포인터 알고리즘은 배열을 순차적으로 탐색하면서 시작 포인터와 끝 포인터를 조정하여 조건에 맞는 연속된 부분 배열을 찾습니다.
결론
최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 "부분 수열(Subsequence)" 개념을 사용합니다. 이것은 원본 배열에서 순서를 유지하며 선택된 요소들로 구성된 수열을 의미하며, 선택된 요소들은 반드시 연속적일 필요가 없습니다.
이 두 개념은 배열 또는 수열을 다루는 방식에 있어 핵심적인 차이를 가집니다. 투 포인터는 배열의 연속적인 구간을 탐색하는 데 초점을 맞추고, LIS는 증가하는 순서를 유지하는 수열의 부분 집합을 찾는 데 중점을 둡니다.
