08. 재귀함수와 완전탐색(DFS:깊이우선탐색)
개념 정리
재귀함수(Recursion)
재귀함수란 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다. 조건으로 그 재귀를 빠져나오도록 설계해야 무한 루프에 빠지지 않는다.
장점
변수를 여럿 만들 필요가 없다. → 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드로 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있다.
단점
지속해서 함수를 호출하게 되면서 지역변수, 매개변수, 반환 값을 모두 process stack에 저장해야 한다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다. 이를 보완하기 위해 Tail Call Recursion이라는 것이 있다.
Tail Call Recursion
아래와 같이 함수에 담에서 호출하게 되면 Process Stack 에 쌓여 메모리를 잡아먹는 이슈를 보완할 수 있다.
// Basic Recursion
function factorial(n: number): number {
if (n === 1) return 1;
return n * factorial(n - 1);
}
// Tail Recursion
function factorial(n: number, total: number): number {
if (n === 1) return 1;
return factorial(n - 1, n * total);
}
DFS(Depth-First Search) - 깊이우선탐색
DFS는 깊이 우선 탐색이며 깊이를 먼저 탐색한다. 2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 깊이 탐색을 통해 방문하여 모든 노드를 탐색하는 방법이다. 조금 더 쉽게 설명하면, 걸어 가다가 왼쪽과 오른쪽 선택지가 지속적으로 나올 때 계속 하나의 방향만 선택하여 끝을 본 후에 끝에서부터 하나씩 돌아오면서 끝을 찍고 오는 개념이다. 따라서 재귀함수를 기본적으로 이해를 해야 한다.
DFS - 선형구조
선형구조란 여러 개의 데이터가 있을 때, 하나의 데이터 뒤에 하나의 데이터가 존재하는 것이다. 리스트 같이 index값을 순차적으로 구성된 것이 선형구조이다. 쉽게 말해서 배열에 for문으로 완전검색하여 풀수 있는 문제를 선형구조라고 할 수 있다. 이와 반대로 단순한 for문을 통해 데이터를 탐색할 수 없는 구조가 비선형구조라고 할 수 있다. (추후에 다룰 예정)
순열(Permutation) & 중복 순열
순열 : 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음)
중복 순열 : 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음)
계승(Factorial)
팩토리얼 : 서로 다른 n개를 나열하는 경우의 수를 의미합니다. 기호로는 n! 이렇게 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱합니다.
조합(Combination) 중복 조합
조합 : 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)
중복 조합 : 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)
메모제이션(Memoization)
기억되어야 할 것이라는 뜻의 라틴어에서 파생된 단어로, 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법(DP; Dynamic Programming)의 핵심이 되는 기술입니다.
문제 풀이
Ch.08 - 01. 재귀함수와 스택프레임(중요)
const solution = (n: number): void => {
const DFS = (L: number): void => {
if (L === 0) return;
else {
DFS(L - 1);
console.log(L);
}
};
DFS(n);
};
Ch.08 - 02. 이진수 출력(재귀)
const solution = (n: number): string => {
let answer: string = "";
const DFS = (L: number): void => {
if (0 < L) {
DFS(Math.floor(L / 2));
answer += L % 2;
} else return;
};
DFS(n);
return answer;
};
Ch.08 - 03. 이진트리순회(DFS: 깊이우선탐색)
const solution = (n: number): void => {
const DFS = (v: number): void => {
if (v <= 7) {
console.log(v);
DFS(v * 2);
DFS(v * 2 + 1);
} else return;
};
DFS(n);
};
Ch.08 - 04. 부분집합 구하기(이진트리 DFS)
const solution = (n: number): Array<string> => {
const answer: Array<string> = [];
const checkList: Array<number> = Array.from({ length: n + 1 }, () => null);
const DFS = (v: number): void => {
if (v === n + 1) {
const temp = checkList.filter((value) => value).join(" ");
if (temp) answer.push(temp);
} else {
checkList[v] = v;
DFS(v + 1);
checkList[v] = null;
DFS(v + 1);
}
};
DFS(1);
return answer;
};
Ch.08 - 05. 합이 같은 부분집합(이진트리 DFS)
const solution = (arr: Array<number>): string => {
let answer: string = "NO";
const goalSum: number = arr.reduce((acc, cur) => acc + cur, 0) / 2;
const DFS = (L: number, sum: number): void => {
if (answer === "YES") return;
if (L === 6) {
if (sum === goalSum) answer = "YES";
} else {
DFS(L + 1, sum + arr[L]);
DFS(L + 1, sum);
}
};
DFS(0, 0);
return answer;
};
Ch.08 - 06. 바둑이 승차(이진트리 DFS)
const solution = (maxWeight: number, dogWeightList: Array<number>): number => {
let answer = 0;
(function DFS(idx: number, sum: number): void {
if (maxWeight < sum) return;
if (dogWeightList.length <= idx) {
answer = Math.max(answer, sum);
} else {
DFS(idx + 1, sum + dogWeightList[idx]);
DFS(idx + 1, sum);
}
})(0, 0);
return answer;
};
Ch.08 - 07. 최대점수 구하기(이진트리 DFS)
const solution = (
limitTime: number,
tableList: Array<Array<number>>
): number => {
let bestScore = 0;
const tableListLength: number = tableList.length;
(function DFS(L: number, sumScore: number, time: number): void {
if (limitTime < time) return;
if (tableListLength <= L) {
bestScore = Math.max(bestScore, sumScore);
} else {
const [point, estimatedTime] = tableList[L];
DFS(L + 1, sumScore + point, time + estimatedTime);
DFS(L + 1, sumScore, time);
}
})(0, 0, 0);
return bestScore;
};
Ch.08 - 08. 중복순열(다중 for문과 재귀의 차이점)
const solution = (n: number, m: number): number => {
let answer: Array<Array<number>> = [];
const tmp: Array<number> = [];
(function DFS(L: number): void {
if (L === m) {
console.log(tmp);
answer.push(tmp);
} else {
for (let i = 1; i <= n; i++) {
tmp[L] = i;
DFS(L + 1);
}
}
})(0);
return answer.length;
};
Ch.08 - 09. 동전교환(DFS-Cut Edge Tech)
const solution = (coinLsit: Array<number>, change: number): number => {
let answer: number = Number.MAX_SAFE_INTEGER;
(function DFS(L: number, sumMoney: number): void {
if (change < sumMoney) return;
if (change === sumMoney) {
answer = Math.min(answer, L);
} else {
for (const coin of coinLsit) {
DFS(L + 1, sumMoney + coin);
}
}
})(0, 0);
return answer;
};
Ch.08 - 10. 순열 구하기
const solution = (n: number, arr: Array<number>): number => {
let answer: Array<Array<number>> = [];
const tmp: Array<number> = Array.from({ length: n }, () => 0);
const tmpCheckList: Array<number> = Array.from(
{ length: arr.length },
() => 0
);
(function DFS(L: number): void {
if (n === L) {
console.log(tmp);
answer.push(tmp);
} else {
for (let i = 0; i < arr.length; i++) {
if (tmpCheckList[i] === 0) {
tmpCheckList[i] = 1;
tmp[L] = arr[i];
DFS(L + 1);
tmpCheckList[i] = 0;
}
}
}
})(0);
return answer.length;
};
console.log(solution(2, [3, 6, 9]));
Ch.08 - 11. 팩토리얼
const solution = (n: number): number => {
return 1 < n ? n * solution(n - 1) : n;
};
console.log(solution(5));
Ch.08 - 12. 조합수(메모이제이션)
const solution = (n: number, r: number): number => {
const cacheArr: Array<Array<number>> = Array.from({ length: n + 1 }, () =>
Array.from({ length: r + 1 }, () => 0)
);
return (function DFS(tempN: number, tempR: number): number {
if (cacheArr[tempN][tempR]) return cacheArr[tempN][tempR];
if (tempN === tempR || tempR === 0) return 1;
else {
const tempValue = DFS(tempN - 1, tempR - 1) + DFS(tempN - 1, tempR);
cacheArr[tempN][tempR] = tempValue;
return tempValue;
}
})(n, r);
};
Ch.08 - 13. 수열 추측하기(순열, 이항계수 응용)
const solution = (n: number, m: number): Array<number> => {
const answer: Array<number> = [];
const cacheArr: Array<number> = Array.from({ length: 11 }, () => 0);
const checkArr: Array<number> = Array.from({ length: n + 1 }, () => 0);
const tempAnswer: Array<number> = Array.from({ length: n }, () => 0);
const combiResult: Array<number> = Array.from({ length: n }, () => 0);
function combi(n: number, r: number): number {
if (cacheArr[n][r]) return cacheArr[n][r];
if (n === r || r === 0) return 1;
else return (cacheArr[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
}
for (let i = 0; i < n; i++) combiResult[i] = combi(n - 1, i);
(function DFS(L: number, sum: number) {
if (answer.length) return;
if (L === n && sum === m) {
answer.push(...tempAnswer);
} else {
for (let i = 1; i <= n; i++) {
if (checkArr[i] === 0) {
checkArr[i] = 1;
tempAnswer[L] = i;
DFS(L + 1, sum + tempAnswer[L] * combiResult[L]);
checkArr[i] = 0;
}
}
}
})(0, 0);
return answer;
};
Ch.08 - 14. 조합 구하기(중요)
const solution = (n: number, m: number): number => {
const answer: Array<Array<number>> = [];
const tempArr: Array<number> = Array.from({ length: m }, () => 0);
(function DFS(L: number, idx: number) {
if (L === m) answer.push([...tempArr]);
else {
for (let i = idx; i <= n; i++) {
tempArr[L] = i;
DFS(L + 1, i + 1);
}
}
})(0, 1);
return answer.length;
};
Ch.08 - 15. 수들의 조합
const solution = (n: number, arr: Array<number>, m: number): number => {
let answer: number = 0;
(function DFS(L: number, idx: number, sum: number): void {
if (L === n) {
if (sum % m) return;
answer++;
} else {
for (let i = idx; i < arr.length; i++) {
DFS(L + 1, i + 1, sum + arr[i]);
}
}
})(0, 0, 0);
return answer;
};