오늘배운것

• Tree traversal 트리순회
• BFS
• DFS

트리순회

이미지들 by. https://hongku.tistory.com/160

특정 목적을 위해 트리의 모든 노드를 한번씩 방문하는것
이진트리를 이용하여 순회를 할 수 있다.

• 전위순회 (1,2,4,8,9,5,10,11,3,6,12,13,7,14,15)
  루트 -> 왼쪽 노드들을 순차적으로 둘러보기 -> 오른쪽 순회

• 중위순회 (8,4,9,2,10,5,11,1,12,6,13,3,14,7,15)
  루트를 중앙에 두고, 제일 왼쪽 리프부터 -> 오른쪽 순회
  

• 후위순회 (8,9,4,10,11,5,2,12,13,6,14,15,7,3,1)
  루트를 가장 마지막에 순회한다. 왼쪽 리프 -> 루트를 거치지 않고 오른쪽 순회
  

BFS 너비 우선탐색 (Queue로 구현?)

Breadth-First Search
가장 가까운 정점부터 탐색 (가장 가까운 레벨들을 먼저 쭈욱 훑어준다.)

DFS 깊이 우선탐색 (Stack으로 구현?)

Depth First Search
하나의 경로를 끝까지 탐색
끝까지 한우물 파다가 아니면 다음 경로로 넘어간다 (왼-> 오)

-특징1. 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한번씩 방문하는 것이 목적이다. 또한 그래프는 배열처럼 정렬되어있지 않기 때문에 하나하나 찍어주어야 한다. (?)

-특징2. 같은곳을 또 방문하는 경우는 절대 없음

추가적인 사항

• Math.max()에 배열안에 요소를 검사할때,
  ...스프레드 연산자를 사용해서 풀어주어야 한다.

• 프로퍼티 접근.
  변수로 접근할때에는 [ ]브라켓을 사용해서 접근해야 한다.
  그렇지 않으면, undefined가 뜸.

• node 와 vertex의 차이점
  노드가 다른 노드와 연결이 된다면 => vertex

이부분은 확인작업이 필요함

또ㅡㅡ 버택스를 삭제하는 문제가 나오면 인접리스트가 편함
왜냐면, 하나하나 다 옮겨가야해서(인덱스 기준으로 )
0,1,2,3 -> 2 삭제 -> 0,1,2로 바뀜(0,1,3이 아니라)
매우 복잡해진다

정리 및 느낀점

알면 알수록 미스테리 투성이인 자료구조이다.
어제오늘 자료구조 관련 알고리즘 문제들을 푸는데 이틀내내
13문제를(심지어 구현하는 문제는 거의다 코딩이 되어 있는 수준)을 다 못끝냈다.
매일 생각하지만, 그냥 무작정 많이 접하다 보면 언젠간 익숙해지겠지
할수있다..!