JS 코테 재귀함수 및 DFS 정리 그리고 응용

84363 단어 코테 JavaScript JavaScript

재귀함수

재귀함수는 정의된 함수를 내부에서 한번 더 자기 자신을 호출하여 반복하는 함수이다.

이때, 함수의 실행 스택을 이해해야 하는데

아래 예시를 보자

<!-- 이진트리 순회 복습!! -->
<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n) {
        let answer = "";
        function DFS(num) {
          if (num > 7) return;
          answer += num + " ";
          DFS(num * 2);
          DFS(num * 2 + 1);
        }
        DFS(n);
        return answer;
      }

      console.log(solution(1));
    </script>
  </body>
</html>

먼저 위 코드에서 DFS(1)이 먼저 호출되고 내부 함수를 실행하다가 DFS(2)를 실행하면 해당 코드의 위치와 DFS(1)을 함수의 스택에 저장하고 다음 스택에 DFS(2)를 넣고 다시 함수를 실행한다. 이렇게 계속 스택이 쌓이게 되고 내부 if 문에 의해서 함수가 return되어 종료되면 다시 스택의 최상위에 있던 함수가 pop() 되어 사라지고 바로 하단의 함수의 실행코드부터 해당 함수가 실행된다. 그리고 DFS(n*2 + 1)가 실행되어 또 스택을 다시 쌓고 함수의 스택이 전부 사라질때까지 반복하여 실행된다.

이런 실행 순서를 이해하면 전위순회, 중위순회, 후위순회를 실행해볼 수 있다.

전위순회 출력 : 1 2 4 5 3 6 7

출력
DFS(num*2);
DFS(num * 2 + 1);

중위순회 출력 : 4 2 5 1 6 3 7

DFS(num*2);
출력
DFS(num * 2 + 1);

후위순회 출력 : 4 5 2 6 7 3 1

DFS(num*2);
DFS(num * 2 + 1);
출력

재귀함수가 인자로 받는 부분을 깊이(레벨)로 보면 이해하기 쉽다.

부분집합 구하기

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n) {
        let answer = [];
        let check = Array({ length: n + 1 }, () => 0);
        function DFS(num) {
          if (num > n) {
            let tmp = "";
            for (let i = 0; i < n + 1; i++) {
              if (check[i] === 1) tmp += i + " ";
            }
            if (tmp.length > 0) answer.push(tmp.trim());
          } else {
            check[num] = 1;
            DFS(num + 1);
            check[num] = 0;
            DFS(num + 1);
          }
        }
        DFS(1);
        return answer;
      }

      console.log(solution(3));
    </script>
  </body>
</html>

체크배열을 생성하고 해당 인덱스를 0,1로 바꾸면서 해당 체크배열의 값이 1일때만 해당 반복문의 변수 i를 넣어 부분집합을 구한다.

합이 같은 부분집합

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      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 (sum === total - sum) {
              answer = "YES";
              flag = 1;
            }
          } else {
            DFS(L + 1, sum + arr[L]);
            DFS(L + 1, sum);
          }
        }
        DFS(0, 0);
        return answer;
      }

      let arr = [1, 3, 5, 6, 7, 10];
      console.log(solution(arr));
    </script>
  </body>
</html>

재귀의 else 부분 즉 가지로 뻗는 부분에서 배열의 요소를 더해서 재귀에 넣어줄지 안넣고 깊이 레벨만 증가시킬지 정해서 모든 부분집합의 합을 구하고
레벨이 배열의 길이까지만 반복되게하여 해당 합이 전체 배열의 합에서 뺐을때 함수를 종료시켜 판별한다.

조건에 맞는 부분 집합의 합 구하기

예시1

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      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];
      console.log(solution(259, arr));
    </script>
  </body>
</html>

재귀함수내 재귀를 하기 전에 조건문으로 문제에서 원하는 조건을 걸어 종료시켜 해를 구한다.

예시2

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(m, ps, pt) {
        let answer = Number.MIN_SAFE_INTEGER;
        let n = ps.length;
        function DFS(L, sum, time) {
          if (time > m) return;
          if (L === n) {
            answer = Math.max(answer, sum);
          } else {
            DFS(L + 1, sum + ps[L], time + pt[L]);
            DFS(L + 1, sum, time);
          }
        }

        DFS(0, 0, 0);
        return answer;
      }

      let ps = [10, 25, 15, 6, 7];
      let pt = [5, 12, 8, 3, 4];
      console.log(solution(20, ps, pt));
    </script>
  </body>
</html>

중복순열 구하기

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, m) {
        let answer = [];
        let tmp = Array.from({ length: m }, () => 0);
        function DFS(L) {
          if (L === m) {
            answer.push([...tmp]);
          } else {
            for (let i = 1; i <= n; i++) {
              tmp[L] = i;
              DFS(L + 1);
            }
          }
        }

        DFS(0);
        return answer;
      }

      console.log(solution(3, 2));
    </script>
  </body>
</html>

