[동적 프로그래밍 예제] 부분집합의 합(C언어)

 

[동적 프로그래밍(DP)] 부분집합의 합 

 

본 포스팅은 도서 "문제로 풀어보는 알고리즘"(황인욱, 김용혁 지음)을 공부한 내용을 정리하기 위한 글임을 밝힙니다.

 

 

동적 프로그래밍(Dynamic Programming)이란?

 

동적 프로그래밍의 '프로그래밍'은 컴퓨터 프로그래밍을 뜻하는 말이 아니라 테이블을 채워나가면서 값을 구하는 방법을 일컫는다. 그래서 원어인 "Dynamic Programming"을 '동적 계획법'으로 번역하기도 한다.

 

동적 프로그래밍은 재귀적으로 작성한 프로그램이 중복 계산으로 시간과 메모리를 낭비할 때, 메모이제이션 외에 쓸 수 있는 또 다른 방법이다.

 

그렇기 때문에 정보 올림피아드에서 자주 출제되며, 많은 소프트웨어 회사의 기술 면접에서 알고리즘 분야의 문제로 나오는 주제다.

 

메모이제이션은 위에서 아래로 푸는 Top-Down 방식이고, 동적 프로그래밍은 아래에서 위로 푸는 Bottom-Up 방식인 점, 메모이제이션에서는 함수를 호출하는 비용이 드는 반면 동적 프로그래밍은 함수 호출이 없다는 점에서 두 가지 방법은 약간의 차이가 있다. 그러나 부분문제들의 해를 배열에 저장한다는 아이디어는 본질적으로 같다.

 

 

예제 - 부분집합의 합

 

자연수의 집합에서, 부분집합을 택해 원하는 합을 만드는 방법을 생각해보자.

예를 들어, 열 개의 자연수로 이루어진 집합 {6, 9, 13, 14, 20, 21, 22, 30, 49, 55}이 있다.

{6, 14, 21, 49}처럼 네 개의 숫자를 고르면 합이 90이다. {9, 20, 22, 49}를 고르면 합이 100이다.

합이 110이 되게 하는 부분집합이 있을까?

{6, 14, 20, 21, 49}의 합이 110이다.

 

이처럼 원하는 합과 집합이 주어졌을 때 부분집합을 고르는 것이 가능한지 출력하는 프로그램을 작성해보자.

 

[실행 예]

 

input n, m : 110 10                // 원하는 합은 110, 집합 크기는 10

6 9 13 14 20 21 22 30 49 55        // 10개의 수를 입력 받음

possible                           // 110을 만드는 것은 가능

 

input n, m : 101 10

10 20 30 40 50 60 70 80 90 100

impossible                         // 101을 만드는 것은 불가능

 

 

 

 

알고리즘

 

모든 부분집합을 차례로 구해서 합을 확인하는 것도 '가능'은 하다. 그러나 그 방법은 좋은 방법이 아니다. n이 조금만 커져도 문제를 푸는데 굉장히 많은 연산이 수행되어야 한다.

 

먼저 위 예에서 첫 번째로 예시를 든 {6, 9, 13, 14, 20, 21, 22, 30, 49, 55}의 부분집합 중 합이 110인 것이 있는지 찾는 방법을 재귀적으로 생각해보자. 위 집합의 부분집합은 두 가지로 나눌 수 있다.

마지막 원소 55를 포함하는 부분집합과, 포함하지 않는 부분집합이다.

 

1. 55를 포함하고 있는 부분집합 중 합이 110인 것이 있으려면 55를 제외한 {6, 9, 13, 14, 20, 21, 22, 30, 49}의 부분집합 중 합이 55인 것이 있어야 한다.
2. 만약 55를 포함하지 않은 부분집합 중 합이 110인 것이 있으려면 {6, 9, 13, 14, 20, 21, 22, 30, 49}의 부분집합 중 합이 110인 것이 있어야 한다.

 

이로써 원래 집합의 문제를 크기가 하나 작은 집합의 문제로 바꾸었다. 이 아디이러르 일반적으로 나타내보자.

입력을 길이 n인 배열 arr라고 하고, 원하는 합을 m이라고 하자.

함수 isPossible(arr, n, m)을 다음과 같이 정의할 수 있다.

 

 

 

isPossible(arr, n, m)

-> {arr[0], arr[1], ..., arr[n-1]}의 부분집합 중 합이 m인 것이 있으면 1, 없으면 0

 

 

 

 

프로그램 구현(c언어)

 

 

#include <stdio.h>

#define MAXN 30
#define MAXM 400

int set[MAXN][MAXM];

void calculate_subset_sum(int arr[], int n, int m) {
	int i, j;

	for(i = 0; i <= n; i++)
		set[i][0] = i;

	for(j = 1; j <= m; j++)
		set[0][j] = 0;

	for(i = 1; i <= n; i++) {
		for(j = 1; j <= m; j++) {
			set[i][j] = 0;

			if(j >= arr[i-1]) {
				if(set[i - 1][j - arr[i - 1]] == 1)
					set[i][j] = 1;
			}

			if(set[i - 1][j] == 1)
				set[i][j] = 1;
		}
	}
}

int main(int argc, char** argv) {
	int m, n;
	int arr[MAXN];
	int i;

	printf("input m, n : ");
	scanf("%d", &m);
	scanf("%d", &n);
	for(i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	calculate_subset_sum(arr, n, m);

	if(set[n][m])
		printf("Possible\n");
	else
		printf("Impossible\n");
}

 

calculate_subset_sum() 함수는 배열 set에 isPossible() 값을 채우는 함수로, 동적 프로그래밍 방식이기 때문에 n x m에 비례하는 시간을 사용한다.

이 함수로 배열을 채운 후, set[n][m]의 값이 0인지 1인지 확인하면 된다.