26

let dfs = function (node) {
  //{value: 1, child: {value: 2, child: {value: 3, child: null}}} [1,2,3]
  //return node.value; // 1
  let result = [node.value] //현재 위치의 노드가 갖고있는 value를 result에 할당.
  node.children.filter(n => { //현재 위치의 노드가 갖고있는 자식을 필터링. 즉 {} 한꺼풀 벗김.
    result = result.concat(dfs(n)) //result + dfs({자식노드s})
  })
  return result;
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

다시 정리해보는 dfs

dfs는 스택을 활용함.
스택은 후입선출임,,, 나는 비커를 상상하면서 이해했다. 나올구멍이 하나뿐임
const root = new Node(1);
root.addChild(new Node(2));
root.addChild(new Node(3));
root.children[0].addChild(new Node(4));
root.children[0].addChild(new Node(5));
root.children[1].addChild(new Node(6));
root.children[1].addChild(new Node(7));
root.children[0].children[0].addChild(new Node(8));
root.children[1].children[1].addChild(new Node(9));

이렇게 트리를 만들었다.
root의 value값은 1이다.
...... [ 1 ] -level 0
.....[ 2 | 3 ] -level 1
[ 4 | 5 ] [ 6 | 7 ] -level 2
[ 8 ]...........[ 9 ] -level 3

𝟙 result에 1이 들어있는채로 시작한다.
𝟚 1node는 childern이 있다. 각각 2, 3.
여기서 너무 헷갈렸는데 오름차순에 따라 선택해서 우선 탐색하는 것 같다.
그냥 stack이라고 하면 오름차순이니 2, 3이 들어갔을때 마지막으로 들어간 값이 3이니까 3이 먼저 나올것이라고 생각했는데 2가 먼저 나옴..
이건 그냥 구현하기 나름인 것 같음.개념적으로 스택은 후입선출이 맞지만 위에서 작성한 코드는 node의 children을 배열로 보고 순차적으로 concat하고있음!
𝟛 1에 이어 2와 3이 스택에 들어간다.
3은 대기하고, 2가 들어가서 dfs를 호출하면서 result와 concat한다.
dfs가 2라는 인자를 갖고 호출되었으므로 result = 2가 되므로 기존에 root의 value를 갖고있던 result에 2라는 값을 반환한다. [1,2]
2node는 4,5를 갖고있다. 4, 5가 스택에 들어간다.
5는 대기하고, 4가 dfs를 호출하면서 result와 concat한다. [1,2,4]
4node는 8을 갖고있으므로 8이 스택에 들어가고 dfs를 호출하면서 result와 concat한다. [1,2,4,8]
대기하고있던 5가 dfs를 호출하면서 result와 concat. [1,2,4,8,5]
마찬가지로 대기하고있던 3이 dfs 호출...
이 과정을 반복하게된다.

27

최적화되지 않은 코드

function power(base, exponent) {
  // exponent 번 base를 곱한다.
  if (exponent === 0) return 1;
  let i = 1;
  let result = 1;
  while(exponent >= i){
    result = result * base % 94906249;
    i++;
  }
  return result;
}

base를 exponent의 절반만 계산하고 그 결과값을 두번 곱하면 최종결과값이 나온다.

function power(base, exponent) {
  let half = 1;
  if(exponent === 0) return 1;
  for(let i = 1; i <= Math.floor(exponent/2); i++) {
    half = half * base % 94906249;
  }
  //반절로 나누어서 딱 떨어질때(짝수)
  if(exponent % 2 === 0) {
    return half * half % 94906249;
  } else {
    //반절로 나누어서 딱 떨어지지 않았을때(홀수)
    return half * half * base % 94906249;
  }
}

재귀로 거듭제곱 구하기

function power(base, exponent) {
  return exponent === 0 ? 1 : (base * power(base, exponent-1) % 94906249);
}

근데 여기서는 어떻게 최적화를 해야할지...

아래 재귀 + 최적화한 방법을 찾았다!
https://dong-jinmyong.tistory.com/14

function power(base, exponent) {
  if (exponent === 0) return 1;
  let tmp = power(base, Math.floor(exponent / 2));
  let result = tmp * tmp % 94906249;
 
  return exponent % 2 ? base * result % 94906249 : result;
}

28

let bfs = function (node) {
  let data = [];
  let que = [node];
  while(que.length){
    const head = que[0]
    que = que.slice(1);
    data.push(head.value);
    head.children.map(children => que.push(children))
  }
  return data;
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

let bfs = function (node) {
  let queue = [node]; //fifo
  let result = [];
  while(queue.length > 0){
    let targetNode = queue.pop();
    result.push(targetNode.value);// 1. 0번 인덱스에 있는 값이 나오고 result에 기재
    // 2. target node의 child가 있으면 queue에 push
    targetNode.children.map(chnode => queue.unshift(chnode)) //push하면 1,3,2 이런식으로 나오게 됨.
  }
  return result;
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};