[Swift 알고리즘/백트래킹] Sum of subsets 문제

부분집합의 합 문제

부분집합의 합 문제는 S = {w1 , w2 , . . . , wn} 가 있다고 할 때, 부분 집합 내 원소들의 합이 W가 되는 부분집합을 찾는 것이다. 

 

<Example 1>

S = {w1 = 5, w2 = 6, w3 = 10, w4 = 11, w5 = 16} 일 때,  W = 21가 되는 부분집합들을 찾는 것이다.

정답은:

o {w1 , w2 , w3 } : 5 + 6 + 10 = 21

o {w1 , w5 } : 5 + 16 = 21 

o {w3 , w4 }: 10 + 11 = 21

 

부분집합의 합 문제를 푸는 해결책으로 가장 직관적인 부분은 모든 경우를 해보는 것이다. 이에 대한 시간복잡도는 O(2^n) 이라고 할 수 있다. 아래의 트리를 볼 경우, 왼쪽으로 가는 것은 w_n를 포함한다는 뜻이다. 반면 오른쪽으로 갈 경우는 w_n을 포함하지 않는다는 뜻이다. 그렇게 된다면 S 집합의 처음원소인 2를 포함한다면, 왼쪽으로, 포함하지 않는다면 오른쪽으로 간다.

이 때, 상태 저장 트리를 사용해서, 포함했을때, 부모노드의 값 + 포함된 원소를 노드에 저장한다.

 

모든 경우를 다 확인하는 방법으로 할 경우, 시간복잡도가 증가할 뿐더러, 공간 복잡도까지 증가하게 된다. 왜냐면 레벨이 1칸씩 올라가면서, 2의 제곱씩 올라가기 때문이다.

1+2+2^2+2^3...  = 2^(n+1)

Backtracking : Prune the Tree(나무 가지 치기)

• S에 있는 w값들을 non-decreasing order로 먼저 정렬한다. 왜나면, 계속 상태를 저장하면서 더해나가면서 W값이 될 수 없는 경우를 쳐내려갈 것이기 때문이다.
• Prune the Tree를 할 때, 우리는 Promising한 경우 혹은 non-Promising한 경우를 찾아내어, non-promising 할 때, 그때는 가지를 내려가지 않는 방법을 실행한다. 
  • 상태 노드에 저장된 weight + 다음에 포함시킬 원소 w_i+1 > W(우리가 찾는 부분집합의 합) 이라면 이 가지로는 더 이상 내려가지 않아도 된다.
  • 남은 원소들의 합을 total이라고 한다면, 현재 상태 노드에 저장된 weight + total < W 라면 역시 non-promising 하다. 예를 들면, S= {1,2,3,4} 라고 할때, 1을 포함하고, 2를 포함하지 않아서, 상태노드에 저장된 값은 1이라고 하자. 그렇다면 total = 3+4로 7이다. 그런데, W값이 9아라고 한다면, 1 + 7 < 9 이다 따라서 이 아래로는 어떠한 경우라도 9를 만들지 못하기에 non-promising이라고 하는 것이다.

Worst Case : Still Exponential!

S = { w1 = 1, w2 = 1, w3= 1, …. wn-1 = 1, wn = n+1 }, W = 2n 의 경우에, 역시 Pruning을 거의 할 수 없다는 것을 알 수 있다.  Worst case가 있고, 이는 모든 경우를 진행하는 것과 다를바가 없다. BUT,  많은 경우에서 Pruning the tree가 효율적이기 때문에 진행한다.

NP-complete Problems을 푸는데, 그래도 꽤 효율적일 수 있다.

NP-complete Problems들은 모든 경우를 진행한 것과 어떤 알고리즘을 수행해서 문제를 해결했을때의 최악의 경우를 비교했을때, 나아진 것을 찾을 수 없는 문제들을 말한다. 

Backtracking을 통한 문제풀이는 효율적일 수 있지만, worst case의 경우는 여전히 exponential하다.

Backtracking Procedure

상태 저장트리를 DFS를 시도한다. 만약에, 노드가 solution으로 가지 못한다면, 부모노드로 backtrack하고 다른 방법을 찾아떠나면된다.

