[TIL] Day-5

비선형 자료구조인 그래프와 트리를 구현하고 그것들을 탐색하는 알고리즘을 배웠다.

트리,그래프와 같은 비선형 자료구조를 탐색한다는 것은
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

DFS

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로
넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

• 한 번 길을 정하면 최대한 깊숙히 갔다가 길이 없거나, 왔던 노드일 시
  뒤로 돌아가서 안 간 곳으로 향한다.
• 재귀함수를 사용해 스택의 구조를 활용한다.
• 방문한 노드는 꼭 표시해줘야 한다.

어떤 노드를 먼저 방문할 것인가에 대해(=순회 순서) 3가지의 경우가 있다.
부모 노드의 위치를 기준으로 전위, 중위, 후위로 나뉜다.

• 전위 순회: 부모 - 왼쪽 자식 - 오른쪽 자식

• 중위 순회: 왼쪽자식 - 부모 - 오른쪽 자식

• 후위 순회: 왼쪽 자식 - 오른쪽 자식 - 부모

  
  

DFS의 원리인 재귀함수와 스택구조를 완전히 이해하기 위해 노력 중이다.

• 재귀함수로 인해 함수가 끝나지 않고 계속 스택에 쌓인다.
  → 자식 노드로 계속 파고 드는 것
• 조건에 맞지 않다면(노드가 없다면) 또는 방문했던 노드라면
  해당 함수가 끝나서 스택에서 pop()되고
• 쌓여있던 바로 직전의 함수의 진행으로 돌아온다
  (다시 백해서 부모 노드로 올라가는 것)
• 이 과정이 반복됨

재귀함수 개념은 함수의 반복문이라는 생각이 들었다.

preOrder(node) {
        if(!node) return;
        else{
            console.log(node.value);
            this.preOrder(node.left);
            this.preOrder(node.rigth);
        }
    } ;
preOrder(tree.root)

BFS

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드부터 방문하는 방법이다.
• 자신에게 가장 가까운 계층 level부터 방문하며 내려간다.
• queue 사용해 구현 - queue에서 계층 순서대로 노드가 나온다.
• 출발 지점 → 도착 지점까지의 최단 거리를 구할 때 쓰인다.

각 노드의 계층을 구하는 방법

0. 그래프 또는 트리를 만든다.
1. queue배열에 1번 index에 처음 값을 push한다. (첫 노드)
2. distance배열 1번 index에 1을 push한다. (루트 노드의 계층은 1)
3. queue.shift()를 해준다.
4. 빼낸 노드와 연결된 자식 노드들을 queue에 push()한다.
5. distance배열의 자식 인덱스에 부모 노드의 계층 +1한 값을 넣어준다.
6. queue가 빌 때까지 3~5번 반복한다.

너무 어려워서 몇 번이고 반복해서 강의를 보고 있다. (그림 그려가면서)
볼 때마다 점차적으로 조금씩 이해되는 느낌이라서 몇 십번(?)은 더 봐야겠다.
자료구조와 그와 관련된 알고리즘은 개념이 어렵지는 않지만
그 구조를 코드로 표현하는 것이 굉장히 까다롭다는 것을 느꼈다.
추상적인 데이터나 공간을 물리적인 형태?로 설계하고 다루는 게 낯설다고 해야하나
아직 많이 헤매고 문제 푸는 것도 어려워서 자괴감이 들긴했지만
어려운 거 맞으니까 너무 잘하려고 하지말고 그냥 하자
라고 생각하기로 했다 ~!