TIL 6 (2021.10.12)

전위 순회 출처 위키백과

 

'일반적인 순서'는 왼쪽에서 오른쪽으로 진행을 합니다. 이름에 따라서 중간(노드)을 방문하는 순서가 이름에 맞춰서 '일반적인 순서' 에 위치하는 것으로 볼 수 있습니다.

 

전위 순회(preorder)는 다음과 같은 방법으로 진행한다. 

중 - '왼 - 오' =>  '일반적인 순서'의 전방에 중간(노드)가 위치한다.

 

노드를 방문한다.

 

왼쪽 서브 트리를 전위 순회한다.

 

오른쪽 서브 트리를 전위 순회한다.

 

중위 순회(Inorder)은 다음의 순서로 진행된다.

왼 - 중 - 오 =>  '일반적인 순서'의 중간에 중간(노드)가 위치한다.

 

왼쪽 서브 트리를 중위 순회한다.

 

노드를 방문한다.

 

오른쪽 서브 트리를 중위 순회한다.

 

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

'왼 - 오' - 중 => '일반적인 순서'의 후방에 중간(노드)기 위치한다.

 

왼쪽 서브 트리를 후위 순회한다.

 

오른쪽 서브 트리를 후위 순회한다.

 

노드를 방문한다.

---

다음의 질문에 대한 답을 고민해 보세요.

 

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

 

출처 위키백과

 

컴퓨터 과학에서, 자가 균형 (높이 균형) 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리이다.

 

이진 트리에서 노드보다 큰 수는 오른쪽, 작은 수는 왼쪽에 배치를 하게 됩니다. 위의 사진처럼 수들이 입력이 되면 길이가 길어지게 되고, 특정 노드에 도달하는 시간이 오래 걸리게 되지만, 균형 이진 탐색 트리를 통해서 높이는 작게 유지하게 되면 특정 노드에 도달하는 시간을 줄일 수 있습니다.

 

(Advanced) 힙이란 무엇일까요?

 

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

 

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

 

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

 

BFS/ DFS

 

너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 합니다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 합니다. 자식들을 다 돌고 난 뒤에, 각 자식들의 손자들을 또 탐색합니다.

 

깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 합니다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다. 한 자식의 자식들까지 다 보고 난 뒤에 다음 자식(손자)에게 넘어갑니다.

 

 

DFS와 BFS의 장단점은 또 무엇이 있을까요?

 

깊이 우선 탐색의 장점과 단점

 

장점

 

단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

 

목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

 

해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노

드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

 

얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

너비 우선 탐색의 장단점

장점
출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

 

단점

경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.

 

해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.

 

무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 할까요? 

 

반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까요? 

 

---

boiler-plate 

 

Axios란? 출처 Axiou 공식 사이트

Axios는 노드 js와 브라우저를 위한 promise-based HTTP Client 입니다. 서버 측에서는 기본 node.js http모듈을 사용 하고 클라이언트(브라우저)에서는 XMLHttpRequests를 사용합니다.

 

특징

브라우저에서 XMLHttpRequests 만들기

node.js에서 http 요청 만들기

Promise API 지원

요청 및 응답 가로채기

요청 및 응답 데이터 변환

취소 요청

JSON 데이터에 대한 자동 변환

XSRF 로부터 보호하기 위한 클라이언트 측 지원

 

사용 방법

npm install axios ---save