그래프란? 객체 간의 연결을 시각화한 것으로 정점(Vertex)간의 관계를 표현하는 자료구조 그래프의 용어 정점(vertex) : 그래프를 형성하는 노드 간선(edge) : 그래프에서 노드 간의 연결 (정점 간에 '선') - 아크라고도 함 정점 차수(degree of vertex) : 해당 정점에 연결된 간선의 개수 인접 노드 : 간선에 의해 직접 연결된 노드 완전 그래프 : 모든 정점이 간선으로 연결된 그래프. 그리고 그래프의 부분집합을 부분 그래프라고 한다. 희소 그래프(sparse graph) : 정점들 간에 가능한 연결 중 일부만 존재하는 경우 해당 그래프를 희소 그래프라고 한다. 밀집 그래프(dense graph) : 다양한 정점들 간에 연결이 많은 경우 해당 그래프를 밀집 그래프라고 한다. 순..

일련의 숫자에서 중앙값 찾기 중앙값이란 어떤 배열을 정렬했을 때 정 가운데에 위치하는 값 원소의 개수가 홀수인 경우: 가장 중앙에 위치한 원소가 중앙 값((전체 개수 + 1) / 2 번째 원소) [1, 2, 3]의 배열에서는 2가 중앙값 원소의 개수가 짝수인 경우: 가운데 두 원소의 평균이 중앙값 [1, 2, 3, 4]에서는 2와 3의 평균인 2.5가 중앙값 중앙값을 찾을 때 그냥 최소힙이나 최대힙 둘중 하나로 만들고 중앙에 해당하는 인덱스에 있는 값을 반환하면 되겠지만 데이터가 지속적으로 추가/삭제되고 있는 상황에서 중앙값을 찾으려면 중앙값을 찾을때마다 배열 전체에 대한 정렬을 시도하므로 시간 낭비임 🌟🌟🌟하나의 최소 힙과 최대 힙을 만들면 중간 값을 얻는 것은 단지 O(1) 시간 밖에 걸리지 않음 그..

힙 정렬 지난 시간 까지 힙 클래스를 생성했으니 힙을 사용해서 정렬을 하는 것은 간단함 정렬된 배열을 얻기 위해 힙이 빈 상태가 될 때까지 힙에 대해 .pop()을 호출하면서 꺼낸 객체를 저장하기만 하면 된다. 삼투(bubbleUp, bubbleDown)가 O(logN)가 걸리고 정렬이 n개의 항목들을 꺼내야 하기 때문에 힙 정렬의 시간 복잡도는 O(NlogN)이다. 최소 힙을 이용하면 오름차순 정렬이 가능할 것이고, 최대 힙을 이용하면 내림차순 정렬이 가능할 것이다. 두가지 모두 sort()라는 메소드를 추가하면 된다. (MinHeap 클래스에 추가하면 MaxHeap은 상속받을 것이다) sort(){ let sort = []; const count = this.items.length; for(let i..

힙(Heap) 힙이란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 힙에는 최소힙과 최대힙이 있음 최소힙 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함 최대힙 가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음 힙에 데이터를 삽입하고 값을 꺼내오는 방법 최소힙에 데이터를 삽입하는 방법 저런 트리가 있다고 하자 1을 삽입하려고 할 때 완전이진트리의 요건을 만족시키기위해 저 자리에 삽입 자신의 값과 자신의 부모노드값을 비교하여 자신의 값이 더 작으면 자리를 바꿈 3번의 과정을 자신의 값이 부모노드값보다 작을때까지 혹은 루트에 도착할 때까지 반복한다. 이 작업은 밸런스가 맞춰져있..

이진탐색트리에서 삭제를 할 때에는 경우의 수를 3가지를 생각해야 한다. 경우 1) 리프노드(자식이 없는 노드)일 경우 * 이 경우 단순히 해당 노드를 null로 처리하고 그 노드를 return하기만 하면 된다. 경우 2) 왼쪽/오른쪽 중에서 한쪽에만 자식이 있는 경우 * 오른쪽에만 자식이 있다면, 왼쪽 자식을 해당 노드로 바꾸고 그 노드를 return한다 (한마디로 할아버지가 손자 손을 잡도록 하는 격) 경우 3) 왼쪽/오른쪽 양쪽 모두 자식이 있는 경우 * 삭제하려고 하는 노드를 [왼쪽 서브트리 중 가장 큰 노드]또는 [오른쪽 서브트리 중 가장 작은 노드]로 교체하고, 이 후 서브트리에서 그 노드는 삭제를 해준다. * 나는 [오른쪽 서브트리 중 가장 작은 노드]로 대체하는 방법을 선택하여 자바스크립트 ..

최솟값/최댓값 찾기 (min(), max()) 이진탐색트리에서 최솟값은 맨 왼쪽 노드값이고, 최댓값은 맨 오른쪽 노드값이다. 그러므로 최솟값을 구하는 메소드 min(), 최댓값을 구하는 메소드 max()는 다음과 같이 구현할 수 있다. //최솟값 찾기 min(){ return this.minNode(this.root); } minNode(node){ if(node){ while(node && node.left !== null){ node = node.left; } return node.key; } return null; } //최댓값 찾기 max(){ return this.maxNode(this.root); } maxNode(node){ if(node){ while(node && node.right !=..