수학 문제로 풀 때는 순열과 조합은 할만했는데,
컴퓨터한테 시키는 것은.. 쉽지 않다..
알고리즘을 할 때마다 느끼는 것은 기존 수학 + 활용하는 방법이 포함되어서
실용법을 느껴 흥미롭지만 아직 익숙하지 않아서 어렵다.
그래서 좀 더 익숙해지고 기억에 남기고자 정리한다.
중복순열
function solution(n, m) {
let answer = [];
let tmp = Array.from({ length: m }, () => 0);
function DFS(L) {
//틀림
if (L === m) {
answer.push(tmp.slice());
} else {
for (let i = 1; i <= n; i++) {
tmp[L] = i;
DFS(L + 1);
}
}
}
DFS(0);
for (let i = 0; i < answer.length; i++) {
console.log(answer[i]);
}
}
solution(4, 2);
중복을 허락하여서 순열을 만드는 것이다.
1부터 N까지 번호가 적힌 구슬을 고르고, 중복을 허락하여 M번 뽑는 것이다.
N = 4, M = 2
재귀를 활용하여야한다. 먼저
for문을 작성하고, tmp에 값을 넣어주고 재귀에 넣어준다.
그러면 tmp[L]번째에 이미 값이 들어간 상태로 재귀가 들어간다.
그러고 나서 for문이 돌아가면,
그다음 i+1번째에서는 tmp[L]에는 i+1이 들어가고 또 재귀가 들어가면서,
중복 순열에 첫째자리가 바뀌는 방식으로 흘러간다.
이러한 방식을 첫째, 둘째 이어가면서 중복순열을 만든다.
동전교환
가장 적은 수의 동전으로 교환해주려면 어떻게 해야하는지 구하는 알고리즘이다.
let arr = [1, 2, 5];
function solution(m, arr) {
let n = arr.length;
let answer = Number.MAX_SAFE_INTEGER;
function DFS(L, sum) {
if (sum > m) return;
if (answer <= n) return;
if (m === sum) {
answer = Math.min(answer, L);
} else {
for (let i = 0; i < n; i++) {
DFS(L + 1, sum + arr[i]);
}
}
}
DFS(0, 0);
return answer;
}
console.log(solution(15, arr));
먼저 DFS 재귀를 활용해서 1번째 인자에는 index, 2번째 인자에는 sum값을 넣어준다.
그리고 함수에 들어가면 for문에서 횟수를 올려주고, 횟수 계산한 값만큼의 수를 넣어준다.
반복을 통해 sum값과 같아지면 출력한다.
그런데 sum이 이미 넘었거나, answer(최솟값)에 들어간 갯수보다 크다면 return으로 시간복잡도를 줄여주는 방법으로 푼다.
순열 구하기
순열이란 순서가 있는 열이라는 뜻이다.
한번 사용한 것은 다시 사용할 수 없고 한번씩만 사용 가능하다.
let arr = [3, 6, 9, 5];
function solution(m, arr) {
let n = arr.length;
let ch = Array.from({ length: n }, () => 0); // 체크
let tmp = Array.from({ length: m }, () => 0); // 담을 공간
let answer = [];
function DFS(L) {
if (L === m) {
answer.push(tmp.slice());
} else {
for (let i = 0; i < n; i++) {
if (ch[i] === 0) {
ch[i] = 1;
tmp[L] = arr[i];
DFS(L + 1);
ch[i] = 0;
}
}
}
}
DFS(0);
return answer;
}
console.log(solution(2, arr));
문제에서는 2자리수와, arr이라는 배열이 주어졌다.
먼저 ch는 체킹하는 공간이며,
tmp는 해당 순열을 담을 공간이다.
DFS를 통해 재귀를 돌리면, for문과 만나는데
먼저 체킹이 되어있는지 확인하고 안되어있다면 사용한다.
그러고 tmp에 넣어주고, 재귀에 넣어준다
이후 첫째 자리수에 다른 수를 넣어주는 경우를 고려하기 위해
체킹을 지워주고, for문이 돌아가면 첫째자리수에 다른수가 들어오는 방식으로
모든 경우의 수를 고려해준다.
깊은 복사를 위해 slice를 해준다. 만약에 slice를 안해주면 주소를 복사하기때문에
같은 값으로 다 바뀐다. 주의하자
팩토리얼
function solution(N) {
let answer;
function DFS(n) {
if (n === 1) {
return 1;
} else {
return n * DFS(n - 1);
}
}
answer = DFS(N);
return answer;
}
console.log(solution(5));
재귀를 통해서 n값을 넣고 1씩 줄어든 재귀를 돌리는 방식으로 해결한다.
조합(메모이제이션)
function solution(N, R) {
let dy = Array.from(Array(N + 1), () => Array(R + 1).fill(0)); //최대 범위 중요
function DFS(n, r) {
if (dy[n][r]) return dy[n][r];
if (n === r || r === 0) {
return 1;
} else {
return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
}
}
return DFS(N, R);
}
console.log(solution(5, 3));
이 문제는 메모이제이션 없이 풀 수 있지만, 시간 복잡도를 고려해서 메모이제이션으로 기록하여서 풀면 시간이 상당히 줄어들기 때문에 메모이제이션을 사용하는 것이 좋다.
먼저 dy라는 공간을 만들어준다. 여기선 2차원 배열로
N C R 을 캐싱하여서 빠르게 처리해준다.
주의할 점은 dy가 n개를 만들면 dy[n]이 존재하지 않기때문에, n+1로 작성해주어야한다.
수열 추측하기
function solution(N, SUM) {
let dy = Array.from(Array(N + 1), () => Array(N + 1).fill(0));
let b = Array.from({ length: N }, () => 0);
let answer;
let ch = Array.from({ length: N + 1 }, () => 0);
let a = Array.from({ length: N }, () => 0);
function combi(n, r) {
// nCr의 n을 고정하고 r의 값들을 차례대로 구함
//조합 메모이제이션
if (dy[n][r] > 0) return dy[n][r];
if (n === r || r === 0) {
return 1;
} else {
return (dy[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
}
}
let flag = 0;
function DFS(n, sum) {
//순열
if (flag) return;
if (n === N && sum === SUM) {
answer = a.slice();
flag = 1;
} else {
for (let i = 1; i <= N; i++) {
if (ch[i] === 0) {
ch[i] = 1;
a[n] = i;
DFS(n + 1, sum + i * b[n]);
ch[i] = 0;
}
}
}
}
for (let i = 0; i < N; i++) {
b[i] = combi(N - 1, i); // 4개면 3C0부터 시작임
}
DFS(0, 0); //주의
return answer;
}
console.log(solution(4, 16));
가장 어려웠던 문제다. 먼저 조합을 메모이제이션해서 기록하고, 이후에 메모이제이션된 조합을 활용한다.
순열로 주어진 수를 넣어줄때마다 해당 index에 맞춘 조합을 곱해주어서 sum에 넣어주고
목표한 sum에 도달하면 뱉는다.
말로 간단히 요약되었지만, n번째 순서에서 n번째 조합을 곱해준다는 개념을 적용하고
생각을 정리하는 것이 복잡하였다.
조합 구하기
function solution(N, M) {
let tmp = Array.from({ length: M }, () => 0);
let answer = [];
function DFS(n, m) {
if (n === M) {
answer.push(tmp.slice());
} else {
for (let i = m; i <= N; i++) {
tmp[n] = i;
DFS(n + 1, i + 1);
}
}
}
DFS(0, 1); //첫번째 인자는 횟수 두번째 인자는 시작하는 수를 의미함
for (let i = 0; i < answer.length; i++) {
console.log(answer[i]);
}
}
solution(4, 2);
조합을 구하는 방법이었다.
인상 깊었던 것은 처음 1부터 카운팅하니 DFS 두번째 인자에 1을 넘겨주는 것이 인상적이었다.
그리고 그 이후에 2번째 인자에 i+1을 넣어줌으로서 그 수보다 작은 수를 사용하지 못하게하고,
큰 수들만 사용하는 것이 인상깊었다.
수들의 조합
let arr = [2, 4, 5, 8, 12];
function solution(N, M, ARR, SUM) {
let answer = 0;
let tmp = Array.from({ length: M }, () => 0);
function DFS(l, n, s) {
if (l === M) {
if (s % SUM === 0) answer++;
console.log(s, tmp);
} else {
for (let i = n; i < N; i++) {
//0부터 시작해서 N을 포함 x
tmp[l] = ARR[i];
DFS(l + 1, i + 1, s + ARR[i]);
}
}
}
DFS(0, 0, 0); //level, index, sum
console.log(answer);
}
solution(5, 3, arr, 6); //정수의 갯수, 뽑는 횟수, 배열, 합
//조합의 총 합이 6으로 나눠지는 수의 갯수를 구하여라!
조합을 구하고 합이 6의 배수인지 확인하고 체킹하는 문제이다.
if문을 2개를 하나로 할 수 있었지만, tmp값을 확인하기 위해서 2개로 작성하였고,
위 조합 문제와 다르게 2번째인자에는 숫자가 아니라 배열의index 값을 전달했다
그리고 습관적으로 풀면서 마지막에 tmp 의 합을 구하는 방식으로 접근하려하였는데,
3번째 인자를 만들어서 전달하는게 더 직관적이고 좋은 코드였다.
(parameter를 활용하자)
마무리
여지껏 강의를 들으면서 재귀 파트가 가장 어려웠다.
(가장 부족했다)
재귀를 활용하여서 sum값을 활용하거나 index 및 숫자를 넘겨서 카운팅하는 등 다양한 방법들이 있었는데 그 중 핵심은 parameter을 통한 관리였다.
parameter를 통해 다양한 방법들을 적용하여서 하나의 기준점으로 사용하였고,
이러한 방식이 인상적이었다.
이외에도 메모이제이션을 활용하여 캐싱하는 방법도 인상적이었다.
