uni's code uni's code

1. graph란? 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조 ex) 지도, 지하철 노선도, 선수 과목 등을 표현 할 수 있는 자료구조. 크게 아래 방식으로 구분함. - 방향 그래프 vs 무방향 그래프 - cyclic vs acyclic (싸이클의 존재 유무) 2. graph 용어 정리 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(..

1) concept binary tree는 이진트리라고 하며, tree의 속성에서 자식 노드를 최대 2개로 제한한 트리이다. (자식 노드가 0개여도, 이진트리이다.) (+) 공집합도 이진트리인 이유 루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 위는 이진트리를 재귀적 정의로 표현한 것인데, 공집합도 이진트리여야 이는 성립된다. 재귀적으로 조건을 확인해갔을 때, leaf node 에 다다랐을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 된다. 2) 이진트리의 종류 full binary tree(정이진 트리), complete binary tree(완전 이진트리)..

1. tree 란? 순차적 자료구조 : 리스트, 연결리스트, 스택, 큐 등 저장되어 있는 순서가 있음.(자료를 순서를 매겨 나열한 구조) 비선형 자료구조 : 일렬로 나열하기 힘들고, 자료의 순서가 불규칙해서 연결관계가 복잡한 구조. tree는 비선형 자료구조에 해당한다. 형태가 나무를 뒤집힌 모양과 유사해서 tree라고 부른다. 부모와 자식 간의 관계(계층적 관계)를 표현. (링크드 리스트는 사실상 자식이 한개만 가지고 있는 경우임) 2. 알아야 할 용어 노드 : 각 원소 root 노드 : 부모 노드가 없는 최상단 노드. leaf 노드(terminal 노드) : 자식 노드가 없는 말단 노드. internal 노드 : leaf 노드를 제외한 모든 노드. 엣지 : 노드들을 잇는 선 경로(path) : 노드와..

1. Queue 란? 데이터가 한쪽 끝에서 추가가 되고, 반대쪽 끝에서 데이터가 삭제되는 형태의 자료구조. FIFO(First In First Out)으로, 가장 먼저 들어간 원소가 첫번째로 나오는 형태이다. 참고로, queue에서 앞에 있는 원소를 first(head), 마지막에 있는 원소를 rear라는 포인터로 가르킨다. 2. js에서 queue의 구현 js에서 queue에 대한 기능을 독립적으로 제공하지 않는다. 그러나 array의 shift() 메소드를 통해, 비슷하게 구현이 가능하다. 하지만 실제 queue를 통한 enqueue와 array의 shift와의 연산 속도는 차이가 있다. 그 이유는 shift의 로직과 관련이 있다. shift 의 로직은 다음과 같다. 배열의 첫번째 원소에 접근 후 삭..

1. stack 이란? 데이터(원소)를 탑 형태로 쌓는 형태의 자료구조. LIFO(Last In First Out)이라고 하며, 가장 마지막에 들어간 원소가 가장 처음으로 나오는 구조이다. stack의 예시는, ctrl + z(실행 취소) , 이전페이지로 가기 등이 있다. 2. stack 의 코드 구현 class Node { constructor(value){ this.value = value; this.next = null; } } class Stack { constructor(){ this.top = null; this.bottom = null; this.length = 0; } peek() { // stack에 쌓인 가장 마지막 녀석을 확인하는 메소드 return this.top; } push(va..