Algorithm (21) 썸네일형 리스트형 [Udemy] 그래프(Graph) 란? 정의그래프는 노드와 노드 사이의 연결을 모은 자료구조를 말한다. 위 그래프는 양방향인 것 처럼 보이지만 양쪽 방향이 있는 것은 방향이 없는 것으로 간주한다. 용어- vertex(정점): 노드를 말한다.- edge: 간선 유형- directed graph(방향 그래프): 간선에 방향이 존재한다.- undirected graph(무방향 그래프): 간선에 존재하는 방향이 없다.- weighted graph(가중 그래프): 간선에 부여된 값이 없다.- unweighted graph(비가중 그래프): 간선에 부여된 값이 있다. 그래프 정렬그래프 정렬은 간선 사이의 관계를 표현하는 방법이다. 1. 인접행렬(adjacency matrix) - 데이터끼리 뭉쳐있고 간선이 많은 그래프에 적합 2. 인접 .. [Udemy] 해쉬 테이블(Hash Table)이란 ? 정의해쉬 테이블은 모든 언어에서 사용하는 자료구조로, 해쉬 테이블은 key, value로 구성된 자료구조이다.자바스크립트에서 객체가 해쉬 테이블이다. 해쉬 테이블을 구현하는 방법은 수많은 방법이 있고 각 방법 마다 효율성이 달라지기 때문에여기선 어떻게 구현하는지 정도만 이해하고 실제로 해쉬 테이블을 사용할 때는 객체를 사용하는 것을 추천한다. 코드 및 구현1. Hash 함수 구현해쉬 테이블을 구현하기 위해선 key 값을 입력했을 때, 해당 key 값에 해당하는 특정한 값을 반환하는 함수인Hash 함수를 구현해야 한다.예를 들어, 특정 값인 0을 반환하면 [[key, value], ... ] 이런식으로 배열에 특정 값(인덱스)에 key, value를 가진 배열을 가진다.function firstHash(.. [Udemy] 이진 힙(Binary heap)과 우선순위 큐(Priority Queue) 정의이진 힙은 힙의 한 종류이고, 힙(Heap)은 트리 자료구조의 한 종류이다. 이진 힙과 이진 검색 트리의 가장 큰 차이점은 이진 힙에 값이 추가될 때 항상 왼쪽먼저 채워진다는 점이다. 이진 검색 트리는 부모 노드와 값을 비교하여 작으면 왼쪽, 크면 오른쪽 자식 노드로 채워진다. 이진 힙에는 최대 이진 힙, 최소 이진 힙 두 가지로 나뉜다. 최대 이진 힙부모 노드가 자식 노드보다 값이 커야만 한다. 최소 이진 힙부모 노드가 자식 노드보다 값이 작아야만 한다. 우선 최대 이진 힙을 구현하여 이진 힙에 대해 알아보고,최소 이집 힙을 통해 우선순위 큐에 대해 알아보자. 최대 이진 힙 구현최대 이진 힙은 부모 노드보다 자식 노드 값이 커야만 한다.function swap(arr,i,j) { [arr[i.. [Udemy] Tree 순회 - BFS, DFS 이란? 정의BFS(Breadth First Search), 너비 우선 탐색은 트리 자료구조에서 순회 시루트노드에서 부터 시작하여 하위 노드들로 이동할 때, 같은 레벨에 있는 노드들부터 순회하는 방법을 말한다. DFS(Depth First Search), 깊이 우선 탐색은 트리 자료구조에서 순회 시루트노드에서 부터 시작하여 가장 리프 노드까지 먼저 순회하는 방법을 말한다.DFS에서는 순회시 후위 순회, 전위 순회, 중위 순회 방법이 있다. BFS 구현class Node { constructor(value) { this.value = value; this.left = null; this.right = null; }}class BinarySearchTree { .. [Udemy] 이진 검색 트리(Binary Search Tree)란? 정의이진 검색 트리를 설명하기 전 트리 자료구조에 대해 먼저 설명하자면,트리 자료구조는 비선형 자료구조로, 부모가 자식을 가리키는 구조이다.위 사진처럼 최상위 노드를 '루트'라고 부르고,'루트'에서 하위 노드 방향으로 연결된 자료구조를 '트리' 자료구조라고 한다. 이진 트리는 노드당 최대 2개의 자식을 가지며,이진 검색 트리는 추가로 부모 노드보다 작은 숫자는 좌측노드, 부모 노드보다 큰 숫자는 우측노드로 정렬되어 있다는 특징이 있다. 용어- 루트(root) : 최상위 노드- 자식노드(child) : 같은 부모를 가지는 노드, 루트와 먼쪽으로 이동할 때 직접적으로 연결된 노드- 부모노드(parent) : 자식을 가진 노드- 형제노드(siblings) : 동일한 부모를 갖는 노드 그룹- 리프노드(leaf.. [Udemy] 큐(Queue)란? 정의큐(Queue)는 선입선출 특징을 가진 선형 자료구조이다.매표소에 줄 서기, 편의점 진열 매대 등 일생활 대부분에서 사용되는 자료구조이다. 코드 및 구현1. 배열로 구현배열 메서드를 통해 구현할 수 있다.const queue = [];queue.push(1);queue.push(2);queue.push(3);queue.shift(); // 1queue.shift(); // 2queue.shift(); // 3// orqueue.unshift('a');queue.unshift('b');queue.unshift('c');queue.pop(); // aqueue.pop(); // bqueue.pop(); // c 큐를 배열로 구현할 때 주의할 점은 선입선출을 지켜줘야 한다는 것이다.push 메서드로 데이터.. [Udemy] 스택(Stack)이란 ? 정의스택(Stack)은 선형자료구조로, 후입선출(LIFO) 특징을 가지고 있다.브라우저 히스토리, 쌓여있는 접시, ctrl + z로 undo 하는 행위에 사용된다. 코드 및 구현1. 배열로 구현가장 간단하게 스택을 구현하는 방법은 배열로 구현하는 것이다.const stack = [];stack.push('a');stack.push('b');stack.push('c');stack.pop(); // cstack.pop(); // bstack.pop(); // a// orstack.unshift('hi');stack.unshift('my');stack.unshift('name');stack.shift(); // namestack.shift(); // mystack.shift(); // hi 배열로 스택을 구.. [Udemy] 이중 연결 리스트 (Double Linked List) 구현 정의이중 연결 리스트는 단일 연결리스트에서 각 node에 prev(포인터)만 추가된 자료구조이다.prev(포인터)가 있어 유연성이 늘어난 만큼 메모리가 더 크다. 코드 및 구현1. Node 객체 구현class Node { constructor(val) { this.val = val this.next = null; this.prev = null; }} 단일 연결 리스트의 Node 클래스의 constructor에 prev 포인터를 추가했다. 2. DoubleLinked List 구현2.1. push 메서드 구현단일 연결 리스트의 마지막 부분에서 요소를 추가하는 메서드push(val) { let node = new Node(val); .. 이전 1 2 3 다음
