효율적인 피보나치 만들기
재귀함수를 처음 배울 때 피보나치를 만들라는 문제가 있었고 가장 먼저 풀게 된 방법은 이렇다.
function fibonacci(num) { if (num === 0) { return 0; } else if (num === 1) { return 1; } return fibonacci(num-2) + fibonacci(num -1) }
이렇게 해도 피보나치의 답은 나올 수 있다. 하지만 이 식이 효율적이냐는 질문에는 나는 대답할 수 없었다.
효율이라는 부분을 이해하지 못했기 때문이다.
그리고 실제로 내가 만든 식을 돌려본 결과 피보나치 5번째를 구하기 위해서 피보나치 3,4번째를 구해야하고 또 그 둘을 구하기 위해선 1,2,2,3번째가 필요하고 또 그 넷을 확인하면 1,0,1,0,1,1,2번째가 필요하고를 거듭해서 굉장히 많은 단계가 필요하단 것을 깨달았다. 그리고 확인해본 결과 memoization 이란것을 문제에서 확인할 수 있었다. (기초문제에서는 memoization을 사용하지 말라고 했고 효율적인 피보나치를 만들때는 사용해야하는 것 같았다.)
피보나치를 재귀를 활용하여 효율적으로 만드는 법
인터넷에서 피보나치를 효율적으로 만들기를 찾았고 fibonacci(num)의 값을 배열에 더해주는 memoization에 대해 알아냈고 위의 방식으로 식을 만들자 처음에는 각각의 값을 구해야했지만 그 뒤로는 이미 넣어놓은 값을 활용하여 문제를 해결하는 모습을 볼 수 있었다.
JSON이란? JSON 만드는 과정
JSON이란?
객체를 문자화 하기 위해서 String을 써보면
let a = {a:1}
String(a)
"[object Object]""[object Object]" 라는 답이 나온다. 객체를 문자열로 나타내기 위해 JSON을 써야했고 JSON을 만들어보기 위해 재귀함수를 이용한 식을 활용했다.
임의의 인자가 들어갔을 때 그것을 문자화 하는 식이며,
function makeJSON(obj) {
if (typeof obj === "function" || obj === undefined) {
return undefined;
}
else if (obj === null || obj === NaN) {
return 'null';
}
else if (typeof obj === 'string') {
return `"${obj}"`
}
else if (!Array.isArray(obj) && typeof obj === "object") {
let newObj = '{';
for (let prop in obj) {
let property = makeJSON(prop);
let value = makeJSON(obj[prop]);
if (value !== undefined) {
newObj = newObj+`${property}:${value},`
}
}
if (newObj === '{') {
newObj = '{}';
}
else {
newObj = newObj.slice(0,-1)+'}';
}
return newObj;
}
else if (Array.isArray(obj)) {
let newArr = [];
for (let el of obj) {
newArr.push(makeJSON(el))
}
return `[${newArr}]`
}
else {
return `${obj}`
}
}; //물론 이 식은 JSON.stringify() 을 구현하기 위한 식이지만 함수이름을 간단하게 makeJSON으로 했다.이런 식을 만들게 되었다. 함수이거나 undefined일 경우는 undefined를 리턴해주고 객체의 경우 키가 문자열이 되어야 했기에 재귀함수를 이용했다. 또한 배열의 경우 배열 안에 객체가 있을 경우를 생각해서 요소에 재귀함수를 넣었다.
Tree UI 만들기
DOM과 재귀함수를 이용해 리스트를 만들 수 있었고 그 리스트는 리스트 안에 리스트가 들어가는 경우였기에
리스트를 재귀함수를 활용해 만들고 리스트 안의 리스트를 재귀함수를 넣어줬다.
<body>
<ul id="root">
<li>
<input type="checkbox" checked />
<span>음료</span>
<ul>
<li>
<input type="checkbox" />
<span>콜드브루</span>
<ul>
<li>나이트로 콜드 브루</li>
<li>돌체 콜드 브루</li>
<li>제주 비자림 콜드 브루</li>
<li>콜드 브루</li>
</ul>
</li>
<li>
<input type="checkbox" />
<span>프라푸치노</span>
<ul>
<li>애플 쿠키 크림 프라푸치노</li>
<li>더블 에스프레소 칩 프라푸치노</li>
<li>모카 프라푸치노</li>
<li>피스타치오 크림 프라푸치노</li>
</ul>
</li>
<li>
<input type="checkbox" />
<span>블렌디드</span>
<ul>
<li>망고 바나나 블렌디드</li>
<li>딸기 요거트 블렌디드</li>
<li>자몽 셔벗 블렌디드</li>
<li>피치 & 레몬 블렌디드</li>
</ul>
</li>
<li>
<input type="checkbox" />
<span>티</span>
<ul>
<li>라임 패션 티</li>
<li>민트 블렌드 티</li>
<li>아이스 유스베리 티</li>
<li>아이스 캐모마일 블렌드 티</li>
</ul>
</li>
<li>
<input type="checkbox" />
<span>주스</span>
<ul>
<li>한방에 쭉 감당</li>
<li>파이팅 청귤</li>
<li>딸기주스</li>
<li>도와주 흑흑</li>
</ul>
</li>
</ul>
</li>
</ul>
</body>만들고자 했던 HTML의 형식이며
const root = document.getElementById('root');
function createTreeUi(menu, currentNode) {
for (el of menu) {
if (el.type === 'group') {
let li = document.createElement('li');
currentNode.append(li);
let check = document.createElement('input');
check.setAttribute('type','checkbox');
li.append(check);
let span = document.createElement('span');
span.textContent = el.name;
li.append(span);
let makeUl = document.createElement('ul');
li.append(makeUl);
createTreeUi(el.children, makeUl);
}
else {
let li = document.createElement('li');
li.textContent = el.name;
currentNode.append(li);
}
}
}
createTreeUi(menu, root);코드를 작성해서 리스트가 재귀를 통해 리스트안의 리스트로 만들어 질 수 있도록 했다.
마지막으로...
화이팅 하자 노력하자
