C++에서 최소 변경으로 엄격하게 증가하는 정수 배열 만들기

이 튜토리얼에서는 최소한의 변경만으로 배열을 엄격하게 증가하는 정수 배열로 변환하는 프로그램을 살펴보겠습니다.

정수 배열이 하나 주어지며, 우리의 과제는 배열의 원소를 가능한 한 적은 횟수만 변경하여 전체 배열이 엄격하게 증가하는 순서, 즉 각 원소가 바로 앞 원소보다 반드시 커지도록 만드는 것입니다.

접근 방법

이 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘을 응용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 변경하지 않고 그대로 유지할 수 있는 원소들의 최대 개수를 구합니다.
• 두 원소 arr[i]와 arr[j]를 동시에 유지하려면, 인덱스 차이만큼의 값 여유가 있어야 사이의 원소들을 서로 다른 정수로 조정할 수 있습니다. 따라서 (i - j) ≤ (arr[i] - arr[j]) 조건을 만족해야 합니다.
• 유지 가능한 원소의 최대 개수를 len이라 하면, 필요한 최소 변경 횟수는 n - len이 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
//필요한 변경 횟수 계산
int remove_min(int arr[], int n){
    int LIS[n], len = 0;
    for (int i = 0; i < n; i++)
    LIS[i] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && (i-j)<=(arr[i]-arr[j])){
                LIS[i] = max(LIS[i], LIS[j] + 1);
            }
        }
        len = max(len, LIS[i]);
    }
    //필요한 변경 횟수 반환
    return n - len;
}
int main(){
    int arr[] = { 1, 2, 6, 5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << remove_min(arr, n);
    return 0;
}

출력 결과

2

코드 설명

입력 배열 { 1, 2, 6, 5, 4 }에서는 1, 2, 6 세 원소를 그대로 유지할 수 있으므로(len = 3), 나머지 두 원소만 변경하면 됩니다. 예를 들어 배열을 { 1, 2, 6, 7, 8 }처럼 바꾸면 엄격하게 증가하는 배열이 되며, 이때 변경 횟수는 최솟값인 2입니다.

이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이고, LIS 배열을 위해 O(n)의 추가 공간이 필요합니다.