📖 오늘 학습 뽀인트!

1. 페이지 교체 알고리즘
2. 트리와 그래프
   2-1 트리
   2-2 그래프

1. 페이지 교체

🕵️‍♀️페이지 교체 알고리즘이란?
새로운 값을 메모리에 추가해야 될 때 이미 값이 할당된 메모리 중에서 어느 것과 교체할지를 결정하는 것이라고 생각한다.

---

✍ Hit & Miss
메모리에 해당 값이 있다면 cache hit, 없다면 cache Miss 라고 한다.

---

FIFO 알고리즘 (First-in First out) : 먼저 들어온 값을 먼저 제거한다.
0 4 6 5 4 7 8 4 7 5 순서로 참조하며 메모리 사이즈가 3일 경우,
[0] ➡ [0, 4] ➡ [0, 4, 6] ➡ [4, 6, 5] ➡ 4 Cache Hit ➡ [6, 5, 7] ➡ [5, 7, 8] ➡ [7, 8, 4] ➡ 7 Cache Hit ➡ [5, 8, 4]

---

OPT 알고리즘 (Optimal) : 값이 메모리상에 없는 경우, 순서에 따라 사용하지 않는 값을 교체하는 기법이다.
0 4 6 5 4 7 8 4 7 5 순서로 참조하며 메모리 사이즈가 3일 경우,
[0] ➡ [0, 4] ➡ [0, 4, 6] ➡ [5, 4, 6] ➡ 4 Cache Hit ➡ [5, 4, 7] ➡ [8, 4, 7] ➡ 4 Cache Hit ➡ 7 Cache Hit ➡ [5, 4, 7]

---

LRU 알고리즘 (Least-Recently-Used) : 가장 오랫동안 사용하지 않은 값을 제거한다.
0 4 6 5 4 7 8 4 7 5 순서로 참조하며 메모리 사이즈가 3일 경우,
[0] ➡ [0, 4] ➡ [0, 4, 6] ➡ [5, 4, 6] ➡ 4 Cache Hit ➡ [5, 4, 7] ➡ [8, 4, 7] ➡ 4 Cache Hit ➡ 7 Cache Hit ➡ [5, 4, 7]

2. 트리와 그래프

2-1 트리

🕵️‍♀️트리 구조란?
한 노드가 다른 노드를 가리키는 구조이다. 나무를 거꾸로 뒤집은 형태와 같기 때문에 트리 구조라고 한다. 탐색 알고리즘 구현에 많이 사용된다.

class Node {
        constructor(data) {
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }

      class Tree {
        constructor(data) {
          let init = new Node(data);
          this.root = init;
          this.데이터수 = 0;
        }

        length() {
          return this.데이터수;
        }

        insert(data) {
          let 새로운노드 = new Node(data);
          let 순회용현재노드 = this.root;

          while (순회용현재노드) {
            if (data === 순회용현재노드.data) {
              // 값이 같으면 추가시켜주지 않습니다.
              return;
            }
            if (data < 순회용현재노드.data) {
// 들어온 데이터가 작은 경우 왼쪽에 노드 연결
// 해당 데이터 부분이 비어있으면 데이터를 넣고, 비어있지 않으면 더 깊이 탐색
              if (!순회용현재노드.left) {
                순회용현재노드.left = 새로운노드;
                this.데이터수 += 1;
                return;
              }
              순회용현재노드 = 순회용현재노드.left;
            }
            if (data > 순회용현재노드.data) {
//들어온 데이터가 큰 경우 오른쪽에 노드 연결.
// 해당 데이터 부분이 비어있으면 데이터를 넣고, 비어있지 않으면 더 깊이 탐색.
              if (!순회용현재노드.right) {
                순회용현재노드.right = 새로운노드;
                this.데이터수 += 1;
                return;
              }
              순회용현재노드 = 순회용현재노드.right;
            }
          }
        }

        DFS() {
          // 깊이우선탐색, DFS(Depth First Search)
          // Stack 이용!
          let 결과값 = [];
          let 스택 = [this.root];

          while (스택.length !== 0) {
            let current = 스택.pop();
            if (current.right) {
              스택.push(current.right);
            }
            if (current.left) {
              스택.push(current.left);
            }
            결과값.push(current.data);
          }
          return 결과값;
        }

        BFS() {
          // 너비우선탐색, BFS(Breadth First Search)
          // Queue 이용!
          let 결과값 = [];
          let 스택 = [this.root];

          while (스택.length !== 0) {
            let current = 스택.shift();
            if (current.left) {
              스택.push(current.left);
            }
            if (current.right) {
              스택.push(current.right);
            }
            스택.push(current.data);
          }
          return 결과값;
        }
      }

      let t = new Tree(5);
      t.insert(3);
      t.insert(8);
      t.insert(1);
      t.insert(4);
      t.insert(6);
      t.insert(9);

위에 코드는 노드 추가, 깊이 우선, 너비 우선 탐색 모두 작성되어 있다.
조금 복잡하다고 생각해 아래 상황에 따라 코드를 정리해봤다.

// BFS
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"]
};

const start = "A";
const end = "F";

const bfs = (graph, start, end) => {
  let queue = [start];
  let visited = [];
  let count = 0;

  while (queue.length !== 0) {

    let size = queue.length;
    for (let i = 0; i < size; i++) {
      let n = queue.shift();              // 1
      if (n == end) return count;         // 2

      if (!visited.includes(n)) visited.push(n);    // 3
      let sub = graph[n].filter((x) => !visited.includes(x));  // 4
      for (let i of sub) queue.push(i);   // 4
    }
    count += 1      // 5
  }
};

1. FIFO를 위해 큐에 있는 값을 shift로 빼기.
2. 만약, 큐에 있는 값을 뺏는데 도착 노드면, count 값 반환.
3. 만약 검토된 적이 없는 노드면, visited 배열에 추가.
4. 지금 검토하고 있는 값에서 이전에 검토한 적이 없는 값을 빼내어 큐에 저장.
5. 카운트 증가.

2-2 그래프

🕵️‍♀️그래프 구조란?
마인드맵 또는 거미줄과 비슷한 형태라고 생각한다. 루트 노드가 지정되어 있지 않고 상황에 따라 기준이 되는 노드가 있다.