문제
자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
훔치고 싶은 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
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];
}
이번에는 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 공부