비선형 자료구조인 그래프와 트리를 구현하고 그것들을 탐색하는 알고리즘을 배웠다.
트리,그래프와 같은 비선형 자료구조를 탐색한다는 것은
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로
넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
어떤 노드를 먼저 방문할 것인가에 대해(=순회 순서) 3가지의 경우가 있다.
부모 노드의 위치를 기준으로 전위, 중위, 후위로 나뉜다.
전위 순회: 부모 - 왼쪽 자식 - 오른쪽 자식
중위 순회: 왼쪽자식 - 부모 - 오른쪽 자식
후위 순회: 왼쪽 자식 - 오른쪽 자식 - 부모
DFS의 원리인 재귀함수와 스택구조를 완전히 이해하기 위해 노력 중이다.
재귀함수 개념은 함수의 반복문이라는 생각이 들었다.
preOrder(node) {
if(!node) return;
else{
console.log(node.value);
this.preOrder(node.left);
this.preOrder(node.rigth);
}
} ;
preOrder(tree.root)
각 노드의 계층을 구하는 방법
너무 어려워서 몇 번이고 반복해서 강의를 보고 있다. (그림 그려가면서)
볼 때마다 점차적으로 조금씩 이해되는 느낌이라서 몇 십번(?)은 더 봐야겠다.
자료구조와 그와 관련된 알고리즘은 개념이 어렵지는 않지만
그 구조를 코드로 표현하는 것이 굉장히 까다롭다는 것을 느꼈다.
추상적인 데이터나 공간을 물리적인 형태?로 설계하고 다루는 게 낯설다고 해야하나
아직 많이 헤매고 문제 푸는 것도 어려워서 자괴감이 들긴했지만
어려운 거 맞으니까 너무 잘하려고 하지말고 그냥 하자
라고 생각하기로 했다 ~!