부분수열의 합: DFS의 문제점과 DP로의 전환

🔷 부분수열의 합: DFS의 문제점과 DP로의 전환

✅ 1. DFS 방식의 문제점

배열이 주어졌을 때, 숫자를 하나씩 선택하거나 선택하지 않아 만들 수 있는 모든 합을 찾는 문제를 생각합니다.

예시로 다음 배열을 생각합니다.

A = [4, 7, 2, 5]

각 숫자는 독립적으로 선택(1)하거나 선택하지 않음(0)을 결정합니다. 이 과정에서 모든 가능한 경우의 수를 살펴보는 것이 DFS입니다.

모든 경우를 비트열(0과 1의 조합)로 표현하면 다음과 같습니다.

비트열	선택된 숫자	합
0000	없음	0
0001	5	5
0010	2	2
0011	2+5	7
0100	7	7
0101	7+5	12
0110	7+2	9
0111	7+2+5	14
1000	4	4
1001	4+5	9
1010	4+2	6
1011	4+2+5	11
1100	4+7	11
1101	4+7+5	16
1110	4+7+2	13
1111	4+7+2+5	18

이 과정에서 문제점은 같은 합을 중복하여 계산한다는 것입니다.

예를 들어,

• 합이 7인 경우: (0011) 2+5, (0100) 7
• 합이 9인 경우: (0110) 7+2, (1001) 4+5
• 합이 11인 경우: (1011) 4+2+5, (1100) 4+7

이렇게 같은 합을 여러 번 중복으로 탐색하여 시간이 불필요하게 낭비됩니다.

✅ 2. DP로 해결 아이디어

DFS의 중복된 계산 문제를 해결하기 위한 아이디어가 DP(Dynamic Programming, 동적계획법)입니다.

DP의 핵심 아이디어는 이미 계산한 결과를 메모해두고, 다시 사용하여 중복 계산을 하지 않는 것입니다.

📌 무엇을 기록할지

DP 배열에서 기록할 내용은 다음과 같습니다.

• 지금까지 만든 합이 가능한지 불가능한지 (true or false)

예시 배열 [4,7,2,5]를 사용하면, 만들 수 있는 최대 합은 \(4+7+2+5=18\)입니다. 즉, DP 배열의 크기는 \(18+1 = 19\)가 필요합니다.

다음과 같이 정의합니다.

• \(DP[x]\) : 합 \(x\)를 만들 수 있는가? (true 또는 false)

처음 아무 숫자도 선택하지 않았으므로 초기 DP 상태는 다음과 같습니다.

DP[0] = true, 나머지 DP[1~18] = false

📌 점화식 설정 방법

배열의 각 숫자를 하나씩 보면서, 지금까지 가능한 합에서 새로 숫자를 추가할 때마다 다음 점화식을 사용합니다.

DP[현재 합 + 새 숫자] = true

여기서 주의할 점은 반드시 DP 배열을 뒤에서부터 앞으로 업데이트해야 합니다. 이유는 앞에서부터 업데이트하면 같은 단계에서 새롭게 추가된 값이 다시 중복 사용될 가능성이 있기 때문입니다.

구체적으로, 숫자 7을 처리할 때를 예로 들면:

• 현재 가능한 합 {0,4}에서
• 7을 더해 {7,11}이 추가로 가능해집니다.
• 이때 반드시 18에서 0 방향으로 업데이트해야 중복이 발생하지 않습니다.

📌 DP 배열을 예시로 업데이트 하는 과정

예시 배열 [4,7,2,5]를 DP로 업데이트 하는 과정을 애니메이션처럼 단계적으로 살펴봅니다.

📌 초기상태

DP[0]=true // 합 0은 항상 가능

📌 첫 번째 숫자 (4)를 추가로 고려

• 기존 DP: {0}
• 추가 가능한 합: {0+4=4}
• 업데이트 결과: {0,4}

DP[0]=true, DP[4]=true

📌 두 번째 숫자 (7)를 추가로 고려

• 기존 DP: {0,4}
• 추가 가능한 합: {0+7=7, 4+7=11}
• 업데이트 결과: {0,4,7,11}

DP[0]=true, DP[4]=true, DP[7]=true, DP[11]=true

📌 세 번째 숫자 (2)를 추가로 고려

• 기존 DP: {0,4,7,11}
• 추가 가능한 합: {0+2=2, 4+2=6, 7+2=9, 11+2=13}
• 업데이트 결과: {0,2,4,6,7,9,11,13}

DP[0]=true, DP[2]=true, DP[4]=true, DP[6]=true, DP[7]=true, DP[9]=true, DP[11]=true, DP[13]=true

📌 네 번째 숫자 (5)를 추가로 고려

• 기존 DP: {0,2,4,6,7,9,11,13}
• 추가 가능한 합: {0+5=5, 2+5=7(중복), 4+5=9(중복), 6+5=11(중복), 7+5=12, 9+5=14, 11+5=16, 13+5=18}
• 중복을 제외한 최종 결과: {0,2,4,5,6,7,9,11,12,13,14,16,18}

이 과정에서 DP 배열은 숫자를 추가할 때마다 새로운 가능한 합을 기록하면서 중복되는 합은 추가하지 않습니다.

✅ 3. DP의 코드 구현

#include 
using namespace std;

int main() {
    int A[4] = {4,7,2,5};
    bool DP[19] = {false}; // 가능한 합 최대 18이므로 0~18까지

    DP[0] = true; // 아무것도 안 고른 상태는 합 0 가능

    for(int i=0; i<4; i++){
        int num = A[i];

        // DP 배열을 뒤에서 앞으로 업데이트해서 중복 방지
        for(int sum=18; sum>=0; sum--){
            if(DP[sum] == true && sum+num<=18){
                DP[sum+num] = true;
            }
        }
    }

    // 결과 출력
    cout << "가능한 합들: ";
    for(int sum=0; sum<=18; sum++){
        if(DP[sum] == true) cout << sum << " ";
    }
    return 0;
}

📌 상세한 코드 설명

• 배열 A: 숫자 저장
• DP 배열: 합이 가능한지 여부 저장 (true이면 가능)
• 처음 상태로 DP[0]=true 설정 (숫자를 안고른 상태)
• 각 숫자를 추가하면서 기존 가능한 합에 추가하여 DP 업데이트
• 뒤에서 앞으로 내려오면서 업데이트하여 같은 숫자를 중복으로 계산하는 문제를 해결합니다.
• 최종 DP 배열에 기록된 값이 가능한 모든 합입니다.

📌 위 코드의 실제 출력결과

가능한 합들: 0 2 4 5 6 7 9 11 12 13 14 16 18

✅ 결론

• DFS는 같은 합을 여러 번 중복 계산해 시간이 오래 걸립니다.
• DP는 이미 계산한 결과를 저장하고 재사용하여 중복을 없애 빠릅니다.
• DP 배열을 사용해 중복 계산을 막을 수 있으며, 간단한 배열만으로 구현할 수 있습니다.
• STL 없이도 간단한 고정 배열로 효율적으로 구현 가능합니다.