DFS 또는 Backtracking을 하거나 하는 방식으로 문제를 풀게 되면, 완전검색(Exhaustive Search)을 고려하게 된다.
처음 문제를 보았을때 이것이 완전검색을 원하는 것인지 아니면 최적의 P를 찾아낼 수 있는지를 판단하는 것이 중요하다.
가장 쉬운 판단법은 전제사항을 유심히 보는 것이다. 대부분 문제를 보면 숫자의 범위가 0에서 100,000이상의 범위를 갖게 된다. 그런데 이 문제만 이상하게 24, 32이런식으로 매우 작은 수로 범위를 갖는 경우가 나타난다.
이럴때는 완전검색을 고려해볼 필요가있다.
문제를 하나 풀어보면서 Masking과 DP를 어떻게 활용하는지 같이 알아보자.
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
문제 내용
num으로 이루어진 Array가 주어지고, k라고 하는 파티션의 갯수가 주어진다.
해당 array가 k개의 subsets으로 이루어지고, 그 각각의 subset의 합이 모두 동일할 경우를 찾는 문제이다.
접근 방법
예를 보자.
[4,3,2,3,5,2,1]의 array를 4개의 group으로 나누고 그 sum이 동일한 값이 될까?
기본적으로 4개의 그룹으로 나누어서 같은 값이 나오려면, 주어진 모든 값의 sum/4를 했을때 나오는 값이 목표값이 된다.
위는 $ 5 = \frac{4+3+2+3+5+2+1}{ 4 } $가 된다
이제 목표값을 찾았다. 위의 array에서 5를 구성할 수 있는 subsets가 4개가 있는지 알아보면 된다.
시작부터 이렇게 접근하면 조금 어려우니까 문제를 쉽게 변경해 보겠다.
문제 변경
- 주어진 array에서 목표값 5가 있는지 확인해보자.
눈으로 보면 (4,1), (3,2), (5), (1,2,2) 등이 나타난다. 이것을 프로그램으로 찾기 위해서는
이런식으로 모든 경우의 수를 찾아가야 한다.
위의 경우는 4와 1이라고 하는 한가지 경우만을 찾았는데 만약 (2,2,1)을 찾아야 한다면 어떻게 해야할까?
현재의 선택값 이전의 선택값 그리고 이후에 선택할 선택값이 모두 visited할 때까지
- 목표값을 찾으면 true를 return
- 목표값보다 낮은 값을 찾으면, 한번더 다음 값을 search
- 목표값 보다 높으면 false를 return
한다.
라고하는 기본 Rule을 갖고 dfs를 진행해 나가야 한다.
Mask 만들기
위에서 visited에 대해서 언급을 했다.
backtracking의 경우에는
어떤 상태를 try하고 실패 (또는 성공 포함) 했을 경우 해당 상태를 원복해줘야 한다.
위의 경우를 보자면 4를 선택하고 3을 선택하면 목표값 5가 넘어가기 때문에, 3을 다시 visited하지 않았다고 상태를 원복해 줬다. 그이유는 (3,2)라고 하는 5의 목표 선택지가 있는데 visited 를 그냥 두게 되면 해당 해답지를 영원히 찾지 못하는 상태가 되기 때문이다.
이 Masking을 만들어주는 방법은 일반적으로 Array를 이용해서 처리해도 되지만 위의 backtracking이 복잡해지거나 DP처리 하기에는 적절하지 않다.
위의 그림을 DP로 어떻게 만들겠는가?
4와 3을 (index 0,1) 선택하면 false임을 어디에 어떤형태로 저장해 두지? 만약에 최대 2depth까지 밖에 없다면 2차원 array를 이용해서
dp[0][1] = false
이런식으로 만들수 있지만 몇개까지 depth가 갈지 예측할 수 없는 현 상황에서는 불가하다.
그래서 bit masking을 이용해서 이것을 쉽게 처리가능하다.
위는 모두 7자리로 이루어져 있다. visited를 0으로 기본 값을 1로 설정해 보자.
'1111111' <- 이것이 우리가 원하는 making이 될것이다.
이것은 다음과 같은 방법으로 쉽게 mask를 만들 수 있다.
- 1 << length - 1
예를 들자면 위의 경우는
let mask = (1 << nums.length) - 1;이렇게 만들 수 있다.
- (1 << nums.length) = 10000000
여기에서 1을 빼게 되면
- 1111111
7자리의 1이 만들어 지게 된다.
이 Mask를 한자리씩 지워가보자.
만약에 첫번째 num을 선택했다고 생각해보자.
index 0번인 4를 선택했음으로
- 0111111 (보기 좋게 하기 위해서 reverse를 했다. 1111110 <- 이게 맞다)
이 된다.
그리고 4는 목표값 5보다 작음으로 1을 target값으로 해서 다음 값을 찾아야 한다.
즉, 결과 mask는
- '0111110' 이고 이 결과 값은 true가 된다.
위의 내용을 코드로 만들면 아래와 같다.
let rst = dfs(mask ^ (1 << i), k - nums[i]);i가 현재 선택한 위치 index이다.
- '1111111' xor '1000000' 이면 결과 값은 '0111111'이 되게 되고
- k(5) - nums[i](4) = 1이 됨으로, 다음으로 찾아야 할 대상은 target 1이 되게 되고,
- 다음 loop에서는 0번 index는 사용하면 안된다.
if(!(mask & (1 << i))) continue;이것을 코드로 나타내면 위와 같다. i번째 mask가 false 즉 0이라면 다음 번째로 넘어가시오.
Mask에 DP 적용하기
위의 코드중에
let rst = dfs(mask ^ (1 << i), k - nums[i]);이 코드를 보면 우리는 다음과 같이 DP를 활용할 수 있다는 것을 알 수 있다.
- 현재 mask의 결과 값이 0보다 크다면 target값을 찾은 것이다.
예를 들어서
- '0111110' 은 5를 찾은 masking이고, 10진수로 76이다.
- 즉, 76은 true가 될수있고 또한
- '0111111'도 77도 true가 될 수 있다. (보기 좋게 하기 위해서 reverse를 했다. 1111110 <- 이게 맞다 126이다)
이를 이용하면 어떤 mask에 목표값이 동일하게 들어오는 경우 더이상 뒤를 확인할 필요 없이, dp에서 결과 값을 보내주면 되게 된다.
위의 것을 모두 적용시킨 코드는 아래와 같다.
var findSubset = function(nums, k) {
let mask = (1 << nums.length) - 1;
let dp = new Map();
return dfs(mask, k);
function dfs(mask, k) {
if(dp.has(mask)) return dp.get(mask);
for (let i = 0; i < nums.length; i++) {
if(!(mask & (1 << i))) continue;
if(nums[i] === k) {
return mask ^ (1 << i);
} else {
if(0 < k - nums[i]){
let rst = dfs(mask ^ (1 << i), k - nums[i]);
if(0 <= rst) {
dp.set(mask, rst);
return rst;
}
}
}
}
dp.set(mask, -1);
return -1;
}
};이렇게 하면 backtracking에서 사용한 visited를 다시 살려주는 행위를 할 필요도 없고, dp를 적용하는것도 매우 쉽게 가능하다. 결국은 10진수 값에 결과를 넣는 것이기 때문이다.
- mask와 dp를 만들어준다
- dfs에서 visited가 되지 않은 한 자리를 선택하고 dfs를 다시 try한다
- k값이 0이거나 target보다 커지면 dfs를 종료한다.
원래 문제로
위에서 target값을 찾는 방법을 코드로 만들었다.
원래 문제는 동일한 값을 갖는 group이 k번 나오는지를 확인하는게 목표였다.
for (let i = 0; i < k; i++) {
mask = findSubset(nums, findNum, mask);
// console.log(findNum, mask.toString(2));
if(mask < 0) return false;
}k번의 subsets을 찾기만 한다면 결과는 true가 될 것이다.
주의 할 것은 findSubset은 한번을 찾는 것이기 때문에 기 활용된 mask를 visited상태로 유지해서 다음 findSubset에서 재활용 해줘야 한다는 것이다.
그래서 입력값에 mask가 들어가게 된다.
마지막으로 위 프로그램에 단점이 있는데, 왼쪽에서부터 target을 만들때까지 모두 visited를 한다는 것이다.
[1,1,1,1,2,2,2,2] k = 3
이런 문제가 주어지게 되면, 1,1,1 이렇게 3개를 미리 사용해 버림으로써 뒤에 (2,1),(2,1),(2,1)의 기회를 빼았게 된다.
그래서 Group의 크기를 최대한 작게 선택하게 하기 위해서 역 sorting처리가 필요하다.
[2,2,2,2,1,1,1,1] k = 3
이것을 최종 코드로 나타내면 아래와 같다.
var canPartitionKSubsets = function(nums, k) {
let findNum = nums.reduce((cum, cur) => cum + cur) / k;
if(findNum === 0 || findNum % 1 !== 0) return false;
let mask = (1 << nums.length) - 1;
nums.sort((a,b)=> b-a);
for (let i = 0; i < k; i++) {
mask = findSubset(nums, findNum, mask);
if(mask < 0) return false;
}
return true;
};
var findSubset = function(nums, k, mask) {
let dp = new Map();
return dfs(mask, k);
function dfs(mask, k) {
if(dp.has(mask)) return dp.get(mask);
for (let i = 0; i < nums.length; i++) {
if(!(mask & (1 << i))) continue;
if(nums[i] === k) {
return mask ^ (1 << i);
} else {
if(0 < k - nums[i]){
let rst = dfs(mask ^ (1 << i), k - nums[i]);
if(0 <= rst) {
dp.set(mask, rst);
return rst;
}
}
}
}
dp.set(mask, -1);
return -1;
}
};시간복잡도를 findSubset을 통해서 알아보자.
'1111111' N개의 bit가 있을때 우리는 매 loop마다 2가지의 선택이 가능하다. 선택 또는 선택하지 않음 그럼으로 이것을 숫자로 나타내면 2이고 매 loop마다 2의 선택이 생김으로 $ O(2^N) $이 된다.
이것을 조금더 수학적으로 생각해 보자.
'0111111' 여기서 첫번째 숫자를 선택할 수 있다. 일단 한번 선택하면 이 첫번째 숫자로 인해서 target이 만들어질 수 있는 모든 경우의 수를 search하게 된다. (보기좋게 하기 위해서 첫번째를 맨 왼쪽이라고 했다. 프로그램 상으로는 '1111110'이 된다)
'0111110' 그리고 마지막 1을 선택하면서 target을 찾아 냈다.
처음 1과 마지막 1까지의 사이에 그중간에서 우리는 다음과 같은 선택들을 했다.
'0011110'
'0101110'
'0000110'
....
즉, 모든 case를 선택해보고 또는 선택하지 않아 보면서 target이 있는지 모든 경우를 찾은 것이다.
1이 선택할 수 있는 모든 경우는 선택 또는 선택하지 않음 2가지 선택지 임으로 하나의 target을 찾기위해서 최대
$ O(2^N) $ 의 시간복잡도를 활용하게 된다.
마지막으로 Partition의 갯수 k만큼 findsubset을 하게 됨으로
$ O(k * 2^N) $
이 최종 시간 복잡도가 된다.
오늘 leet code post에 잘 정리된 내용이 있어서 이곳에 link한다
이하는 Masking을 사용하는 문제 리스트
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
https://leetcode.com/problems/matchsticks-to-square/
https://leetcode.com/problems/beautiful-arrangement/
https://leetcode.com/problems/shortest-path-visiting-all-nodes/
https://leetcode.com/problems/find-the-shortest-superstring/
https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/
https://leetcode.com/problems/parallel-courses-ii/
ttps://leetcode.com/problems/distribute-repeating-integers/
https://leetcode.com/problems/maximize-grid-happiness/
https://leetcode.com/problems/minimum-incompatibility/
https://leetcode.com/problems/k-similar-strings/
https://leetcode.com/problems/maximize-score-after-n-operations/
'Problem Solving' 카테고리의 다른 글
| Arithmetic Slices (0) | 2021.09.22 |
|---|---|
| Shortest Path Visiting All Nodes (0) | 2021.09.16 |
| Jump Game II (0) | 2021.08.30 |
| Sparse Matrix Multiplication (0) | 2021.08.17 |
| Javascript 32bit 이상 Number&Integer 계산하기 (BigInt) (1) | 2021.08.14 |