반응형 자료구조알고리즘1 [알고리즘] 백트래킹 문제 - Sum of Subsets 백트래킹 문제 - Sum of Subsets 백트래킹(Backtracking) 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻한다. 즉, 탐색하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 백트래킹이라는 이름이 붙었다. Sum of Subsets 백트래킹을 사용하여 해결할 수 있는 문제 중 Sum of Subsets이 있다. Sum of Subsets은 집합 w의 부분집합 중 그 합이 숫자 K와 같은 부분 집합들을 찾는 문제다. 이때, 집합에 음의 값과 중복 값은 없다고 가정한다. 예제를 통해 문제를 이해해보자. 집합 w는 w₁ = 2, w₂ = 10, w₃ = 13, w₄ = 17, w₅ = 22, w₆ = 42 이다. K = 52일때, K와 값이 같은 집합 w의 부분 .. 2021. 1. 1. 이전 1 다음 반응형