우선 부분수열을 구할 임시배열을 만들고 재귀함수 내 재귀가 시작되는 부분 즉, 깊이 레벨이 높아져 가지가 뻗는 부분에서 반복문을 실행하여 가지의 갯수만큼 돌려서 답을 구한다.

DFS cut edge

재귀함수 도중 조건을 만족하면 바로 종료시켜 전체 트리를 반복하지 않도록 하는 기법이다.

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(m, arr) {
        let answer = Number.MAX_SAFE_INTEGER;
        let n = arr.length;
        function DFS(L, sum) {
          if (sum > m) return;
          if (L > answer) return;
          if (sum === m) {
            console.log(L, 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;
      }

      let arr = [1, 2, 5];
      console.log(solution(15, arr));
    </script>
  </body>
</html>

재귀 실행문 위에 깊이 반복 제한 조건과 해를 구했을 때 바로 종료되는 조건을 두번 걸어 해를 찾았을 때 바로 종료되게 하여 실행속도를 향상시킨다.

재귀 응용 : 팩토리얼

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n) {
        let answer;
        function DFS(n) {
          if (n === 1) return n;
          else {
            return n * DFS(n - 1);
          }
        }
        answer = DFS(n);
        return answer;
      }

      console.log(solution(5));
    </script>
  </body>
</html>

재귀를 실행시키면서 값으로 결국 1이 들어올때 해당 1을 반환하여 함수를 종료시켜 함수 스택이 제거되면서 펙토리얼이 완성되는 코드이다.

조합의 경우의 수

위 공식을 사용해서 재귀로 조합의 경우의 수를 구한다.

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, r) {
        let answer = [];
        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(5, 3));
    </script>
  </body>
</html>

위 코드로 조금 더 큰 수의 조합의 수를 얻으려고 할때는 실행속도가 너무 오래걸려 단축이 필요하다. 따라서 아래의 메모이제이션 기법을 사용해 실행시킨 함수의 결과를 기억해서 재귀를 실행시킬 필요 없이 바로 함수를 반환 종료하여 트리의 반복을 줄여 실행속도를 비약적으로 향상시킨다.

메모이제이션

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, r) {
        let answer = [];
        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 return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
        }
        answer = DFS(n, r);
        return answer;
      }

      console.log(solution(5, 3));
    </script>
  </body>
</html>

위처럼 들어올 최대 자연수가 33이라고 했을때 35행 35열의 이차원배열에 0으로 가득 채운 임시배열을 만들고 트리가 뻗을 때 만드는 조합의 결과를 해당 배열에 값으로 넣어 재귀함수의 첫 실행부분에 이차원배열의 값이 존재하면 바로 해당 값을 리턴하여 트리의 깊이 레벨을 위로 올려 반복횟수를 줄인다.

조합 구하기

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, m) {
        let answer = [];
        let tmp = Array.from({ length: m }, () => 0);
        function DFS(L, s) {
          if (L === m) {
            answer.push([...tmp]);
          } else {
            for (let i = s; i <= n; i++) {
              tmp[L] = i;
              DFS(L + 1, i + 1);
            }
          }
        }
        DFS(0, 1);
        return answer;
      }

      console.log(solution(4, 2));
    </script>
  </body>
</html>

조합을 구하려면 순열과 비슷한 방식으로 진행되나 else의 반복문의 반복 변수가 시작하는 숫자가 처음 시작되어 임시배열의 첫번째 요소와 중복되지 않도록 시작시점을 변수로 두어 재귀시 1씩 증가시켜 넣어주어 조합을 완성시킨다.
(순열은 [1,2]와 [2,1]은 다르지만 조합에서는 같은 경우이다.)

코드예시(배열 메서드 사용)

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, m) {
        let answer = [];
        let tmp = [];
        function DFS(L, s) {
          if (L === m) {
            answer.push([...tmp]);
          } 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));
    </script>
  </body>
</html>

위처럼 임시 배열을 구하고자 하는 조합의 길이만큼 만들지 않고 빈배열을 만들어 push와 pop으로 조합을 구하는 것이 가능하다.

조합 구하기 2

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, k, arr, m) {
        let answer = 0;
        let tmp = [];
        function DFS(L, s, sum) {
          if (L === k) {
            if (sum % m === 0) {
              answer++;
            }
            console.log(sum, tmp);
          } else {
            for (let i = s; i < n; i++) {
              tmp.push(arr[i]);
              DFS(L + 1, i + 1, sum + arr[i]);
              tmp.pop();
            }
          }
        }

        DFS(0, 0, 0);
        return answer;
      }

      let arr = [2, 4, 5, 8, 12];
      console.log(solution(5, 3, arr, 6));
    </script>
  </body>
</html>

위처럼 반복문의 반복요소를 넣는게 아닌 주어진 배열을 이용해 조합을 만드는 것이 가능하니 참고하여 나중에 코테에 적용해보자.

Author And Source

이 문제에 관하여(JS 코테 재귀함수 및 DFS 정리 그리고 응용), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@padd60/JS-코테-재귀함수-및-DFS-정리-그리고-응용

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

Yarn 설치 by npm & Yarn 사용법

Java 문자와 숫자 조합의 크기 비교

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다