배열이 하나 주어졌을 때, 인접하게 선택된 요소들 간의 차이가 0 또는 1이 되도록 요소를 고른 부분 수열(subsequence) 중 가장 길이가 긴 것을 찾는 것이 이 글의 목표입니다. 여기서 부분 수열이란 배열에서 요소의 상대적인 순서를 유지하면서 일부 요소를 생략해 만든 나열을 의미합니다.
문제 이해하기
입력 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }
출력 − 인접 요소 간 차이가 0 또는 1인 최장 부분 수열의 길이: 4
설명 − 원래 순서를 유지한 채 {5, 6, 7, 6}을 선택하면 인접 요소 간 차이가 각각 1, 1, 1로 조건을 모두 만족합니다. 따라서 최장 부분 수열의 길이는 4입니다.
입력 − int arr[] = { 2, 1, 7, 6, 5 }
출력 − 인접 요소 간 차이가 0 또는 1인 최장 부분 수열의 길이: 3
설명 − 차이가 0 또는 1이 되도록 선택할 수 있는 부분 수열은 {7, 6, 5}입니다. 따라서 최장 부분 수열의 길이는 3입니다.
접근 방법: 동적 계획법(DP)
이 문제는 최장 증가 부분 수열(LIS) 문제와 비슷한 방식으로 동적 계획법을 적용해 해결할 수 있습니다. 임시 배열 temp[i]에는 "i번째 요소를 마지막으로 선택했을 때 만들 수 있는 조건 만족 부분 수열의 최대 길이"를 저장합니다.
- 양수와 음수를 모두 포함할 수 있는 정수형 배열을 입력받습니다.
- 배열의 크기를 계산한 뒤, 이후 처리를 위해 배열과 크기를 함수에 전달합니다.
- 입력 배열과 같은 크기의 임시 배열 temp[size]를 준비하고, 변수 maximum을 선언해 0으로 초기화합니다.
- 첫 번째 반복문을 0부터 배열 크기까지 돌면서 temp[i]를 1로 설정합니다. 어떤 요소든 혼자서 길이 1짜리 부분 수열이 될 수 있기 때문입니다.
- 이어서 i를 1부터 배열 크기까지 도는 반복문을 실행합니다.
- 그 안에서 j를 0부터 i 미만까지 도는 내부 반복문을 실행합니다.
- 내부 반복문에서 arr[i]와 arr[j]의 절댓값 차이가 1 이하이고 temp[i] < temp[j] + 1이라면, temp[i]를 temp[j] + 1로 갱신합니다. 즉, j번째 요소로 끝나는 부분 수열 뒤에 i번째 요소를 이어 붙일 수 있는 경우를 확인하는 것입니다.
- 마지막으로 0부터 크기까지 반복문을 돌며 maximum이 temp[i]보다 작으면 maximum을 temp[i] 값으로 갱신합니다.
- maximum 값을 반환하고, 호출부에서 결과를 출력합니다.
이 알고리즘의 시간 복잡도는 O(n²), 공간 복잡도는 O(n)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
//조건을 만족하는 최장 부분 수열의 길이를 계산하는 함수
int maximum_adja(int arr[], int size){
int temp[size], maximum = 0;
for (int i=0; i<size; i++){
temp[i] = 1;
}
for (int i=1; i<size; i++){
for (int j=0; j<i; j++){
if (abs(arr[i] - arr[j]) <= 1 && temp[i] < temp[j] + 1){
temp[i] = temp[j] + 1;
}
}
}
for (int i=0; i<size; i++){
if (maximum < temp[i]){
maximum = temp[i];
}
}
return maximum;
}
int main(){
int arr[] = {1, 5, 3, 7, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"인접 요소 간 차이가 0 또는 1인 최장 부분 수열의 길이: "<<maximum_adja(arr, size);
return 0;
}
실행 결과
인접 요소 간 차이가 0 또는 1인 최장 부분 수열의 길이: 3
위 예제의 배열 {1, 5, 3, 7, 8, 9, 2}에서는 {7, 8, 9}처럼 인접 요소 간 차이가 1씩 나는 세 요소를 순서대로 선택할 수 있으므로 결과는 3이 됩니다.