1ilsang

Developer who will be a Legend

Subset Sum Problem - Dynamic Programming

2019-11-09 1ilsangData-Structure & Algorithm

0 이상의 자연수들의 집합에서 일정 숫자를 포함하는 부분집합의 합이 존재하는지를 찾으려면 어떻게 해야할까?

cover image

위의 그림을 예로 들자면, 6을 포함하는 부분집합은 {3, 2, 1}이 존재한다. 이것을 어떻게 효율적으로 찾아낼까?

int[] arr = { 3, 2, 7, 1 };
int target = 6;

System.out.println(go(arr, target, 0, 0));
////////

boolean go(int[] arr, int target, int curSum, int lo) {
	if(curSum == target) return true;
	if(lo >= arr.length) return false;

	if(arr[lo] > target) return go(arr, target, curSum, lo + 1);
	
	return go(arr, target, curSum + arr[lo], lo + 1) || go(arr, target, curSum, lo + 1);
}

가장 쉬운 방법은 탑다운 재귀로 모든 케이스를 다 보는 것이다. 하지만 위의 경우는 중복된 계산이 엄청나게 일어나게 된다. 따라서 백퍼 시간초과가 나게된다. 그러므로 메모이제션을 하던가, 상향식 다이나믹 프로그래밍을 적용해 풀어야한다.

int[] arr = { 3, 2, 7, 1 };
int target = 6;

System.out.println(go(arr, target));
////

boolean go(int[] arr, int target) {
	boolean[][] memo = new boolean[arr.length][target + 1];
	memo[0][0] = true;

	for(int i = 0; i < arr.length; i++) {
		for(int j = 0; j < target + 1; j++) {
			if(j == 0 || i == 0 && arr[i] == j) {
				memo[i][j] = true;
				continue;
			} else if(i == 0) continue;

			if(arr[i] > j) memo[i][j] = memo[i - 1][j];
			else if(memo[i - 1][j]) memo[i][j] = true;
			else memo[i][j] = memo[i - 1][j - arr[i]];
		}
	}

	return memo[arr.length - 1][target];
}

dp table image

image link: https://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/

DP 테이블은 위와같이 채워지게 된다. 나의 경우는 첫 번째 행을 위와 같이 채우지 않고 바로 시작하는데, 이렇게해도 상관없다. 중요한 점은 위와 같이 상향식 다이나믹 프로그래밍을 적용해 시간복잡도를 지수승에서 N^2 으로 줄였다는 점이다.

DP 테이블에서 0에 해당하는 애들은 전부 true 인 것을 볼 수 있는데, 이 경우는 0을 만들 수 있는 공집합이 있으므로 항상 트루인 경우이다. 그 외에 첫 번째 행은 비교 대상이 자신밖에 없으므로 자신과 열의 값이 같은지 비교해준다. 마지막으로 2번째 행부터는 자신의 값이 열보다 크다면, 위의 값을 그대로 가져오고 이전의 값이 트루라면 그대로 트루를 가져오고 그게 아니라면 이전 행의 자신의 값을 뺀 값을 가져오고 있다.

이거 잘 보면 배낭 문제와 매우 유사한 것을 알 수 있다!

행은 가치에 해당하고 열은 무게에 해당한다고 바라보면, 행의 값(가치)을 넣을 때 버틸 수 있는 무게(열의 값)를 비교하는 것이다.

그렇기 때문에 맨 처음 2 의 경우 0, 1 는 어짜피 담을 수 없는 값이기 때문에 무시하고 넘어간다(이전 행의 값을 가져옴) 그 후 j >= 2의 상황에서 만약 이전 행의 값(memo[i - 1][j])이 true 라면 자신도 true로 해준다. 이 경우는 이전의 값 3일때 true이므로 당연히 2의 값일 때도 true여야 하기 때문이다.(2를 선택 하지 않고 3만 선택해 3을 만들 수 있으므로.)

나머지 경우는 이전 행의 열에 자신의 값을 빼주어 해당 위치의 값을 가져온다. 이게 조금 이해가 안될 수 있는데, 배낭과 연관해 생각해보면 간단하다. 현재까지의 배낭의 무게에서 현재 물건의 무게를 빼면 그 물건이 들어가기 전의 마지막 가치값이 나온다.(memo[i - 1][j - arr[i]]) 이 가치값이 만약 true 라면 자신이 들어가도 true 이므로 true 를 반환하면 되는 것이다. 반대로 말하면 이 가치값이 false라면 자신이 들어가는게 무의미하므로 false이다.(이미 이전의 계산에서 해당 값을 만들 수 없으므로 자신을 더해줘도 해당 열의 값을 맞출 수 없다는 뜻)

글로 써서 장황하지만, 천천히 따라가면서 디피테이블을 바라보면 쉽게 이해할 수 있다.


p.s 그렇다면 true/false가 아닌 부분집합의 원소를 반환해야 한다면 어떻게 해야할까?

사실 이건 DP 테이블에 이미 답이 있다. memo[arr.length - 1][target] 에서부터 거슬러 올라가며 True 인 값의 경계들을 쫓아가면 그 값들이 Target 을 만들 수 있는 부분집합의 원소들이다.

그럼 이만!