Javascript 알고리즘: 힙, 그래프
글 작성자: SoniaComp
공부한 기록을 공유하기 위한 글입니다. 수정할 내용이 있다면 알려주세요!
📕 위 책을 추천하는 이유
JS 코드가 간결해서, 알고리즘의 핵심 논리를 이해하기 정말 쉽다! 👍
Table of the Contents
1. 힙 — 이진힙배열
2. 그래프
3. 다이나믹 프로그래밍
4. 비트조작
1. 힙
힙은 O(1) 시간에 가장 높은 항목이나 가장 낮은 항목을 반환하는 자료구조
최대힙: 부모의 값이 자식들보다 큼(root node가 최대값)
최소힙: 부모의 값이 자식들보다 작음(root node가 최솟값)
특징: 포인터 대신 배열로 자료 저장
→ 부모-자식 관계가 쉽게 정의되기 때문에, 자식의 위치(index)계산이 쉬움
코드구현은 Github 참고
이진힙배열
노드 인덱스
자신: N
부모: (N-1)/2
왼쪽자식: N*2+1
오른쪽 자식: N*2+2
function Heap(){
this.items = [];
}
Heap.prototype.swap = function(index1, index2){ // 둘이 자리 바꾸기
// temp 이용
}
// Parent와 right, left Child와 Index를 지정하는 함수
Heap.prototype.peek = function(item){
return this.items[0];
}
Heap.prototype.size = function(){
return this.items.length;
}삼투: 항목을 추가하거나, 삭제할 때 힙의 구조가 유지 돼야 한다. O(log2(n))
→ 항목 간에 교환이 일어날 때, 비누 거품이 일 듯, 부분 교환이 일어난다.
function MinHeap(){
this.items = [];
}
// 프로토타입을 복사함으로써, 힙으로부터 도움함수를 상속
MinHeap.prototype = Object.create(Heap.prototype);MinHeap.prototype.bubbleDown = function(){
var idx=0;
while(this.leftChild(idx)&&this.leftChild(idx)<this.items[idx]){
var smallerIdx = this.leftChildIndex(index);
if( 오른쪽 항목이 더 작은 경우 ) 교환
this.swap(smallerIdx, idx);
idx=smallerIdx;
}
}
MinHeap.prototype.bubbleUp = function(){
// 위와 비슷한 논리
}// ---- 최소 힙 구현 완성을 위해 필요한 함수 ----//
// 1. add: 신규 항목을 힙에 추가
MinHeap.prototype.add = function(item){
this.items[this.items.length] = item;
this.bubbleUp(); // 순서 만족하도록 보장
}
// 2. poll: 힙으로부터 최소 항목을 추가하고 bubbleDown()을 호출해 순서 유지
MinHeap.prototype.poll = function(){
var items = this.items[0];
this.items[0] = this.items[this.items.length - 1];
this.items.pop();
this.bubbleDown();
return item;
}
2. 그래프
그래프를 사용하면 노드 간의 연결을 다양하게 나타낼 수 있다.
📍그래프 구성 요소: 정점(Vertex), 간선(Edge)
📍그래프 속성: 정점 차수(degree of Vertex), 가중치(weight)
📍그래프 특성: 희소그래프(sparse graph), 밀집 그래프(densegraph), 순환그래프(cyclical graph)
그래프 용어를 공부하려면 클릭🔎
코드구현은 Github 참고
2.1 방향이 없는 그래프
추가(정점을 만든 후, 간선 추가)
function UndirectedGraph(){
this.edges = {};
}
UndirectedGraph.prototype.addVertex = function(vertex){
this.edges[vertex]={};
}삭제(간선 삭제 후, 정점 삭제)
UndirectedGraph.prototype.removeEdge = function(vertex1, vertex2){
if(this.edges[vertex1]&&this.edges[vertex1][vertex2]!=undefined){
delete this.edges[vertex1][vertex2];
}
if(this.edges[vertex2]&&this.edges[vertex2][vertex1]!=undefined){
delete this.edges[vertex2][vertex1];
}
}UndirectedGraph.prototype.removeVertex = function(vertex){
for(var adjacentVertex in this.edges[vertex]){
this.remove(adjacentVertex, vertex);
}
delete this.edges[vertex];
}
2.2 방향이 있는 그래프
추가, 삭제(방향이 없는 그래프 논리에서 방향성만 없앤 논리)
2.3 알고리즘
너비우선검색: O(V+E)
/* 큐를 사용 */
// 시작하는 값: vertex
// fn에는 (vertex)=>{console.log(vertex)} 를 넣을 수 있다.
DirectedGraph.prototype.traverseBFS = function(vertex, fn){
var queue=[], visited={};
queue.push(vertex); // 갈 수 있는 후보군을 queue에 넣고 뺄 거다!
while(queue.length){
vertex=queue.shift();
if(!visited[vertex]){
visited[vertex]=true;
fn(vertex);
for(var adjacentVertex in this.edges[vertex]){
queue.push(adjacentVertex);
}
}
}
}깊이우선검색: O(V+E)
/* 재귀 함수 */
DirectedGraph.prototype.traverseDFS = function(vertex, fn){
var visited = {};
this._traverseDFS(vertex, visited, fn);
}
DirectedGraph.prototype._traverseDFS = function(vertex,visited,fn){
visited[vertex]=true;
fn(vertex);
for(var adjacentVertex in this.edges[vertex]){
if(!visited[adjacentVertex]){
this._traverseDFS(adjacentVertex, visited, fn);
}
}
}다익스트라(가중치 간선 최단경로): O(V²+E)
/* 각 노드에 대한 최단 경로 계산 */
function _isEmpty(obj){
return Object.keys(obj).length===0;
}
function _extraMin(Q, dist){
var minimumDistance=Infinity, nodeWithMinimumDistance=null;
// infinity는 가장 큰 값
for(var node in Q){
if(dist[node]<=minimumDistance){
minimumDistance=dist[node];
nodeWithMinimumDistanc=node;
}
}
return nodeWithMinimumDistance;
}
// 이제 다익스트라를 구현해보장!
// source는 출발점
DirectedGraph.prototype.Dijkstra=function(source){
var Q={}, dist={}; // dist는 source에서 각 노드까지의 거리를 저장
for(var vertex in this.edges){
dist[vertex] = Infinity;
Q[vertex]=this.edges[vertex];
}
dist[source]=0;
while(!_isEmpty(Q)){
var u = _extraMin(Q, dist); // get the min distance
delete Q[u]; // u를 지나왔으니까 Q에서 삭제
// where v is still in Q
for(var neighbor in this.edges[u[){
var alt = dist[u] + this.edges[u][neighbor];
if(alt<dist[neighbot]){
dist[neighbor]=alt;
}
}
}
return dist;
}위상정렬(방향이 있는 그래프 정렬 — 작업 스케쥴링): O(V+E)
/* 추가적인 스택을 지닌 깊이 우선 정렬 */
/* 연결된 모든 노드들을 재귀적으로 방문하면서 해당 노드들을 스택에 추가 */
/* 스택: 순서가 시간순이 되도록 보장 */
/* 사용 예시: 작업 스케줄러 - 순서에 따라 이후 수행될 작업이 이전 작업에 의존 */
DirectedGraph.prototype.Sort = function(){
var visited = {} ;
var stack = []; // 추가
for (var item in this.edges) {
if (visited.has(item) == false) { // 방문했는지 체크
this.topologicalSortUtil(item, visited, stack);
}
}
return stack;
}
DirectedGraph.prototype.SortUtil = function(v,visited,stack){
visited.add(v);
for (var item in this.edges[v]) {
if (visited.has(item) == false) {
this.SortUtil(item, visited, stack)
}
}
stack.unshift(v); // 스택 앞에 넣는다.
}3. 다이나믹 프로그래밍
문제를 더 작은 부분들로 쪼개서 해결한 후, 메모리에 저장
작은 문제들의 해결 값을 사용하여, 더 큰 문제를 해결
다이나믹 프로그래밍 알고리즘 사용 조건
1) 중복 부분 문제가 존재
2) 최적 부분 구조가 존재: 최적 해결책들을 사용해 찾은 부분 문제
4. 비트조작
코드구현은 Github 참고
