재귀와 이진트리

Imnottired·2023년 4월 26일

이번 알고리즘에서는 재귀에 대해서 배웠다.

전에도 재귀에 대해 배웠지만, 이해하려고 하였지만 두려움이 존재했다

그래서 이를 극복하고 정복하고 싶었다.

스택 프레임

let num = 3;

function solution(num) {
  function DFS(N) {
    if (N === 0) return;
    else {
      console.log(N);
      DFS(N - 1);
      console.log(N);
    }
  }

  DFS(num);
}

solution(num);

N! 를 출력하거나
역으로 출력하는 문제이다.
이 문제를 풀면서 좋았던 것은 재귀함수와 스택을 엮어서 생각해본 적이 없었고,
다른 자료 구조형이라고 생각하였다.
(처음 재귀를 배울 당시에 스택에 대한 이해도가 부족하였다.)

재귀 함수를 이해하는 방식이 단순히 머리나, 연산으로 적는 것이 아니고,
스택을 통해 원리 하나하나 풀어가는 방식이 인상적이어서 와닿았다.

재귀에 대해 좀 더 간단하게 정리할 수 있었다.

이진수 출력


let num = 11;
let answer = "";

function solution(n) {
  function DFS(num) {
    if (num === 0) return;
    else {
      DFS(parseInt(num / 2));
      answer += String(num % 2);
    }
  }
  DFS(n);
}
solution(num);
console.log(answer);

// 11 /2 = 5...1
// 5 /2 = 2...1
// 2 /2 = 1...0
// 1 /2 = 0...1
// 1011 거꾸로 올라간다.

이진법에 대한 기본 이해가 필요하다.
이진법은 2로 나누었을 때 나머지를 적으면, 그것을 역순으로 나였했을 때 이진법으로 변한다.
이 원리를 이용하고 스택까지 엮어서 자연스럽게 완성하였다.

재귀에 의해서 가장 아래 자식에 있는 것부터 answer에 쌓이면서
역순으로 자연스럽게 쌓여진다.

이진트리 순회

let num = 1;

function solution(v) {
  function DFS(v) {
    if (v > 7) return;
    else {
      console.log(v);//전위
      DFS(v * 2);
      console.log(v);//중위
      DFS(v * 2 + 1);
      console.log(v);//후위
    }
  }
  DFS(v);
}
solution(num);

이진트리 원리에 대해 이해하는 문제 였다.
전위 순회는 부모 왼쪽 오른쪽
중위 순회는 왼쪽 부모 오른쪽
후위 순회는 왼쪽 오른쪽 부모
순으로 나열 된다.

처음 배웠을 적에는 계속해서 손가락으로 찍으며 가는 순서를 찾아헤맸는데, 원리를 아니
자연스럽게 머리에 들어오게 되었다.

부분집합 구하기


let num = 3;

function solution(v) {
   let anwser = [];
  let ch = Array.from({ length: v + 1 }, () => 0); //틀림

  function DFS(s) {
     if (s === v + 1) {
       //틀림

       let tmp = "";
       for (let i = 1; i <= v; i++) {
        if (ch[i] === 1) tmp += i + " ";
     }

      if (tmp.length > 0) anwser.push(tmp.trim());
    } else {
      console.log(s);
      ch[s] = 1;
      DFS(s + 1); //틀림
      ch[s] = 0;
     DFS(s + 1);
    }
  }

   DFS(1); //틀림
  console.log(anwser);
 }
 solution(num);

부분집합 문제였다.
사실 코테에서 틀린 문제였는데, 다시보니 반가웠다.
부분집합은 2의 n제곱이다.
간단히 말하면 하나씩 뽑기, 안뽑기로 경우의수가 나뉜다.
이를 1, 0으로 표현하여 작성하였고,

횟수를 넘겨줌으로서 특정 횟수에 도달하면 체크하는식으로 처리하였다.
중요했던 것은, trim이나 빈배열이 들어오지 않게 작성하는 것이 중요했다.

합이 같은 부분집합


let arr = [1, 3, 5, 6, 7, 10];

function solution(arr) {
  let total = arr.reduce((a, b) => a + b, 0);
  let answer = "NO";
  let num = arr.length;
  let flag = 0;
  function DFS(l, sum) {
    if (flag) return;
    if (l === num) {
      if (total - sum === sum) {
        answer = "YES";
        flag = 1;
      }
    } else {
      DFS(l + 1, sum + arr[l]);
      DFS(l + 1, sum);
    }
  }
  DFS(0, 0); //틀림

  return answer;
}
console.log(solution(arr));

모든 부분집합이 [1,2,3,4,5] 라면

부분집합을 [1,4] 뽑았을 때, 뽑은 수의 합과 남아있는 [2,3,5] 의 합이 같은 것이 있는지 찾는 문제이다.
중요한 것은, 기존의 갯수만 파리미터로 넘겼던 것과 다르게, 합까지 같이 전달하는 방식으로 해결하는 것이 인상적이었다.
또한 결과가 나왔을 때 flag를 활용하여 체크해주고, 재귀가 남아서 돌지 않도록 처리해주는 것도 인상적이었다.

가장 머리 아팠고 어려웠다.

최대 점수 구하기

let ps = [10, 25, 15, 6, 7]; // 점수
let pt = [5, 12, 8, 3, 4]; //걸리는 시간
let num = 5;
let time = 20;
function solution(ps, pt, time) {
  let answer = Number.MIN_SAFE_INTEGER;
  let M = ps.length;

  function DFS(L, sum, t) {
    if (t > time) return;
    if (L === M) {
      answer = Math.max(answer, sum);
    } else {
      DFS(L + 1, sum + ps[L], t + pt[L]);
      DFS(L + 1, sum, t);
    }
  }
  DFS(0, 0, 0);
  console.log(answer);
}

solution(ps, pt, time);

//[Solved✌🏻]최대점수 구하기

이 문제는 기존의 재귀 문제와 유사했지만 한가지 더 변수를 추가하였다.
어려웠던 점은 다뤄야할 수들이 많아서 까다로웠고, 시행 착오가 반복되어서 문제 뒤에 주석을 쓰는 방식으로 착오를 줄였다.