알고리즘 스터디를 진행한 후 배운 내용들을 정리했다.

BFS

최단 경로 구할 때 주로 사용.

templete

class BFS() {
    constructor(val) {
	let val = val;
	let left = null || left;
	let right = null || right;
    }
}

function bfsTemplate(root) {
    const queue = [[root]];	// queue declaration
    const result = [[root.val]];
    while (queue.length > 0) {
      const curLevelElement= queue.shift(); // first element in the queue; /// [3], [9, 20], [15, 7]
          // queue = []
      const nextLevel = [];
      // curLevelElement = [3]
      for (let i = 0; i < curLevelElement.length; i++) { // 9 , 20
          const curNode = curLEvelElement[i]; // 3-root, 9, 20
          if (curNode.left) { // 15
          nextLevel.push(curNode.left);
          }
          if (curNode.right) { // 7
          nextLevel.push(curNode.right);
          }
      }
      //nextLevel = [15, 7]
      if (nextLevel.length === 0) return;
      else queue.push([]);
      //queue = [[9, 20]]
      }
    return
}

---

DFS

많이 사용한다. 특정 경로를 구할 때 사용한다.

recursive

어떤 값이 들어있는지 모를 때 사용한다.
전위(preorder), 중위(inorder), 후위순회(postorder)

• 전위 순회: 자신 - 왼쪽 - 오른쪽
• 중위 순회: 왼쪽 - 자신 - 오른쪽
• 후위 순회: 왼쪽 - 오른쪽 - 자신

시간 복잡도: O(N) -> 모든 요소를 다 탐색한다.
공간 복잡도: O(d) -> d=depth - stack을 사용하기 때문. maximum call stack
worst space: O(N)

iterative

Binary Search Tree(이진 탐색 트리)에서 유효한 BST일 때 사용.
즉, 트리의 값이 정해져 있고 규칙이 있을 때 사용한다.
정확한 값을 이용할 때 사용한다.

시간 복잡도: O(logN) -> 아래로 내려갈수록 반씩 줄어든다.
공간 복잡도: O(1)

templete

recursive

function main (root) {
const result = []
    dfsTemplate(root, result);
}
function dfsTemplate(curNode, result)  {
	// base case when do we stop the recursion
    if(curNode === null) return;

    dfsTemplate(curNode.left);
    dfsTemplate(curNode.right);
    result.push(curNode.val);
}

iterative

function dfsIterativeTemplate(root, target) {
    const curNode = root; // 6
    while(curNode) {
	if(curNode.val > target) {
	    curNode = curNode.left; // 4
	} else {
	    curNode = curNode.right // 8
	}

    }
}

---

depth와 height의 차이

depth: 깊이. root부터 leaf node까지
height: 높이. leaf node부터 root까지
보통은 depth 쓰지만 어려운 문제는 height 쓴다.

코드

var maxDepth = function(root) {
    
    // base case ==> edge case
    if(root === null) return 0;
    const depth = [0];
    depthRecursive(root, depth, 1)
    return depth[0];
    //return heightRecursive(root).height;
};

// top to bottom approach
function depthRecursive(curNode, depth, curDepth) {
    if(!curNode.left && !curNode.right) {
        depth[0] = Math.max(depth[0], curDepth);
        return;
    }
    
    if(curNode.left) {
        depthRecursive(curNode.left, depth, curDepth + 1);
    }
    
    if(curNode.right) {
        depthRecursive(curNode.right, depth, curDepth + 1);
    }
    
    return;
    
}

/// bottom up approach
function heightRecursive(curNode) {
    if(curNode === null) {
        return {height: 0};
    }
    
    let left = heightRecursive(curNode.left);
    let right = heightRecursive(curNode.right);
    //console.log(left.height, right.height)
    
    return {height : Math.max(left.height, right.height) + 1};
}

---

topological sort

다른 알고리즘과 BFS나 DFS를 섞는 것.

ex) 비행기 환승 문제.