따로 정해진 이름이 있는 알고리즘이라기 보단 문제를 접해보니 비슷한 패턴이 보여서 정리해두려고 글을 쓴다.
처음에 이 글을 쓸 때 명확하지 않았던 개념이 시간이 지나 이해도가 높아져서 추가 설명을 붙이려한다.
이 패턴 역시 백트래킹의 일종이다. dfs로 모든 경우를 탐색하면서 원하는 부분은 check 또는 값을 누적하는 것이다.
// 부분 집합 구하기
function solution(n) {
let answer = [];
let check = Array.from({ length: n + 1 }, () => 0); //[0,0,0,0]
function DFS(L) {
if (L === n + 1) {
let tmp = "";
for (let i = 1; i <= n; i++) {
if (check[i] === 1) tmp += i + " ";
}
if (tmp.length > 0) answer.push(tmp.trim());
} else {
check[L] = 1;
DFS(L + 1); //부분집합에 참여.
check[L] = 0;
DFS(L + 1); // 부분집합에 참여하지 않음.
}
}
DFS(1);
return answer;
}
//[ '1 2 3', '1 2', '1 3', '1', '2 3', '2', '3' ]
기본 패턴이다. 내부함수에 Level 변수를 이용해 깊이 탐색을 하는 방식이고 참여하는 경우와 참여하지 않는 케이스를 나눌 때 사용하면 쉽게 문제를 풀 수 있다.
// 합이 같은 부분 집합
function solution(arr) {
let answer = "NO",
flag = 0;
let total = arr.reduce((a, b) => a + b, 0);
let n = arr.length;
function DFS(L, sum) {
if (flag) return;
if (L === n) {
if (total - sum === sum) {
answer = "YES";
flag = 1; // 깃발, 더 돌 필요는 없으니까.
}
} else {
DFS(L + 1, sum + arr[L]);
DFS(L + 1, sum);
}
}
DFS(0, 0);
return answer;
}
앞 문제와 같은 패턴이 보이는가?
// DFS 내부의 조건문
if (L === n) {
// 리턴 또는 수행해야하는 작업
} else {
// 재귀 호출
}
}
}
// DFS 최초의 호출
DFS();
이런 유형의 특징은 일단 탐색을 다하기는 해야 한다는 점이다. 문제마다 따로 조건이 있어서 답이 다 다르고 하는 것이지만 일단 그 답을 찾기전까지는 계속 탐색을 해나간다는 소리이다.
// 최대값을 구하는 문제 limit가 주어지고 거기에 가장 가까운 값을 구한다.
function solution(c, arr) {
let answer = Number.MIN_SAFE_INTEGER;
let n = arr.length;
function DFS(L, sum) {
if (sum > c) return;
if (L === n) {
// 최대레벨
answer = Math.max(answer, sum);
} else {
DFS(L + 1, sum + arr[L]);
DFS(L + 1, sum);
}
}
DFS(0, 0);
return answer;
}
let arr = [81, 58, 42, 33, 61];
// 242
포함하는지 하지 않는지를 생각해야되는 문제에 적용해보자