🎯 Achievement Goals

코플릿 [DP] 금고를 털어라

👉 코플릿 [DP] 금고를 털어라

문제

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.

예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

$50 한 장을 훔친다
$20 두 장, $10 한 장을 훔친다
$20 한 장, $10 세 장을 훔친다
$10 다섯 장을 훔친다

훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.

주의사항

Number 타입을 리턴해야 합니다.
모든 화폐는 무한하게 있다고 가정합니다.

입출력 예시

let output = ocean(50, [10, 20, 50]);
console.log(output); // 4

let output = ocean(100, [10, 20, 50]);
console.log(output); // 10

let output = ocean(30, [5, 6, 7]);
console.log(output); // 4

🤔 나의 생각

이 문제는 DP 알고리즘이기 때문에 문제를 작게 분할해서 생각해야 했다.
DP 알고리즘은 점화식으로 문제를 풀어나아가야 한다.
나는 먼저 정렬을 해주었고, 작은것 부터 올라가는 방식인 bottom-up 형태로 알고리즘을 풀어갔다.
문제를 작은 것에서부터 풀어나가면서 메모이제이션도 가능해야 한다. 그래야 숫자가 커졌을 때도 복잡도 문제를 해결할 수 있다.

code

function ocean(target, type) {

  let type_ = type.sort((a, b) => a - b);
  // 가방에 값을 저장하면서 카운트를 할 예정이기 때문에
  // 1을 넣어준다.
  let bag = [1];

  // 2번째부터 ~ target 까지 0으로 만들어준다.
  for (let i = 1; i <= target; i++) {
    bag[i] = 0;
  }

  for (let i = 0; i < type.length; i++) {
    for (let j = 1; j <= target; j++) {
      // type보다 작은 숫자는 탐색할 필요가 없다.
      if (type[i] <= j) {
        // 돈을 훔칠 수 있는 금액이면 bag[0] = 1 인 점을 이용해서
        // 카운트를 해준다.
        bag[j] += bag[j-type[i]];
      }
    }
  }
  return bag[target];
}  

👉 Tree-Map

이번에는 pseudo-classical 방식으로 Tree-Map을 구현을 해보았다.

자식 노드를 추가할 수 있는 addChild 메소드와 모든 요소에 callback 함수를 적용시킬 수 있는 map 메소드를 구현하였다.

Code

const Tree = function (value) {
  this.value = value;
  this.children = [];
};

// 자식 노드 추가 메소드
Tree.prototype.addChild = function(child) {
  const childNode = new Tree(child)
  this.children.push(childNode);
};

// 콜백 함수 메소드
Tree.prototype.map = function(callback) {
  // 콜백함수가 적용된 값을 넣어준 새로운 생성자 함수
  let newTree = new Tree(callback(this.value));

  // 생성자 함수 자식 노드에 내장함수 map 을 사용해서 모든 노드에
  // callback 함수를 적용시킨다. 
  newTree.children = this.children.map(function(child) {
    return child.map(callback);
  });
  return newTree;
};

🙌 느낀점

드디어 힘들고 힘들었던 자료구조 스프린트가 끝이났다!!! 만세~~ 하지만 알고리즘 Toy 50문제가 남았다 … ㅎㅎ 이 50문제는 수료하기 전까지(6월 전까지) 하루에 한 문제씩 풀어야 한다. 그래도 또 한 고비를 넘긴 것 같아서 기분이 좋다 ㅜㅜㅜㅜㅜ

이제는 React, Redux와 node.js, 백엔드 내용을 다룬다. 앞으로 배울 내용들이 정말 재밌을 것 같아서 설렌다!!

앞으로도 쭉 열심히하자~!!

👊 내일의 TIW(today I Will)

React 공부

← Previous Post Next Post →

DP 알고리즘, Tree-Map

📅 TIL #44