0827 TIL BFS, DFS

BFS (Breathed First Search)

BFS는 너비우선탐색 알고리즘이다.
주로 Queue와 while문과 함께 사용한다.

장점:
1. 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다.
2. 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.
3. 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리하다.

단점:
1. 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간이 필요하다.
2.노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적이다.

DFS (Depth First Search)

DFS는 깊이우선탐색 알고리즘이다.
주로 Stack과 재귀호출을 사용한다.

장점:
1. BFS에 비해 저장공간의 필요성이 적다. 백트래킹을 해야하는 노드들만 저장해주면 된다.
2. 찾아야하는 노드가 깊은 단계에 있을 수록, 그 노드가 왼쪽에 있을 수록 BFS보다 유리하다.

단점:
1. 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려가 있다.
2. 찾은 해가 최단 경로라는 보장이 없다.

🙆‍♀️Array.prototype에는 Stack, Queue 사용을 위해 어떤 메서드가 존재하나요?

Stack : Array.prototype.push(),Array.prototype.pop()
Queue :Array.prototype.push(), Array.prototype.shift()

균형 이진 탐색 트리란 무엇일까요?

AVL Tree 기존 이진탐색트리에서 치우쳐짐을 방지해 균형을 맞게하는 일종의 트릭을 넣은 구조이다.
이진 탐색 트리의 균형판 버전이다.
BF(Balance Factor)를 유저가 설정해두어 트리내 서브트리간의 높이 차이가 BF를 안넘게 수시로 조정한다.
삽입의 경우 4가지 케이스(LL, RR, LR, RL) 로 나누어, '회전' 이라는 개념으로 트리 균형을 유지한다.

3가지 트리 순회방식 (DFS)

      (1)
     /   \
   (2)   (3)
  /  \      
(4)  (5)

1. 전위 순회 (preorder)

1. root
2. left
3. right

결과 : 4 2 5 1 3

2. 중위 순회 (inorder)

1. left
2. root
3. right

결과 : 1 2 4 5 3

3. 후위 순회 (postorder)

1. left
2. right
3. root

결과 : 4 5 2 3 1

그외

Array의 요소를 swap하는 방법

자바스크립트에는 별도의 swap메소드가 없기 때문에 직접 사용해야한다.

1. temp 변수 사용

const arr = [1,2,3,4,5]

let temp = arr[1]
arr[1] = arr[2]
arr[2] = temp

console.log(arr) //[1,3,2,4,5]

2. 구조분해할당 사용

const arr = [1,2,3,4,5]
[arr[1], arr[2], arr[4]] = [arr[2],arr[4],arr[1]]
                            
console.log(arr) //[1,3,5,4,2]

느낀점

어제 자료구조를 처음 봤을때보다는 조금 이해하기가 수월해졌다. 계속해서 반복하면 잘 이해하겠지 ㅎ 주말동안 계속 복습하면 오늘보다 더 이해를 잘 하게될 것같다. 안되면 될때까지 반복하자!