C++에서 인접하지 않은 두 요소를 선택하는 최대 합 구하기 - 세트 2

이 문제에서는 배열 arr[]가 주어지며, 우리의 목표는 배열에서 서로 인접한 두 요소를 동시에 포함하지 않는 조건 하에 얻을 수 있는 최대 합을 구하는 프로그램을 C++로 작성하는 것입니다.

문제 설명

배열에서 요소들을 선택하여 합을 만들되, 합산 시퀀스에 포함된 두 숫자가 원본 배열에서 서로 인접(바로 옆)해서는 안 됩니다. 이러한 조건을 만족하면서 얻을 수 있는 최대 합을 찾아야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

arr[] = {5, 1, 3, 7, 9, 2, 5}

출력

22

설명

인덱스 0부터 시작하여 한 칸씩 건너뛰며 선택 : 5 + 3 + 9 + 5 = 22
인덱스 1부터 시작하여 한 칸씩 건너뛰며 선택 : 1 + 7 + 2 = 10

위 예시에서 최댓값은 22이므로 정답은 22가 됩니다. 단순히 홀수 번째 또는 짝수 번째 요소만 더하는 방식으로는 최적의 해를 보장할 수 없기 때문에, 더 일반적인 접근 방식이 필요합니다.

해결 접근 방식: 동적 계획법(Dynamic Programming)

이전 세트에서는 한 가지 문제 풀이 방법을 살펴보았습니다. 이번에는 동적 계획법(DP)을 활용한 접근 방식을 알아보겠습니다.

동적 계획법으로 문제를 해결하려면 현재 인덱스까지 도달했을 때 얻을 수 있는 최대 합을 저장하는 DP[] 배열을 생성해야 합니다. 그런 다음 이 배열을 활용해 각 인덱스에서의 최대 합을 계산합니다.

핵심 아이디어는 다음과 같습니다. 각 위치 i에서 우리는 두 가지 선택지가 있습니다.

• 현재 요소 arr[i]를 선택하는 경우 → dp[i+2] + arr[i]
• 현재 요소를 건너뛰는 경우 → dp[i+1]

따라서 현재 위치의 최댓값은 위 두 값 중 더 큰 값이 됩니다. 즉, dp[i] = max(dp[i+1], dp[i+2] + arr[i])입니다.

재귀 호출 시 이미 계산된 상태는 currState[] 배열로 추적하여 중복 연산을 방지함으로써(메모이제이션) 알고리즘의 효율성을 높일 수 있습니다. 이렇게 하면 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)이 됩니다.

예제 코드

아래 프로그램은 이 솔루션이 실제로 어떻게 동작하는지 보여줍니다.

#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
    if(a > b)
        return a;
        return b;
    }
int calcMaxSumWOAdj(int arr[], int i, int n){
    if (i >= n)
        return 0;
    if (currState[i])
        return DP[i];
    currState[i] = 1;
    DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
    return DP[i];
}
int main(){
    int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
    int n = sizeof(arr) / sizeof(int);
    cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
    return 0;
}

실행 결과

The maximum sum such that no two elements are adjacent is 22

마무리

동적 계획법을 적용하면 모든 경우의 수를 단순히 나열하는 브루트포스 방식(시간 복잡도 O(2ⁿ))보다 훨씬 효율적으로 문제를 해결할 수 있습니다. 메모이제이션을 통해 부분 문제의 결과를 재활용하면 선형 시간 안에 답을 구할 수 있어, 입력 배열의 크기가 커져도 안정적인 성능을 기대할 수 있습니다.