Graph
1)개념
: 노드(정점,Node, vertex) 와 간선(edge)로 구성된 자료구조
용어들
차수(Degree): 정점에 몇 개의 간선이 연결되어 있는가
사이클(Cycle): 자기 자신으로 다시 돌아올 수 있는 경로
2) 구현
그래프 구현 방식1: 인접 행렬
- 인접 행렬: 정점의 연결 관계를 2차원 배열에 0(연결x), 1(연결 o)로 표현하는 것
- 인접 행렬의 장점: 연결 여부를 O(1)만에 알 수 있다.
- 인접 행렬의 단점: 1. 인접한 정점을 찾는데 O(n)걸린다. 2. 실제 간선의 개수와 관계없이 무조건 n**2개의 칸을 써야 한다.
그래프 구현 방식2: 인접 리스트
- 인접 리스트: 각각의 정점에 대하여 인접한 정점 번호를 저장
- 인접 리스트의 장점: 1. 인접한 정점을 찾는데 해당 정점의 딱 필요한 개수만 확인하면 된다. 2. 필요한 만큼만 공간을 활용한다.
- 인접 리스트의 단점: 연결 여부를 확인하기 위해선 인접한 모든 node를 전부 확인해야 한다. 그래서 O(v의 차수) = O(deg(v)) 만큼 걸린다.
- 인접 리스트를 이용한 그래프의 구현
/* Undirected Graph */
// 무방향그래프를 인접 리스트로 구현
class Graph {
constructor() {
this.nodes = {};
}
//addNode(node) - 그래프에 노드를 추가합니다.
//그래프의 인접 리스트 구조
//this.node = { 1: [2, 3, 4],
// 2: [1, 3],
// 3: [1, 2],
// 4: [1]
// }
addNode(node) {
this.nodes[node] = this.nodes[node] || {
edges: [],
};
//원래는
// this.nodes[node] = this.nodes[node] || {
// edges: {},
// };
//였는데 굳이 왜 edges를 객체로 해야하는지 이해가 안가서 (위의 '그래프의 인접 리스트 구조'처럼) 배열로 만들어서 구현했음
}
//contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.
contains(node) {
return (this.nodes[node] ? true : false);
}
//removeNode(node) - 그래프에서 노드를 삭제합니다.
//1. 각 노드의 edge에 node 번호 있으면 다 삭제
//2. 그리고 최종적으로 해당 node 객체도 삭제
removeNode(node) {
for(let currNode in this.nodes){
let Nodeindex = this.nodes[currNode]['edges'].indexOf(node)
if(Nodeindex !== -1){
this.nodes[currNode].edges.splice(Nodeindex, 1);
}
}
delete this.nodes[node];
}
//hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.
//무방향이니까 하나만 확인해주면 된다. 나는 fromNode의 edges에 toNode가 있는지만 확인ㄴ
//1. fromNode의 edges에 toNode가 있는지 확인
//2-1. 있으면 true반환
//2-2. 없으면 false반환
hasEdge(fromNode, toNode) {
if(this.nodes[fromNode].edges.includes(toNode)){
return true;
}
return false;
}
//addEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 추가합니다.
//방향이 없으니까 fromNode, toNode에 모두 상대 Node를 추가해 주어야한다.
addEdge(fromNode, toNode) {
this.nodes[fromNode].edges.push(toNode);
this.nodes[toNode].edges.push(fromNode);
}
//removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.
//1. 둘 사이에 간선이 있는지 부터 확인
//2-1. 있으면 간선 삭제(fromNode의 edge에서도 toNode 삭제해야하고, toNode의 edge에서도 fromNode 삭제해야 한다.)
//2-2. 없으면 그냥 끝
removeEdge(fromNode, toNode) {
if(this.hasEdge(fromNode, toNode)){
let Nodeindex = this.nodes[fromNode].edges.indexOf(toNode);
this.nodes[fromNode].edges.splice(Nodeindex, 1);
Nodeindex = this.nodes[toNode].edges.indexOf(fromNode);
this.nodes[toNode].edges.splice(Nodeindex, 1);
}
}
}
Tree
1) 개념
: 노드로 구성된 계층적 자료구조 / 사이클이 없는 그래프
용어들
- 노드(node, 정점): 트리의 구성요소
- 간선(edge): 노드와 노드를 잇는 선
- root: 트리 구조에서 최상위에 존재하는 노드들
- 부모 노드(parent)
- 자식 노드(child)
- depth(level): 루트를 기준으로 다른 노드로 접근하기 위한 거리
- height:
- sibling: 같은 depth에 존재하는 노드들을 부르는 관계
- leaf: 자식이 없는 node
2) 구현
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
//Q. children left, right 신경쓰지 않아도 되는 이유: binary tree가 아니기때문
//트리의 구성
// 1
// /\
// 2 3
// /\
// 4 5 이면
// this.children = [1]
// node 번호 , [children node들]
// 1 (=thiss.chilren[0]) [2, 3]
// 2 (=thiss.chilren[1].children[0]) [4, 5]
// 3 (=thiss.chilren[2].children[1]) []
// 4 (=thiss.chilren[1].children[0].children[0]) []
// 5 (=thiss.chilren[1].children[0].children[1]) []
//insertNode(value) - 트리에 노드를 추가합니다.
//Q. 문제가 '트리에 노드를 추가한다'고 너무 단순하다고 모호하게 적혀있어서 tree.test.js확인
// -> 정말 노드만 추가하면 되고, 기존 트리 노드와의 연결성은 신경써주지 않아도 되는 것으로 보임
// -> 또한 tree.test.js의 31:37 문제를 보았을 때, this.children은 해당 트리에 있는 모든 node들을 모아둔 배열이고,
// 여기서 index를 통해 접근하여 그 TreeNode의 class에 자식 Node를 insertNode하는 방식으로 진행됨.
// 1. 새로운 노드 선언하고
// 2. this.children에 새로운 노드 추가히주기
insertNode(value) {
let newTreeNode = new TreeNode(value);
this.children.push(newTreeNode);
}
//contains(value) - 트리에 해당 노드가 존재하는지 여부를 반환합니다.
//1. this.children의 인덱스(각각의 node) 가서
//2. 그것의 this.children도 확인 - 이때 어디까지 깊이 들어갈지 모르니까 재귀
// 2-1. 기저조건: this.children이 비어있으면 나오기
// 2-2. 아니면 재귀: this.children.contains(value)
contains(value) {
for(let i=0; i<this.children.length; i++){
let currNode = this.children[i];
if(currNode.value === value){
return true;
}
else{
if(currNode.contains(value)){
return true; //tree.test.js의 39:47번 문제를 보면 return true를 왜 해줘야 하는지 이해간다.
// 여기서 return true를 안해주면, 재귀로 깊이 들어갔을 때 value에 해당하는 node를 찾아도, return 이 아무것도 안되기때문에
// 결국 다음 재귀가 들어가게되면 false가 되기 때문이다.
}
}
}
return false;
}
}
Binary Search Tree
1) 개념
최대 2개의 자식만 가지는 트리로, 이진 탐색 트리에서는 노드의 값에 따라 정렬 방법 및 노드의 순서가 존재한다.
예를 들어,
이 트리에서는 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재합니다.
트리의 성질:
트리는 그 안에 또 트리가 존재한다.
질문
깊이 우선 탐색은 무엇인가요?
자료구조의 node들을 돌아다니며, 그 안에 무슨 값이 있는지를 탐색 해보고 싶을 때, 순회(탐색)방법에는 깊이 우선탐색과 너비 우선탐색이 있습니다.
여기서 깊이 우선탐색은, 스택을 이용해서 최대한 깊숙하게, 많이 가보는 방식으로 갈 수 있을 만큼 (발자취-스택 을 남기면서)가보고 갈 수 없으면 남긴 발자취를 따라 이전 node로 back하는 방식입니다.
이진 탐색 트리가 주어졌을 때, 다음과 같은 방법으로 탐색할 수 있나요?
전위 순회(Preorder Traversal): 부모 → 좌 → 우
중위 순회(Inorder Traversal): 좌 → 부모 → 우
후위 순회(Postorder Traversal): 좌 → 우 → 부모
이진 탐색 트리의 종류에도 여러가지가 있습니다. 다음 이진 트리는 각각 어떤 특징을 가지나요?
- 정 이진 트리(Full Binary Tree)
- 완전 이진 트리(Complete Binary Tree)
- 포화 이진 트리(Perfect Binary Tree)
2) 구현
class BinarySearchTreeNode {
constructor(value) {
this.value = value;
this.left = null; //this.value보다 작은 값들로 이루어진 subtree
this.right = null; //this.value보다 큰 값들로 이루어진 subtree
}
//this: 전체 binary search tree의 root..?
//insert(value) - 이진 탐색 트리에 노드를 추가합니다.
//1. 일단 맨 끝에 넣고,
//2. 우선순위 비교해가면서 알맞은 자리 찾아감.
//2-1. 위(this.value)에서부터 비교해가며 내려온다. (이때, 무조건 전체 tree의 우선순위가 맞아야 한다고 생각했는데, 그냥 해당 node, 그 node의 left, 그 node의 right만 맞으면 된다.)
//2-2. this.value > value일 때
// 3-1. 왼쪽이 비어있으면 왼쪽에 넣고 끝, 3-2. 비어있지 않으면, 그 밑으로 내려가서 같은 과정 반복
//2-3. this.value <= value일 때
// 3-1. 오른쪽이 비어있으면 오른쪽에 넣고 끝, 3-2. 비어있지 않으면 그 밑으로 내려가서 같은 과정 반복
insert(value) {
let newNode = new BinarySearchTreeNode(value);
function insertRecursion(topNode){
if(topNode.value > newNode.value){
if(topNode.left === null){
topNode.left = newNode;
}
else{
insertRecursion(topNode.left);
}
}
else if(topNode.value <= newNode.value){
if(topNode.right === null){
topNode.right = newNode;
}
else{
insertRecursion(topNode.right)
}
}
}
insertRecursion(this);
}
//contains(value) - 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환합니다.
//1. 위에서부터 확인하면서 내려온다.
//2. 위에서 값 확인
//3-1. 맞으면 true 반환하고 끝
//3-2. 아니면 값이 작으면 왼쪽 으로 반복
//3-3. 아니면 값이 크거나 같으면 오른쪽으로 반복
contains(value) {
var flag = false;
function containsRecursion(topNode){
if(topNode.value === value){
flag = true;
return;
}
else if(topNode.value > value){
if(topNode.left === null){
return;
}
else{
containsRecursion(topNode.left);
}
}
else{
if(topNode.right === null){
return;
}
else{
containsRecursion(topNode.right);
}
}
}
containsRecursion(this);
return flag;
}
//inorder(callback) - 이진 탐색 트리를 중위순회 합니다.
//기저조건: 좌, 우가 모두 없을 때
//아니면, Left-> Root-> Right(좌 → 부모 → 우)
inorder(callback) {
function findValue(currNode)
{
if(currNode!==null)
{
findValue(currNode.left);
callback(currNode.value);
findValue(currNode.right);
}
}
findValue(this);
}
}
'Dev > SW Engineering' 카테고리의 다른 글
| 6. Inheritance Patterns - Object Oriented Programming (0) | 2020.05.24 |
|---|---|
| 5. Data Structure - Time Complexity (0) | 2020.05.24 |
| 4. DataStructure - Linked List, Hash Table (0) | 2020.05.24 |
| 3. Data Structure - Stack, Queue (0) | 2020.05.24 |
| 0. Bootcamp Roadmap (0) | 2020.05.01 |