그래프란? 객체 간의 연결을 시각화한 것으로 정점(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) 시간 밖에 걸리지 않음 그..

힙(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 !=..

중위순회(in-order traversal) : (왼쪽 - 루트 - 오른쪽) 오름차순(작은 값에서 큰 값 순)으로 방문된다. 트리 정렬 시 사용되는 방법임 전위순회(pre-order traversal) : (루트 - 왼쪽 - 오른쪽) 자식 노드보다 노드 자신을 먼저 방문한다. 구조화된 문서를 출력할 때 많이 이용하는 방법 후위순회(post-order traversal) : (왼쪽 - 오른쪽 - 루트) 자식 노드를 노드 자신보다 먼저 방문 디렉토리와 서브 디렉토리의 파일 용량을 계산할 때 쓰는 방법 //in-order traversal 중위순회 (왼쪽 - 루트 - 오른쪽) inOrderTraverse(callback){ this.inOrderTraverseNode(this.root, callback); }..