아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[재귀함수, DFS, BFS]
재귀함수를 이용한 이진수 출력
10진수 N이 입력되었을 시, 재귀를 이용하여 2진수로 변환하여라
📌 내가 푼 방법
function solution(N) {
if(N === 0) {
return '';
}
else {
return solution(parseInt(N/2), 10) + String(N%2);
}
}
console.log(solution(11));재귀로 리턴을 해가면서 풂.
📌 강사님 방법
function solution(n) {
let answer = 0, tmp = [];
function DFS(n) {
if(n===0) return;
else {
DFS(parseInt(n/2));
tmp.push(n%2);
}
}
DFS(n);
for(let i =0; i<tmp.length; i++) {
answer=answer*10+tmp[i];
}
return answer
}
console.log(solution(11));재귀를 통해 나눈 값을 tmp값에 넣고 다시 for문을 통해 answer에 곱하기 10을 통해 숫자 자리를 맞추면서 값을 넣어줌
이진트리 순회(깊이우선탐색: DFS)
이진트리의 전위, 중위, 후위 순회를 하여라
📌 내가 푼 방법
function solution(n) {
let answer = "";
function DFS(v) {
if(v > 7) return;
else {
// answer+=(v+'');
DFS(v*2);
// answer+=(v+'');
DFS(v*2+1);
answer+=(v+'');
}
}
DFS(n);
return answer;
}
console.log(solution(1));📌 강사님 방법
코드 같음
부분집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(n){
let answer=[];
let part=[];
function DFS(L){
if(L===n+1){
if(part.length!==0) answer.push(part.slice());
}
else{
part.push(L);
DFS(L+1);
part.pop();
DFS(L+1);
}
}
DFS(1);
return answer;
}
console.log(solution(3));함수가 실행되는 순서를 스택과 트리로 그려보면 왼쪽으로 가면 그 숫자를 포함하는 숫자이고 오른쪽으로 가면 그 숫자를 포함하지 않는것! (트리로 보면 그 부분에 있는 값을 사용하겠다, 사용하지 않겠다라고 생각해서 풀면됨)
재귀 안에선 if~else문 무조건!!!
합이 같은 부분집합
N개의 원소로 구성된 자연수 집합이 주어지고, 두 개의 부분집합으로 나눌 때, 원소의 합이 서로 같은 경우가 존재하면 "YES"아니면 "NO"를 출력하여라
📌 내가 푼 방법
function solution(nums) {
let answer = "NO";
let n = nums.length-1;
let part = []
function DFS(N) {
if(N > n) {
if(part.length !== 0) {
let comp1 = part.slice();
let comp2 = nums.filter(x => !comp1.includes(x));
let sum1 = 0;
let sum2 = 0;
for(let c1 of comp1) {
sum1 += c1;
}
for(let c2 of comp2) {
sum2 += c2;
}
if(sum1 === sum2) {
answer = "YES";
}
}
}
else {
part.push(nums[N]);
DFS(N+1);
part.pop();
DFS(N+1);
}
}
DFS(0);
return answer;
}
console.log(solution([3, 9, 11, 13]));위의 부분집합 구하기와 같이 만들 수 있는 집합을 모두 세어서 반대되는 집합을 만들어 그 집합과 만든 집합의 sum을 비교하였다.
📌 강사님 방법
function solution(nums) {
let answer = "NO";
flag = false;
let total = nums.reduce((a, b) => a + b, 0); // 넘어온 nums의 총합 순회하면서 이 total값의 반이되는 sum이 있으면 정답!
let N = nums.length;
function DFS(L, sum) {
if (flag) return; // flag가 true되면 찾았다는 의미이므로 나머지 스택에 있는 함수들을 다 처음에 종료시켜버림
if (L === N) {
if ((total - sum) === sum) {
answer = "YES";
flag = true;
}
} else {
DFS(L + 1, sum + nums[L]); // 매개변수활용을 하여 시간복잡도를 줄이기
DFS(L + 1, sum);
}
}
DFS(0, 0);
return answer;
}
console.log(solution([3, 9, 11, 13]));그 원소를 사용할 것 인지, 사용하지 않을 것인지 트리로 생각을 해보면 된다. 그리고 sum을 활용하여 전체합을 같이 더하면서 내려가기!!
바둑이 승차(DFS)
바둑이의 무게가 배열로 주어지고 최대로 버틸 수 있는 무게 C가 주어졌을 때, 트럭에 태울 수 있는 가장 무거운 무게를 구하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(nums, c) {
let answer = 0;
let total = nums.reduce((a, b) => a+b, 0);
let N = nums.length;
function DFS(L, sum, tsum) {
if(sum > c) return;
if(sum+(total-tsum) < answer) return;
if(L === N) {
answer = Math.max(answer, sum);
} else {
DFS(L+1, sum + nums[L], tsum+nums[L]);
DFS(L+1, sum, tsum+nums[L]);
}
}
DFS(0, 0, 0);
return answer;
}
console.log(solution([34, 56, 55, 67, 33, 76, 63, 43], 379));위의 문제와 마찬가지로 DFS로 원소들을 돌면서 이 원소를 포함시킬 것인지 포함시키지 않을 것인지를 생각하면서 돌고, 그 중 무게 C를 넘지 않는 최대값을 찾아내면 된다.
sum > c로 그 아래 행을 실행시키지 않고 커트시켜주며, tsum을 이용해 더해주지 않은 것들 것 까지 생각을 해서 미리 커트를 생각해준다.
(total-tsum)<-- 앞으로 검사를 받아야할 나머지 바둑이들의 값들을 sum에다가 더해주었는데 불구하고 answer보다 작으면 굳이 해줄 필요없으므로 return으로 커팅!
최대점수 구하기(DFS)
풀었을 때 얻는 점수와 걸리는 시간이 nums 배열로 주어진다. 제한시간안에 M안에 얻을 수 있는 최대점수를 반환하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(nums, m) {
let answer = 0;
let N = nums.length;
function DFS(L, time, sum) {
if(time > m) return;
if(L === N) {
answer = Math.max(answer, sum);
} else {
DFS(L+1, time + nums[L][1], sum+nums[L][0]);
DFS(L+1, time, sum);
}
}
DFS(0, 0, 0);
return answer;
}
console.log(solution([[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]], 20));마찬가지로 문제를 푼다 or 풀지 않는다 를 정해서 모든 경우의 수를 생각해서 풀면됨
또한 tsum을 통해서 위의 문제와 같이 커팅을 할 수 있음.
if(sum+(total-tsum) < answer) return; // 매개변수 4개해서 tsum추가하고 total을 위에 계산해두어서 사용하면 됨
중복순열 구하기
1부터 N까지 번호가 적힌 구슬을 중복을 허락해서 M번을 뽑아 만들 수 있는 경우의수를 출력하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(n, m) {
let answer = [], tmp = [];
function DFS(L) {
if (L === m) {
answer.push(tmp.slice());
} else {
for(let i = 1; i<=n; i++) { // i가 뽑는 숫자, n번을 돌음
tmp.push(i);
DFS(L+1); // 종료지점을 위해
tmp.pop();
}
}
}
DFS(0);
return answer;
}
console.log(solution(3, 2));중복 순열을 구하기 위해 i를 1부터 n까지 돌려서 뽑고 DFS로 순회를 한다.
중복순열이 아닌 경우
function solution(n, m) {
let answer = [], tmp = [];
let ch = Array.from({length: n+1}, () => 0);
function DFS(L) {
if (L === m) {
answer.push(tmp.slice());
} else {
for(let i = 1; i<=n; i++) { // i가 뽑는 숫자, n번을 돌음
if(ch[i] === 0) {
ch[i] = 1;
tmp.push(i);
DFS(L+1); // 종료지점을 위해
tmp.pop();
ch[i] = 0;
}
}
}
}
DFS(0);
return answer;
}
console.log(solution(3, 2));다음과 같이 중복인지 체크를 해주는 변수 배열을 만들어 체크하면서 돌면 됨
순열 구하기
10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하여라.
📌 내가 푼 방법
📌 강사님 방법
function solution(nums, m) {
let answer = [], tmp = [];
let ch = Array.from({length: nums.length}, () => 0);
function DFS(L) {
if (L === m) {
answer.push(tmp.slice());
} else {
for(let i = 0; i<nums.length; i++) { // i가 뽑는 숫자, n번을 돌음
if(ch[i] === 0) {
ch[i] = 1;
tmp.push(nums[i]);
DFS(L+1); // 종료지점을 위해
tmp.pop();
ch[i] = 0;
}
}
}
}
DFS(0);
return answer;
}
console.log(solution([3, 6, 9], 2));중복 순열을 방지하기 위해, ch배열을 만들어서 체킹을 해주고, 돌면서 nums[i] 값들을 가져와 순열을 만든다.
조합의 경우수(메모이제이션)
조합의 경우의 수를 재귀를 이용해 조합수를 구하여라
nCr = n-1Cr-1 + n-1Cr
이 의미는 {1, 2, 3, 4, 5}가 있을 때, 5의 입장에서는 자기가 참여한 조합의 수와 자기가 참여하지 않은 조합의 수로 나눌 수 있음. 그 둘의 합은 5C3의 조합의 수와 같음
📌 내가 푼 방법
📌 강사님 방법
function solution(n, r) {
let answer = 0;
function DFS(N, R) {
if(N===R || R===0) return 1;
else {
return DFS(N-1, R-1) + DFS(N-1, R);
}
}
answer = DFS(n, r);
return answer;
}
console.log(solution(33, 19));분류를 잘해야함! 종료지점은 n과 r이 같아지는 지점
n===r, r이 0이되는 지점r===0
이렇게 코드를 짜면 33, 19를 넣었을 때 시간이 오래걸림
이것을 해결하기 위해 메모이제이션 사용!
메모이제이션 코드
function solution(n, r) {
let answer = 0;
let dy = Array.from(Array(35), () => Array(35).fill(0));
function DFS(N, R) {
if(dy[N][R] > 0) return dy[N][R];
if(N===R || R===0) return 1;
else {
dy[N][R] = DFS(N-1, R-1) + DFS(N-1, R);
return dy[N][R];
}
}
answer = DFS(n, r);
return answer;
}
let start = new Date();
console.log(solution(33, 19));
let end = new Date();
console.log(end-start);약 5밀리초 밖에 안걸림. dy라는 2차원 배열을 선언해서 그 값들을 안에 저장시켜두고 다시 돌 때 그 값이 존재하면 바로 return dy[N][R]을 해주어서 시간을 단축시킴
수열 추측하기
📌 내가 푼 방법
📌 강사님 방법
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀있고, 아래로 파스칼의 삼각형처럼 진행되며 가장 밑에있는 줄의 수가 주어진다. 삼각형에서 가장 위에 들어갈 N개의 숫자를 반환하여라.
function solution(n, f) {
let answer = 0, flag = false;
let dy = Array.from(Array(11), () => Array(11).fill(0));
let ch = Array.from({length: n+1}, () => 0);
let p = [];
let b = []; // 이항 계수
function combi(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);
}
function DFS(L, sum) {
if(flag) return;
if(L === n) {
if(sum === f) {
answer = p.slice();
flag = true;
}
}
else {
for(let i = 1; i<=n; i++) {
if(ch[i] === 0) {
ch[i] = 1;
p.push(i);
DFS(L+1, sum+(p[p.length-1] * b[L]));
ch[i] = 0;
p.pop();
}
}
}
}
for(let i=0; i<n; i++) {
b.push(combi(n-1,i));
}
DFS(0, 0)
return answer;
}
console.log(solution(4, 16));이항계수로 컴비네이션을 이용해서 푸는 방법 중요! 다시해보기!!!
조합 안쓰고 구하는 방법
function solution(n, f) {
let answer = 0, flag = false;
// let dy = Array.from(Array(11), () => Array(11).fill(0));
let ch = Array.from({length: n+1}, () => 0);
let p = [];
let b = []; // 이항 계수
// function combi(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);
// }
function DFS(L, sum) {
if(flag) return;
if(L === n) {
if(sum === f) {
answer = p.slice();
flag = true;
}
}
else {
for(let i = 1; i<=n; i++) {
if(ch[i] === 0) {
ch[i] = 1;
p.push(i);
DFS(L+1, sum+(p[p.length-1] * b[L]));
ch[i] = 0;
p.pop();
}
}
}
}
b.push(1);
for(let i=1; i<n; i++) {
b.push((b[i-1] * (n-i))/i);
}
DFS(0, 0)
return answer;
}
console.log(solution(4, 16));조합 구하기
1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(n, m) {
let answer = [], tmp=[];
function DFS(L, s) {
if(L === m) {
answer.push(tmp.slice());
} else {
for(let i = s; i<=n; i++) {
tmp.push(i);
DFS(L+1, i+1);
tmp.pop();
}
}
}
DFS(0, 1);
return answer;
}
console.log(solution(4, 2));조합의 기본!, 부분집합을 구할 때 이 코드를 이용해서 풀 수 있다!
여기서 포인트는 for문의 i의 값을 넘어온 s를 이용해 초기화를 시켜주어 자신의 위에 숫자만 포함되도록 하는 것!
