재귀함수와 완전탐색(DFS: 깊이 우선 탐색) 문제풀이 (7번~ 10번)

7. 최대점수 구하기(이진트리 DFS)

N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야한다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주.)

주어진 시간과 문제의 점수, 푸는데 걸리는 시간을 인자로 받는다.

  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)); //41

8. 중복순열 구하기

1부터 N까지 번호가 적힌 구슬이 있다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력하는 프로그램 만들기. N과 M을 인자로 받는다.

  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);
    return answer;
  }

  console.log(solution(3, 2));
  [1,1]
  [1,2]
  [1,3]
  [2,1]
  [2,2]
  [2,3]
  [3,1]
  [3,2]
  [3,3]

9.동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
교환되어야하는 금액과 동전의 종류들을 인자로 받는다.

  function solution(m, arr) {
    let answer = Number.MAX_SAFE_INTEGER;
    function DFS(L, sum) {
      if (sum > m) return;
      if (sum === m) {
        answer = Math.min(answer, L); // L = 쓰인 동전의 개수
      } else {
        for (let i = 0; i < arr.length; i++) {
          DFS(L + 1, sum + arr[i]);
        }
      }
    }

    DFS(0, 0);

    return answer;
  }
  let arr = [1, 2, 5];
  console.log(solution(15, arr)); //3

설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

10. 순열 구하기 (중복 허용 ❌)

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하는 프로그램 만들기. M과 N을 인자로 받는다.

푸는 방식 외우자!

  function solution(m, arr) {
    let answer = [];
    let tmp = Array.from({ length: m }, () => 0);
    let ch = Array.from({ length: arr.length }, () => 0);

    function DFS(L) {
      if (L === m) {
        answer.push([...tmp]);
      } else {
        for (let i = 0; i < arr.length; i++) {
          if (ch[i] === 0) { // 중복 제거를 위해 ch를 둔다.
            ch[i] = 1;
            tmp[L] = arr[i];
            DFS(L + 1);
            ch[i] = 0;// 백하는 지점
          }
        }
      }
    }
    DFS(0);

    return answer;
  }
  let arr = [3, 6, 9];
  console.log(solution(2, arr));
  3 6
  3 9
  6 3
  6 9  
  9 3 
  9 6
  

정리

중복을 허용하지 않는 순열을 구해야하는 프로그램을 만들 때에는 체크 배열을 이용할 수 있다. 이미 확인한 i 부분은 1로 바꾸어줌으로써 중복을 막아준다.