(191117) 자료구조 - Tree Tree 자료구조 tree는 graph 자료구조의 한 종류이다 -> 사이클이 없는 연결 그래프 + 유향 - 사이클이 없다 : 한 시작 정점과 종료 정점이 같지 않음 (즉, 끝에서 시작으로 못가) - 연결 그래프 : 모든 정점쌍에 항상 경로가 존재 (끊어진게 없다는 소리?) - 유향 그래프 : 루트 노드부터 자식노드로 ~ Base - 그래프의 한 종류이기 때문에 마찬가지로 정점과 간선으로 구성 - 루트 노드가 있고 루트 노드는 0개 이상의 자식을 갖음(자식 노드도 마찬가지) - 각 노드는 어떤 자료형으로도 표현 가능 - 계층 자료를 나타낼 때 사용 (디렉터리, 조직도 등!!) 용어 - 루트 노드(root node) : 부모가 없는 노드, 즉 트리는 하나의 루트 노드만 갖는다. - 단말 노드 (leaf no.. 2019. 11. 17. (191117) 자료구조 - Graph Graph 자료구조 연결되어 있는 데이터들의 관계를 표현할 수 있는 자료구조 정점(vertex)과 간선(edge)의 집합, root 노드 개념이 없음, 부모-자식 노드 개념이 없음 Graph 용어 정점(vertex) : 위치 (node 라고도 부름) 간선(edge) : 노드를 연결하는 선을 말함 무향 그래프 와 유향 그래프 - 정점과 간선의 연결 관계에 있어서 방향이 없는 것 / 있는 것 정점의 차수(degree) : 각 정점에 연결된 간선의 갯수 (무향 기준) - Indegree : 유향에서 정점에 들어오는 간선의 갯수 - Outdegree : 유향에서 정점에서 나가는 간선의 갯수 가중치 그래프 - 간선에 가중치 정보를 두어서 구성한 그래프 (네트워크) 연결 그래프 와 비연결 그래프 - 무향 그래프에 .. 2019. 11. 17. (191117) 자료구조 - Linked list 정리하면서 느낀점 핵심은 배열은 탐색은 O(1),탐색은 O(n)!!, 특정 index값 추출이 O(1), 데이터의 삭제 및 추가는 O(n) 연결리스트는 탐색은 O(n), 데이터의 삭제 및 추가는 O(1) 인듯.... (블로깅 하는데 너무 몰입하지말자...시간 너무 많이 씀....) 연결 리스트 (Linked list) 연결리스트에 대해 알아보기전에 배열과 연결리스트를 비교해보자. 배열 (array) - 데이터가 연속적으로 저장되어 있음 장점 1. 특정 데이터(엘리먼트)에 접근할 때 인덱스를 사용하여 매우 빠르고 간단하게 접근할 수 있다. 단점 1. (컴파일언어?에서) 배열을 사용하기 위해서는 배열의 크기를 미리 선언해야하고 크기의 수정이 불가능하기 때문에 메모리 관점에서 비효율적이다. 2. 중간에 데이터.. 2019. 11. 17. (191117) 객체지향 프로그래밍 (OOP) - (3) JS에서 Prototype 자바스크립트는 프로토타입 기반 언어라고 불린다. 자바스크립트도 객제지향언어이지만 class라는 개념이 없다. (Class 문법이 ECMA6 표준에서 추가되었지만, 문법이 추가된 것이지 class 기반으로 바뀐 것은 아님!!) 대신 prototype을 통하여 class를 흉내내어 구현한다. var Person = function () {}; Person.prototype.eyes = 2; Person.prototype.nose = 1; var kim = new Person(); var park = new Person(); console.log(kim.eyes); // 결과는 2 Person.prototype 이라는 빈 object가 어딘가에 존재하고, Person 함수로부터 생성.. 2019. 11. 17. (191117) 객체지향 프로그래밍(OOP) - (2) Object를 생성하는 방법들 - Instantiation Patterns JS에서 Object를 생성하는 방법, 즉 Instantiation pattern에는 'Class' 가 나오기전에 4가지 방법이 있었다. Class가 나오기 전에 사용하던 class 선언 방식에 대해서 알아 보았다. Car라는 객체가 position이라는 property와 move 라는 method를 갖는다고 가정하고 각 방법을 적용 1. Functional Instantiation var Car = function () { var someInstane = {}; someInstance.position = 0; // someInstance에 position property 0으로 초기값 설정 // parameter로 positio.. 2019. 11. 17. (191114) 자료구조 - Stack, Queue 오늘 배운 것 - 자료구조란 무엇인가 - 자료구조 중 stack 과 queue는 무엇인가 아래에 정리!! - 스택과 큐에 대한 기본 개념에 대해서 알 수 있었다. Stack 자료구조 stack 자료구조는 후입선출(LIFO, Last In First Out)의 구조로 위 모습에서 알 수 있듯이 쉽게 상자를 생각하면 된다. 빈 상자에 물건을 쌓는 경우 상자에 가장 먼저 들어온 물건이 제일 밑에 쌓이고 제일 마지막에 들어온 물건이 맨 위에 쌓이기 때문에 만약 물건을 뺀다고 하면 제일 마지막에 들어온 물건부터 상자에서 빠지게되고 제일 먼저 들어온 물건은 그 다음에 들어온 물건들이 모두 빠져야 뺄 수 있다. (stack의 대표적인 예 : 브라우저의 뒤로가기) Property / Method stack 자료구조는 .. 2019. 11. 14. 이전 1 ··· 5 6 7 8 9 다음