• Non-promising node: 노드가 방문되었을때, 더이상 내려가지 않아도 되는 노드
• Promising node: 노드는 정답으로 갈 수 있게 만들어준다.
• Pruning State space tree: nonpromising이라고 할 때, 부모노드로 백트랙한다.
• Pruned State space Tree: subtree는 모두 다 방문처리되어있다.

코드 설명

let S = [3,4,5,6]
var w = 13
var result = [Int](repeating: 0, count: S.count)
var total = S.reduce(0){($0 + $1)}
var weight = 0
var index = 0

func promising(total: Int, weight: Int, index: Int) -> Bool {
    if((weight+total >= w) && ((weight == w) || (weight + S[index+1] <= w))){
        return true
    }
    return false
}

func sumOfData(total: Int, weight: Int, index: Int){
    if(promising(total: total, weight: weight, index: index)){
        if(weight == w){
            print(result)
        }
        else{
            result[index+1] = S[index+1]
            sumOfData(total: total-S[index+1], weight: weight+S[index+1], index: index+1)
            result[index+1] = 0
            sumOfData(total: total-S[index+1], weight: weight, index: index+1)
        }
    }
}

sumOfData(total: total, weight: 0, index: -1)

 사실 가장 중요한 것은 코드의 구현과 설명이지않을까 싶다..ㅎ sumofSubset 구현을 해본결과, 백준에서 백트래킹 관련 이것저것을 많이 풀어봐야 더 감이 올듯 싶다. 

 

promising 함수는 위에서 가지치기를 할수 있는지 없는지 파악하는 함수이다. 즉, 상태저장 트리에서 더 내려갈 것인가? 아닌가? 를 확정하는 함수이다. 위에서 설명했던 것처럼, weight + total이 w 보다 크거나 같을때, 내려갈 수있다. 또한 다음에 더해질 원소 S[index+1] + 현재 weight <= w 일때 내려갈 수있다. 하지만 여기서 index+1은 계속 진행될수 있기 때문에 이를 막을 조건이 하나 더 필요하다. 이때 필요한 것이 weight == w이다.

if((weight+total >= w) && ((weight == w) || (weight + S[index+1] <= w)))

weight == w가 하나만 성립하면  OR 조건이기에 index+1은 실행되지 않고, index out of range가 발생하지 않는다.

 

func SumofData가 본격적인 dfs 이다. 사실 이 문제는 tree에서 아래로 내려가기 때문에 visited를 굳이 따지지 않아도 된다. 우리가 이진트리에서 dfs할 때, visited를 쓰지 않는것과 마찬가지이다. 

result[index+1] = S[index+1]
sumOfData(total: total-S[index+1], weight: weight+S[index+1], index: index+1)
result[index+1] = 0
sumOfData(total: total-S[index+1], weight: weight, index: index+1)

이부분을 잘 살펴 보면, 이진트리의 preorder와 비슷하다는 것을 느낄 수 있다. 대신에 우리는 backtracking 위해서 result 배열을 하나 더 운용한다. 문제에 대한 해답이 여러개 있을 수 있는데, result를 하나만 운용한다는 것에 약간 의아할수 있다. 하지만 result는 계속 덮어쓰여진다는것!

만약에 {3, 4, 5, 6}에서 9를 찾는다면, 처음에 3이 promising하고 4로 갔다가 다음 5로 못하니까,, 쭉쭉  0, 0(선택안함)으로 트리를 내려가다가 6을 보고 promising 성립해서 print를 한다. 이때 사실 visited를 3 아래 자식 노드들을 다 방문했으니 3은 visited로 둬도 괜찮을것같긴하다.(내 생각만,,,) 핥츤 이때 result = [3, 0, 0 , 6]이 출력된다.

그리고 또 이제는 3까지 올라갓으니(재귀에서 3 아래의 노드를 조회? 하는 함수? 결국 result[0] = 3이 되었고, 그 다음에 들어온 재귀들은 다 빠졋다고 볼수 있다) 그러니 result[0] = 0으로 덮어씌어진 새로운 함수를 진행한다. 뭐 이런식으로 진행한다.

 

그림을 그려보자면 SOD함수는 sumof Data 함수이다.

이쪽만 콜스택만 한번 그려보자면 이런식인것이다.

이래서 어쨋건 result속 요소들은 계속 덮어쓰기 때문에 weight == w 일때 출력한번만 해주면 되는것이다!