꾸준2

참고)

https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

https://velog.io/@pa324/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-n8k1e9v4jo

그래프(Graph)

• 정점(node)과 정점을 연결하는 간선(edge)의 연결을 시각적으로 표현한 자료구조 입니다.
• 그래프의 종류에는 무방향 그래프, 방향 그래프, 가중치 그래프 등이 있습니다.
• 구현 방법으로는 인접행렬(2차원배열), 인접리스트(리스트)이 있습니다.
• 부모, 자식 관계가 없습니다.

그래프 용어

• 정점(vertex) : 그래프를 형성하는 노드(원을 이용해 위치를 표현합니다.)
• 간선(edge) : 그래프에서 정점(node) 간의 연결, 즉 정점(node)을 연결하는 선을 의미합니다.
• 정점 차수 : 해당 정점(node)에 연결된 총 간선의 개수를 의미합니다.
• 인접 정점 : 해당 정점과 간선에 의해 연결된 정점

용어 설명

정점 : A, B, C, D

간선 : 정점과 정점 사이에 연결된 모든 파란색 선

정점 차수 : A : 3개, B : 1개, C : 2개, D : 2개

인접 정점

{A : B, C, D}

{B : A}

{C : A, D}

{D : A, C}

무방향 그래프(Undirected Graph)

• 두 정점이 각각 간선으로 연결되어 있고 간선의 방향이 없는 그래프(두 정점 모두 간선을 통해 양 방향을 이동 가능)
• 정점 A와 정점 B를 연결하는 간선 (A, B), (B, A) 모두 동일합니다
• ex) 양방향 통행 도로
• 표현하는 방식으로는 인접 행렬, 인접 리스트가 있습니다.

무방향 가중치 그래프 구현

code

// ---------------- Graph 클래스 생성 ----------------

function undirectedGraph() {
  this.edges = {};
}



// ---------------- 간선, 정점 추가 ----------------

undirectedGraph.prototype.addVertex = function(vertex) {
  this.edges[vertex] = {};
}

undirectedGraph.prototype.addEdge = function(vertex1, vertex2, weight) {
  if(weight == undefined) {
    weight = 0;
  }
  this.edges[vertex1][vertex2] = weight;
  this.edges[vertex2][vertex1] = weight;
}



// ---------------- 간선, 정점 삭제 ----------------

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 removeVertex in this.edges[vertex]) {
    this.removeEdge(removeVertex, vertex);
  }
  delete this.edges[vertex]
}




// ---------------- 예제 ----------------

var graph1 = new undirectedGraph();

// 정점 추가
graph1.addVertex(1);
graph1.addVertex(2);
graph1.addVertex(3);
graph1.addVertex(4);
console.log(graph1)
// undirectedGraph { edges: { '1': {}, '2': {}, '3': {}, '4': {} } }

// 간선 추가
graph1.addEdge(1, 2, 1)
graph1.addEdge(2, 3, 10)
graph1.addEdge(3, 1, 15)
graph1.addEdge(4, 1, 5)
console.log(graph1)
// undirectedGraph {
//   edges: {
//     '1': { '2': 1, '3': 15, '4': 5 },
//     '2': { '1': 1, '3': 10 },
//     '3': { '1': 15, '2': 10 },
//     '4': { '1': 5 }
//   }
// }

// 정점, 간선 삭제
graph1.removeVertex(2)
graph1.removeEdge(1, 3)
console.log(graph1)
// undirectedGraph {
//   edges: { '1': { '4': 5 }, '3': {}, '4': { '1': 5 } }
// }

설명

// ---------------- Graph 클래스 생성 ----------------

function undirectedGraph() {
  this.edges = {};
}



// ---------------- 간선, 정점 추가 ----------------

// 정점 추가
undirectedGraph.prototype.addVertex = function(vertex) {
  this.edges[vertex] = {};
}

// 두 정점 간의 간선 추가
undirectedGraph.prototype.addEdge = function(vertex1, vertex2, weight) {
  if(weight == undefined) {
    weight = 0;
  }
  // vertex1 정점, vertex2 정점 모두 가중치가 있는 간선을 추가하는 코드
  this.edges[vertex1][vertex2] = weight;
  this.edges[vertex2][vertex1] = weight;
}



// ---------------- 간선, 정점 삭제 ----------------

// 두 정점 간의 간선 삭제
undirectedGraph.prototype.removeEdge = function(vertex1, vertex2) {

  // (vertex1 간선의 존재 여부) && (vertex1과 vertex2가 간선으로 연결되어 있는지 여부) 참이면
  // vertex1정점에 연결되어 있는 vertex2정점 과의 간선을 삭제
  if(this.edges[vertex1] && this.edges[vertex1][vertex2] != undefined) {
    delete this.edges[vertex1][vertex2]
  }

  // (vertex2 간선의 존재 여부) && (vertex2와 vertex1이 간선으로 연결되어 있는지 여부) 참이면
  // vertex2정점에 연결되어 있는 vertex1정점 과의 간선을 삭제
  if(this.edges[vertex2] && this.edges[vertex2][vertex1] != undefined) {
    delete this.edges[vertex2][vertex1]
  }
}

// 해당 정점 삭제
// 1. 해당 정점에 연결되어 있는 모든 간선을 삭제한다.
// 2. 해당 정점을 삭제한다.
undirectedGraph.prototype.removeVertex = function(vertex) {

  // 해당 정점의 연결되어 있는 모든 간선을 반복문을 통해 삭제하는 코드
  for(var removeVertex in this.edges[vertex]) {
    this.removeEdge(removeVertex, vertex);
  }
  // 해당 정점 삭제
  delete this.edges[vertex]
}




// ---------------- 예제 ----------------

var graph1 = new undirectedGraph();

// 정점 추가
graph1.addVertex(1);
graph1.addVertex(2);
graph1.addVertex(3);
graph1.addVertex(4);
console.log(graph1)
// undirectedGraph { edges: { '1': {}, '2': {}, '3': {}, '4': {} } }

// 간선 추가
graph1.addEdge(1, 2, 1)
graph1.addEdge(2, 3, 10)
graph1.addEdge(3, 1, 15)
graph1.addEdge(4, 1, 5)
console.log(graph1)
// undirectedGraph {
//   edges: {
//     '1': { '2': 1, '3': 15, '4': 5 },
//     '2': { '1': 1, '3': 10 },
//     '3': { '1': 15, '2': 10 },
//     '4': { '1': 5 }
//   }
// }

// 정점, 간선 삭제
graph1.removeVertex(2)
graph1.removeEdge(1, 3)
console.log(graph1)
// undirectedGraph {
//   edges: { '1': { '4': 5 }, '3': {}, '4': { '1': 5 } }
// }

방향 그래프(Directed Graph)

• 두 정점이 간선으로 연결되어 있고 한 정점에만 간선의 방향이 있는 그래프(간선의 방향이 있는곳만 이동할수 있다)
• 정점 A와 정점 B를 연결하는 A -> B 간선이 있다면 (A, B)로만 이동 가능하고 (B, A)로는 이동 불가능
• ex) 일방 통행
• 표현하는 방식으로는 인접 행렬, 인접 리스트가 있습니다.

방향 가중치 그래프 구현

code

function directedGraph() {
  this.edges = {};
}

directedGraph.prototype.addVertex = function(vertex) {
  this.edges[vertex] = {}
}

directedGraph.prototype.addEdge = function(goVertex, stopVertex, weight) {
  if(weight == undefined) {
    weight = 0
  }
  this.edges[goVertex][stopVertex] = weight;
}

directedGraph.prototype.removeEdge = function(goVertex, stopVertex) {
  if(this.edges[goVertex] && this.edges[goVertex][stopVertex] != undefined) {
    delete this.edges[goVertex][stopVertex];
  }
}

directedGraph.prototype.removeVertex = function(vertex) {
  for(var allEdge in this.edges[vertex]) {
    this.removeEdge(allEdge, vertex);
  }
  delete this.edges[vertex]
}


var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('B')
graph2.addVertex('C')

graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('C', 'A', 1)

console.log(graph2.edges)
// { A: { B: 1 }, B: { C: 1 }, C: { A: 1 } }

graph2.removeEdge('A', 'B')
graph2.removeVertex('B')
console.log(graph2.edges)
// { A: {}, C: { A: 1 } }

힙(Heap)

• 가장 높은 항목이나 가장 낮은 항목을 O(1)시간에 반환할 수 있는 자료구조 입니다.
• Tree 형식과 비슷하고 포인터가 아닌 배열을 기반으로 한 완전 이진 트리입니다.
• Tree와 다르게 중복된 값도 추가를 할 수 있습니다.
• 우선 순위 큐 개념을 이용하여 데이터들이 우선순위를 가지고 있고 빠져 나갈때 우선순위로 빠져나갑니다.

힙 종류

최대 힙(Max-Heap)

• 최상위 노드가 가장 높은 값을 갖고 있습니다.
• 부모 노드 값 >= 자식 노드의 값

최소 힙(Min-Heap)

• 최상의 노드가 가장 낮은 값을 갖고 있습니다.
• 부모 노드 값 <= 자식 노드 값

힙 배열 인덱스 구조

• 노드 : 인덱스
• 자신 : N
• 부모 : (N-1)/2
• 왼쪽 자식 : (N*2)+1
• 오른쪽 자식 : (N*2)+2

(1) index - 자신
(2) index*2 + 1; - 왼쪽 자식
(3) index*2 + 2; - 오른쪽 자식

  (1)(2)(3)
!! 0,1,2
!! 1,3,4
!! 2,5,6
!! 3,7,8
!! 4,9,10
                 0
       1                   2
    3     4           5      6
 7   8  9  10   11 12 13 14      

힙 정렬(Heap Sort)

• 완전 이진 트리를 형식으로 만들어진 힙 자료구조를 정렬하는 알고리즘입니다.
• 불안정 정렬에 속합니다.
• 오름차순, 내림차순 정렬이 있습니다.

사용 예시

• 가장 크거나 작은 값을 구할 때
• 최대 i 만큼 떨어진 요소들을 정렬할 때

장점

• 최악의 경우에도 빠른 시간 복잡도를 보장합니다.
• 가장 크거나 작은 값을 필요로 할 때 유용합니다.

단점

• 데이터들의 상태에 따라 다른 정렬들에 비해서 조금 느린편입니다.
• 데이터의 순서가 바뀌는 불안정한 알고리즘입니다.

code

// ----------------------- 힙 클래스 -----------------------

function heap() {
  this.items = [];
}

heap.prototype.swap = function(index1, index2) {
  var temp = this.items[index1];
  this.items[index1] = this.items[index2];
  this.items[index2] = temp;
}

heap.prototype.parentIndex = function(index) {
  return Math.floor((index-1)/2);
}

heap.prototype.leftChildIndex = function(index) {
  return index*2+1
}

heap.prototype.rightChildIndex = function(index) {
  return index*2+2
}

heap.prototype.parent = function(index) {
  return this.items[this.parentIndex(index)];
}


heap.prototype.leftChild = function(index) {
  return this.items[this.leftChildIndex(index)];
}

heap.prototype.rightChild = function(index) {
  return this.items[this.rightChildIndex(index)];
}


// ----------------------- 삼투 구현 -----------------------

function minHeap() {
  this.items = [];
}
minHeap.prototype = Object.create(heap.prototype);


minHeap.prototype.bubbleDown = function() {
  var index = 0;

  while(this.leftChild(index) && (this.leftChild(index) < this.items[index] ||
        this.rightChild(index) < this.items[index]) ) {
          var smallerIndex = this.leftChildIndex(index);
          if(this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
            smallerIndex = this.rightChildIndex(index);
          }
          this.swap(smallerIndex, index);
          index = smallerIndex;
        }
}

minHeap.prototype.bubbleUp = function() {
  var index = this.items.length-1;
  while(this.parent(index) && this.parent(index) > this.items[index]) {
    this.swap(this.parentIndex(index), index);
    index = this.parentIndex(index);
  }
}


// ----------------------- 최소 힙 -----------------------


minHeap.prototype.add = function(item) {
  this.items[this.items.length] = item;
  this.bubbleUp()
}

minHeap.prototype.poll = function() {
  var temp = this.items[0];
  this.items[0] = this.items[this.items.length-1];
  this.items.pop();
  this.bubbleDown();
  return temp;
}


var minH = new minHeap();
minH.add(1);
minH.add(10);
minH.add(5);
minH.add(100);
minH.add(8);
console.log(minH)

console.log(minH.poll());
console.log(minH.poll());
console.log(minH.poll());
console.log(minH.poll());
console.log(minH.poll());
console.log(minH)

설명

// ----------------------- 힙 클래스 -----------------------

// 배열을 기반으로 한 완전 이진 트리이기 때문에 배열로 초기화함
function heap() {
  this.items = [];
}

// 값 비교 후 위치를 바꿔야할때 실행 되는 함수
heap.prototype.swap = function(index1, index2) {
  var temp = this.items[index1];
  this.items[index1] = this.items[index2];
  this.items[index2] = temp;
}

// 해당 index의 부모 인덱스 찾는 함수
heap.prototype.parentIndex = function(index) {
  return Math.floor((index-1)/2);
}

// 해당 index의 왼쪽 자식 인덱스 찾는 함수
heap.prototype.leftChildIndex = function(index) {
  return index*2+1
}

// 해당 index의 오른쪽 자식 인덱스 찾는 함수
heap.prototype.rightChildIndex = function(index) {
  return index*2+2
}




// 1. 해당 인덱스의 부모 인덱스를 찾는다
// 2. this.items[부모 인덱스]를 통해 값을 찾는다

// 해당 index의 부모 값을 찾는 함수
heap.prototype.parent = function(index) {
  return this.items[this.parentIndex(index)];
}

// 해당 index의 왼쪽 자식 값을 찾는 함수
heap.prototype.leftChild = function(index) {
  return this.items[this.leftChildIndex(index)];
}

// 해당 index의 오른쪽 자식 값을 찾는 함수
heap.prototype.rightChild = function(index) {
  return this.items[this.rightChildIndex(index)];
}





// ----------------------- 삼투 구현 -----------------------

function minHeap() {
  this.items = [];
}

// 프로토타입을 복사 해서 힙 클래스로부터 도움 함수를 상속받는다
minHeap.prototype = Object.create(heap.prototype);



// bubbleDown함수는 poll함수에서 트리의 가장 밑부분(배열의 마지막 요소)을 꼭대기(배열[0])에 저장했지만 최솟값인지 알수 없기 때문에
// 반복문을 통해 해당 값 위치를 찾아주는 로직이다.

// (1) - index에 0을 저장해 트리의 꼭대기부터 내려가도록 한다.
// while
// (2) - while문 조건에서 (왼쪽 자식의 존재 여부), (현재 값(부모) > 왼쪽 자식 && 현재 값(부모) > 오른쪽 자식)를 확인한다.
// (3) - (2)조건문을 통과한다면 smallerIndex에 왼쪽 자식 인덱스 값을 임시로 저장한다.
// (4) - 왼쪽 자식과 오른쪽 자식의 값을 비교하고 더 값이 작은 쪽에 index를 smallerIndex에 저장한다.
// (5) - (1)의 인덱스(index)와 (4)의 인덱스(smallerIndex에) 위치를 바꿔준다(위치가 바뀐다는 의미는 트리의 꼭대기에서 점점 내려온다는 의미)
// (6) - index의 값을 변경하면서 자신의 자리를 찾아간다.
minHeap.prototype.bubbleDown = function() {
  var index = 0; // (1)
  while(this.leftChild(index) && (this.leftChild(index) < this.items[index] || // (2)
        this.rightChild(index) < this.items[index]) ) {
          var smallerIndex = this.leftChildIndex(index); // (3)
          if(this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
            smallerIndex = this.rightChildIndex(index); // (4)
          }
          this.swap(smallerIndex, index); // (5)
          index = smallerIndex; // (6)
        }
}




// bubbleUp함수는 트리모양에서 가장 밑부분에서 꼭대기까지 조건에 맞다면 올라오는 로직이다.

// (1) - index에 add함수에서 추가한 요소의 위치(this.items.length-1)값을 넣는다.
// (2) - while문 조건에서 부모의 존재 여부와 부모의 값 > 현재 추가한 값 일때 swap함수를 이용해 교체한다.
// (3) - swap과정에서 위치를 바꾸고 index값을 바꿈으로써 현재 추가한 값의 위치를 (2)조건문과 비교하여 찾아간다.
//     !!! 현재 추가한 값이 최솟값이라면 가장 밑부분에서 꼭대기까지 swap을 하게 된다.
minHeap.prototype.bubbleUp = function() {
  console.log('bubbleUp 함수 실행')
  var index = this.items.length-1; // (1)
  console.log(`방금 추가한 값 : ${this.items[index]}, 부모의 값 : ${this.parent(index)}`)
  console.log('')
  // 부모값이 현재 추가한 값보다 큰 경우 스왑하는 반복문
  while(this.parent(index) && this.parent(index) > this.items[index]) { // (2)
    this.swap(this.parentIndex(index), index);
    index = this.parentIndex(index); // (3)
  }
}







// ----------------------- 최소 힙 -----------------------


// 배열의 총 길이에 +1 위치에 해당 item 값을 추가하고 bubbleUp()함수 실행한다
// 즉 배열의 크기가 0부터 추가횟수만큼 증가한다는 의미!!
minHeap.prototype.add = function(item) {
  this.items[this.items.length] = item;
  this.bubbleUp()
}


// 최소 값을 꺼내지만 배열에서 제거 할때는 가장 마지막 노드를 제거한다.
// 즉 var a = [1,2,3,4,5]에서 1을 제거하지만 a.pop()을 통해 배열의 마지막 요소를 삭제함

// 이유
// (1) temp 임시 변수에 최솟값(arr[0])을 저장한다.
// (2) arr[0]번째에 arr[마지막 인덱스] 값을 저장한다.
// (3) arr.pop()을 통해 마지막 인덱스를 제거한다(하지만 0번째 index에 저장되어있으므로 상관없다)
// (4) bubbleDown()함수를 실행한다. => 그 이유는 arr[0]번째에 arr[마지막 인덱스] 값을 저장했지만 최솟값인지 모르기 때문에
// (5) 최솟값(temp)을 return하여 출력한다.
minHeap.prototype.poll = function() {
  var temp = this.items[0]; // (1)
  this.items[0] = this.items[this.items.length-1]; // (2)
  this.items.pop(); // (3)
  this.bubbleDown(); // (4)
  return temp; // (5)
}






var minH = new minHeap();
minH.add(10);
minH.add(3);
minH.add(8);
minH.add(5);
minH.add(100);
minH.add(1);
// bubbleUp 함수 실행
// 방금 추가한 값 : 10, 부모의 값 : undefined
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 3, 부모의 값 : 10
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 8, 부모의 값 : 3
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 5, 부모의 값 : 10
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 100, 부모의 값 : 5
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 1, 부모의 값 : 8

console.log(minH) // heap { items: [ 1, 5, 3, 10, 100, 8 ] }

console.log(minH.poll()); // 1
console.log(minH.poll()); // 3
console.log(minH.poll()); // 5
console.log(minH.poll()); // 8
console.log(minH.poll()); // 10

console.log(minH) // heap { items: [ 100 ] }

큐(Queue)

• 먼저 들어간 원소가 먼저 나오는 구조
• FIFO(First in First out)구조
• 순서대로 처리해야 경우 => 버퍼

추가

arr.push(item)

삭제

arr.shift()

스택(Stack)

• 나중에 들어간 원소가 먼저 나오는 구조
• LIFO(Last in First out)구조
• 역순으로 처리해야 하는 경우 => 문자열 역순 출력, 연산자 후위 표기법

추가

arr.push(item)

삭제

arr.pop()

해시 테이블(Hash Table)

• 유일한 값(반복되지 않는 값)을 저장하기 위한 자료 구조입니다.
• 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 바꿔 저장한 자료 구조입니다.
• 자바스크립트 객체와 같은 방식으로 key : 값 형식으로 저장됩니다.

해싱이란??

다양한 길이의 키(key) => 고정된 길이 해시(hash)로 바꿔주는 과정을 말합니다

해시 충돌

키(key)는 다른데 해시(hash)값이 똑같은 경우

ex)

11 % 2  == 1
21 % 2 == 1

해시 함수

키(key)를 해시(hash)로 바꿔주는 역할을 한다.
다양한 길이를 가지고 있는 키(key)를 고정된 길이를 가지는 해시(hash)로 변경하여
저장소(해시테이블)를 효율적으로 운영할 수 있도록 도와줍니다.

• 다양한 길이 : [... 3, ... 52 ... 50 ... 5004] - 데이터는 4개지만, 길이가 5005인 배열
  (기존 데이터의 키(key)일 경우)

• 고정된 길이 : [0(50), null, 2(52), 3(3), 4(5004)] - 데이터는 4개지만, 길이가 5인 배열
  (해시함수를 통과한 hash일 경우)

좋은 해시함수 만드는 법

• 결정성 : 동일한 키는 동일한 해시 값을 만들어야 합니다.
• 균일한 분배 : 배열 전체를 최대한 효율적으로 활용해야 합니다.
• 키는 다른데 해시 값이 똑같은 경우 충돌을 피할 수 있게 생성해야 합니다.

해시테이블 장단점

장점

• 작은 저장소(해시 테이블)로 많은 데이터를 효율적으로 관리할 수 있습니다.
• index에 해시값을 사용하여서 모든 데이터를 살피지 않고 검색, 삽입, 삭제를 빠르게 수행할 수 있습니다.
• 길이가 서로 다른 데이터에 대해 일정한 길이로 만들 수 있어서 '데이터 축약' 기능도 수행 가능합니다.

단점

• 순서가 있는 배열에는 어울리지 않습니다.(순서와 상관없이 key를 hash로 바꿔주기 때문)
• 공간 효율성이 떨어집니다.(데이터가 저장되기 전에 미리 공간을 확보해야 하고, 공간이 부족한 경우 채워지지 않기 때문)

해싱 기법

• 선형 탐사 : 키가 다른데 동일한 해시값이 나온경우 hash + 1 하여 저장하는 기법
• 이차 탐사 : 키가 다른데 동일한 해시값이 나온 경우 hash + (중복된 횟수 제곱) 하여 저장하는 기법
• 이중 해싱 : 키가 다른데 동일한 해시값이 나온 경우 hash값을 한번더 해시함수를 이용하여 저장하는 기법

code

function hashTable(size) {
  this.size = size;
  this.keys = this.initArr(size);
  this.values = this.initArr(size);
  this.limit = 0;
}

hashTable.prototype.initArr = function(size) {
  var arr = [];
  for(var i=0; i<size; i++) {
    arr.push(null);
  }
  return arr
}

hashTable.prototype.put = function(key, value) {
  if(this.limit >= this.size) {
    return console.log('더이상 추가 할 수 없습니다.')
  }

  var hashIndex = this.hash(key);

  while(this.keys[hashIndex] !== null) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }

  this.keys[hashIndex] = key;
  this.values[hashIndex] = value;
  this.limit++;
}

hashTable.prototype.get = function(key) {
  var hashIndex = this.hash(key);
  while(this.keys[hashIndex] != key) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }
  return this.values[hashIndex];
}

hashTable.prototype.hash = function(key) {
  if(!Number.isInteger(key)) {
    return console.log('숫자가 아닙니다')
  }
  return key % this.size;
}



var test = new hashTable(13);
test.put(4, "kim");
test.put(13, "lee");
test.put(18, "you");
test.put(33, "heo");
test.put(59, "son");
test.put(82, "jung");
test.put(101, "seo");
test.put(109, "sad");

console.log(test)

// hashTable {
//   size: 13,
//   keys: [
//     13,   null, null, null,
//     4,    18,   82,   33,
//     59,   109,  101,  null,
//     null
//   ],
//   values: [
//     'lee',  null,  null,
//     null,   'kim', 'you',
//     'jung', 'heo', 'son',
//     'sad',  'seo', null,
//     null
//   ],
//   limit: 8
// }

설명

1. HashTable 생성

function hashTable(size) {
  this.size = size;
  this.keys = this.initArr(size);
  this.values = this.initArr(size);
  this.limit = 0;
}

hashTable.prototype.initArr = function(size) {
  var arr = [];
  for(var i=0; i<size; i++) {
    arr.push(null);
  }
  return arr
}

var test = new hashTable(13);

console.log(test)

// hashTable {
//   size: 13,
//   keys: [
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null
//   ],
//   values: [
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null, null, null,
//     null
//   ],
//   limit: 0
// }

2.  추가

// 해시 테이블에 데이터를 추가하는 함수
hashTable.prototype.put = function(key, value) {
  // size == 테이블 최대 크기
  // limit == 현재 테이블 크기
  if(this.limit >= this.size) {
    return console.log('더이상 추가 할 수 없습니다.')
  }

  // 해싱 함수를 호출하여 key값을 => hash값으로 바꿈
  var hashIndex = this.hash(key);

  // 이미 해당 hash값이 있다면 +1 하여 저장
  while(this.keys[hashIndex] !== null) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }

  // 중복되지 않은 해시값이 정해졋을때 hash값 : value 저장하고 현재 테이블 크기도 +1 해줌
  this.keys[hashIndex] = key;
  this.values[hashIndex] = value;
  this.limit++;
}

// key => hash로 바꿔주는 함수
hashTable.prototype.hash = function(key) {
  if(!Number.isInteger(key)) {
    return console.log('숫자가 아닙니다')
  }
  return key % this.size;
}

test.put(4, "kim");
test.put(13, "lee");
test.put(18, "you");
test.put(33, "heo");
test.put(59, "son");
test.put(82, "jung");
test.put(101, "seo");
test.put(109, "sad");

3. 검색

// 해시 테이블에 해당 hash값을 가지고 있는지 검색하는 함수
hashTable.prototype.get = function(key) {
  // 해싱 함수를 호출하여 key값을 => hash값으로 바꿈
  var hashIndex = this.hash(key);

  // 이미 해당 hash값이 있다면 +1하여 검색
  while(this.keys[hashIndex] != key) {
    hashIndex++
    hashIndex = hashIndex%this.size;
  }

  console.log(this.values[hashIndex])
  // 해당 key의 hash값을 찾았을때 value값을 return함
  return this.values[hashIndex];
}

// key => hash로 바꿔주는 함수
hashTable.prototype.hash = function(key) {
  if(!Number.isInteger(key)) {
    return console.log('숫자가 아닙니다')
  }
  return key % this.size;
}

test.get(4, "kim");
test.get(13, "lee");
test.get(18, "you");
test.get(33, "heo");
test.get(59, "son");
test.get(82, "jung");
test.get(101, "seo");
test.get(109, "sad");

병합 정렬(Merge Sort)

• 대표적인 divide and conquer(분할정복)알고리즘을 이용하여 구현한 정렬 알고리즘 입니다.
• 분할 : 해결하고자 하는 문제를 가장 작은 단위로 쪼개는 과정
• 정복 : 가장 작은 단위로 쪼개진 문제들을 해결하고 합치는 과정

구현 방법

• 정렬하고자 하는 배열을 단일 요소를 가진 배열이 될 때 까지 나눕니다.(분할)
• 단일 요소의 배열들을 상황에 맞게 합치면서 정렬합니다.(정복)

장점

• 불규칙한 정렬 상태여도 정렬되는 시간은 동일합니다.
• 안정 정렬에 속합니다.
• 다른 정렬들에 비해 빠른 정렬로 분류됩니다.

단점

• 임시의 배열이 필요하기 때문에 메모리 낭비를 하게 된다
• 배열의 크기가 큰 경우 이동 횟수가 많기때문에 시간적 낭비를 초래할 수 있다.

Code

function merge(leftArr, rightArr) {
  var result = [];
  var leftIndex = 0;
  var rightIndex = 0;

  while(leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if(leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex++]);
    } else {
      result.push(rightArr[rightIndex++]);
    }
  }

  var leftRemain = leftArr.slice(leftIndex);
  var rightRemain = rightArr.slice(rightIndex);

  return result.concat(leftRemain).concat(rightRemain)
}

function mergeSort(arr) {
  if(arr.length == 1) {
    return arr;
  }
  var midNum = Math.floor(arr.length/2);
  var leftArr = arr.slice(0, midNum);
  var rightArr = arr.slice(midNum);

  return merge(mergeSort(leftArr), mergeSort(rightArr))
}

console.log(mergeSort([6,1,23,4,2,3]))

설명

function merge(leftArr, rightArr) {
  var result = [];
  var leftIndex = 0;
  var rightIndex = 0;
  console.log("")
  console.log('정복 함수 실행')
  console.log('left', leftArr, 'right', rightArr)

  console.log("")
  console.log('왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행')
  while(leftIndex < leftArr.length && rightIndex < rightArr.length) {

    if(leftArr[leftIndex] < rightArr[rightIndex]) {
      console.log('result:', result, leftArr[leftIndex], '<', rightArr[rightIndex], '왼쪽 배열 요소 추가')
      result.push(leftArr[leftIndex++]);
    } else {
      console.log('result:', result, leftArr[leftIndex], '>', rightArr[rightIndex], '오른쪽 배열 요소 추가')
      result.push(rightArr[rightIndex++]);
    }
  }

  // slice(index) => index부터 끝까지 추출
  // (만약)
  // leftArr == [2,3,4]
  // leftArr.slice(3) 이면 []빈배열 추출됌
  var leftRemain = leftArr.slice(leftIndex);
  var rightRemain = rightArr.slice(rightIndex);

  console.log('')
  console.log('result, leftArr, rightArr 합치는 과정')
  console.log(result, leftRemain, rightRemain)
  console.log('결과물 : ', result.concat(leftRemain).concat(rightRemain))

  return result.concat(leftRemain).concat(rightRemain)
}

function mergeSort(arr) {
  if(arr.length == 1) {
    return arr;
  }
  var midNum = Math.floor(arr.length/2);
  var leftArr = arr.slice(0, midNum);
  var rightArr = arr.slice(midNum);
  console.log('분할 시작')
  console.log(leftArr, rightArr)
  return merge(mergeSort(leftArr), mergeSort(rightArr))
}

console.log(mergeSort([5,1,33,27,10,2]))

// 1. 첫번째 분할 시작
// [ 5, 1, 33 ] [ 27, 10, 2 ]

// (-------------------- 초기 배열의 왼쪽 부분 -------------------- )

// 분할 시작
// [ 5 ] [ 1, 33 ]
// 분할 시작
// [ 1 ] [ 33 ]
//
// 정복 함수 실행
// left [ 1 ] right [ 33 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 1 < 33 왼쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 1 ] [] [ 33 ]
// 결과물 :  [ 1, 33 ]
//
// 정복 함수 실행
// left [ 5 ] right [ 1, 33 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 5 > 1 오른쪽 배열 요소 추가
// result: [ 1 ] 5 < 33 왼쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 1, 5 ] [] [ 33 ]
// 결과물 :  [ 1, 5, 33 ]

// (---------------- 초기 배열의 오른쪽 부분 ----------------)
// 분할 시작
// [ 27 ] [ 10, 2 ]
// 분할 시작
// [ 10 ] [ 2 ]
//
// 정복 함수 실행
// left [ 10 ] right [ 2 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 10 > 2 오른쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 2 ] [ 10 ] []
// 결과물 :  [ 2, 10 ]
//
// 정복 함수 실행
// left [ 27 ] right [ 2, 10 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 27 > 2 오른쪽 배열 요소 추가
// result: [ 2 ] 27 > 10 오른쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 2, 10 ] [ 27 ] []
// 결과물 :  [ 2, 10, 27 ]
//

// (---------------- 초기 배열의 왼쪽, 오른쪽 부분 정복----------------)
// 정복 함수 실행
// left [ 1, 5, 33 ] right [ 2, 10, 27 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 1 < 2 왼쪽 배열 요소 추가
// result: [ 1 ] 5 > 2 오른쪽 배열 요소 추가
// result: [ 1, 2 ] 5 < 10 왼쪽 배열 요소 추가
// result: [ 1, 2, 5 ] 33 > 10 오른쪽 배열 요소 추가
// result: [ 1, 2, 5, 10 ] 33 > 27 오른쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 1, 2, 5, 10, 27 ] [ 33 ] []
// 결과물 :  [ 1, 2, 5, 10, 27, 33 ]
// [ 1, 2, 5, 10, 27, 33 ]

분할 정복(Divide and Conquer) : 문제를 가장 작은 단위로 분리하고 각각 해결 후 결과를 한곳에 모아서 문제를 해결하는 방식

빠른 정렬(Quick Sort)

• 배열에서 기준점을 구한 후 기준점을 기준으로 배열을 나눕니다.(한쪽에는 기준점보다 큰 항목 다른 한쪽은 기준점보다 작은 항목)
• 분할 정복 방법을 통해 배열을 정렬 합니다.
• 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다.

장점

• 초기에 결정된 피벗(기준점)들은 연산에서 제외되고, 피벗을 통해 나눠진 배열의 데이터들의 불필요한 데이터 이동을 줄여서 시간측면에서 굉장히 빠릅니다.
• 배열 안에서 교환하기 때문에 다른 메모리 공간이 필요하지 않습니다.

단점

• 구현하기 어렵습니다.
• 불안정 정렬입니다.
• 정렬된 배열에서는 불균형 분할에 의해 오히려 수행 시간이 더 오래 걸립니다.

CODE

function quickSort(arr) {
  return quickSortHelper(arr, 0, arr.length-1)
}

function quickSortHelper(arr, left, right) {
  if(left<right) {
    var index = partition(arr, left, right)
    quickSortHelper(arr, left, index-1);
    quickSortHelper(arr, index+1, right)
  }
  return arr
}

function partition(arr, left, right) {
  var pivot = arr[right];
  var i = (left-1);
  for(var j=left; j<=right-1; j++) {
    if(arr[j] <=pivot) {
      i++
      swap(arr, i, j)
    }
  }
  swap(arr, i+1, right)
  return (i+1);
}

function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2]
  arr[index2] = temp;
}

console.log(quickSort([1,7,5,2,3,4]))

설명

function quickSort(arr) {
  return quickSortHelper(arr, 0, arr.length-1)
}

function quickSortHelper(arr, left, right) {
  if(left<right) {
    var index = partition(arr, left, right)

    console.log('초기 기준점(4)을 기준으로 왼쪽 항목 분할')
    quickSortHelper(arr, left, index-1);
    console.log("")

    console.log('초기 기준점에서 오른쪽 항목 분할')
    if(index<right) {
      console.log(`초기 기준점 : 4 left : ${index+1}`)
      console.log(`left가 초기 기준점 오른쪽에 위치해서 높아서 분할 합니다`)
      console.log("")
      quickSortHelper(arr, index+1, right)
    } else {
      console.log(`초기 기준점 : 4 left : ${index}`)
      console.log(`left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서 분할하지 않습니다`)
      console.log("")
    }

  }
  return arr
}

function partition(arr, left, right) {
  console.log('정복 함수 실행')
  console.log(arr, `left : ${left}, right : ${right}`)
  var pivot = arr[right];
  var i = (left-1);
  for(var j=left; j<=right-1; j++) {
    if(arr[j] <=pivot) {
      i++
      console.log(`i : ${i}, j : ${j},  ${arr[j]} < ${pivot}`)
      swap(arr, i, j)
    }
  }
  console.log("")
  console.log(i+1, right)
  swap(arr, i+1, right)
  return (i+1);
}

function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2]
  arr[index2] = temp;
}

console.log(quickSort([1,7,5,2,3,4]))

// 정복 함수 실행
// [ 1, 7, 5, 2, 3, 4 ] left : 0, right : 5
// i : 0, j : 0,  1 < 4
// i : 1, j : 3,  2 < 4
// i : 2, j : 4,  3 < 4
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
// 정복 함수 실행
// [ 1, 2, 3, 4, 5, 7 ] left : 0, right : 2
// i : 0, j : 0,  1 < 3
// i : 1, j : 1,  2 < 3
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
// 정복 함수 실행
// [ 1, 2, 3, 4, 5, 7 ] left : 0, right : 1
// i : 0, j : 0,  1 < 2
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 1
// left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서  분할하지 않습니다
//
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 2
// left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서  분할하지 않습니다
//
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 4
// left가 초기 기준점 오른쪽에 위치해서 높아서 분할 합니다
//
// 정복 함수 실행
// [ 1, 2, 3, 4, 5, 7 ] left : 4, right : 5
// i : 4, j : 4,  5 < 7
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 5
// left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서  분할하지 않습니다
//
// [ 1, 2, 3, 4, 5, 7 ]

삽입 정렬(Insertion Sort)

• 해당 순서의 배열 값을 기존의 배열에 올바른 위치를 찾아 삽입한다.
• 2번째 배열의 값부터 앞쪽의 배열의 값들과 비교하여 삽입할 위치를 정한 후 나머지 값을 한칸씩 뒤로 옮기는 알고리즘이다.
• 최선의 경우 O(N)이라는 빠른 효율성을 가지고 있다. 

장점

• 구현하기 쉽다.
• 정렬된 배열이라면 비교와 교환을 적게 하기 때문에 효율적일 수 있다.
• 배열 안에서 교환방식으로 다른 메모리 공간을 필요로 하지 않는다. 

단점

• 최악의 경우 많은 값들의 이동을 필요로한다.
• 배열의 길이가 길고 비교할 값이 많다면 비효율적이다.

CODE

function insertionSort(arr) {
    var store = 0;
    for(var i=0; i<arr.length; i++) {
      store = arr[i]
      for(var j=i-1; j>-1 && arr[j]>store; j--) {
        arr[j+1] = arr[j]
      }
      arr[j+1] = store;
    }
    return arr
}

console.log(insertionSort([6,4,13,2,1]))

설명

function insertionSort(arr) {
    var store = 0;
    for(var i=0; i<arr.length; i++) {
      console.log(arr)
      console.log(`배열 ${i}번째 인덱스 탐색시작!!!`)
      console.log(" ")
      store = arr[i]
      for(var j=i-1; j>-1 && arr[j]>store; j--) {
        arr[j+1] = arr[j]
        console.log(`${i}번째 값 ${j}번째 위치로 삽입`)
        console.log(arr, i, j)
      }
      console.log("끝!!!")
      console.log(" ")
      arr[j+1] = store;
    }
    return arr
}

console.log(insertionSort([6,4,13,2,1]))
// console.log(insertionSort([1,2,3,4,5]))

// [ 6, 4, 13, 2, 1 ]
// 배열 0번째 인덱스 탐색시작!!!
// 끝!!!
// 
// [ 6, 4, 13, 2, 1 ]
// 배열 1번째 인덱스 탐색시작!!!
// 
// 1번째 값 0번째 위치로 삽입
// [ 6, 6, 13, 2, 1 ] 1 0
// 끝!!!
// 
// [ 4, 6, 13, 2, 1 ]
// 배열 2번째 인덱스 탐색시작!!!
// 끝!!!
// 
// [ 4, 6, 13, 2, 1 ]
// 배열 3번째 인덱스 탐색시작!!!
// 
// 3번째 값 2번째 위치로 삽입
// [ 4, 6, 13, 13, 1 ] 3 2
// 3번째 값 1번째 위치로 삽입
// [ 4, 6, 6, 13, 1 ] 3 1
// 3번째 값 0번째 위치로 삽입
// [ 4, 4, 6, 13, 1 ] 3 0
// 끝!!!
// 
// [ 2, 4, 6, 13, 1 ]
// 배열 4번째 인덱스 탐색시작!!!
// 
// 4번째 값 3번째 위치로 삽입
// [ 2, 4, 6, 13, 13 ] 4 3
// 4번째 값 2번째 위치로 삽입
// [ 2, 4, 6, 6, 13 ] 4 2
// 4번째 값 1번째 위치로 삽입
// [ 2, 4, 4, 6, 13 ] 4 1
// 4번째 값 0번째 위치로 삽입
// [ 2, 2, 4, 6, 13 ] 4 0
// 끝!!!
// 

// 결과!!!!
// [ 1, 2, 4, 6, 13 ]

선택 정렬(Selection Sort)

• 순서대로 해당 위치마다 (최솟값 or 최댓값)을 찾아서 넣는 알고리즘
• 오름차순 정렬 : 배열의 왼쪽부터 순서대로 최소값을 찾는다
• 내림차순 정렬 : 배열의 왼쪽부터 순서대로 최대값을 찾는다

시간 복잡도 : O(n^2)   => n(n-1)/2

공간 복잡도 : O(N)

장점 

• 구현하기 쉽다
• 비교는 여러번 수행하지만 교환 횟수는 적기 때문에 교환이 많이 일어나야 하는 정렬에 비해 효율적이다
• 배열 안에서 교환하기 때문에 다른 메모리 공간이 필요없다.

단점

• 시간 복잡도 측면에서 비효율적이다.
• 불안정한 정렬이다

function selectionSort(arr) {
  var min = 0;
  var temp = 0;
  var count = 0;

  for(var i=0; i<arr.length; i++) {
    min = i //(arr[0] ~ arr.length-1)순서대로 최솟값을 구하기위해서 min에 i를 넣는다
    for(var j=i+1; j<arr.length; j++) {
      count++
      if(arr[j]<arr[min]) {
        min = j
        console.log(`${i}번째 위치에 최솟값 ${j}번째에서 찾음`)
      }
      if(i != min) {
        temp = arr[i]
        arr[i] = arr[min]
        arr[min] = temp
        console.log(`${i}번째 위치에 최솟값 ${j}번째와 교환`)
      }
      console.log(`${arr}, i : ${i}, j : ${j}, 횟수 : ${count} 최솟값 : ${min}`)
    }
    console.log(`${i}번째 최솟값 탐색 끝`)
    console.log("")
  }
  return arr
}
console.log(selectionSort([2,13,22,6,1]))

// 2,13,22,6,1, i : 0, j : 1, 횟수 : 1 최솟값 : 0
// 2,13,22,6,1, i : 0, j : 2, 횟수 : 2 최솟값 : 0
// 2,13,22,6,1, i : 0, j : 3, 횟수 : 3 최솟값 : 0
// 0번째 위치에 최솟값 4번째에서 찾음
// 0번째 위치에 최솟값 4번째와 교환
// 1,13,22,6,2, i : 0, j : 4, 횟수 : 4 최솟값 : 4
// 0번째 최솟값 탐색 끝
// 
// 1,13,22,6,2, i : 1, j : 2, 횟수 : 5 최솟값 : 1
// 1번째 위치에 최솟값 3번째에서 찾음
// 1번째 위치에 최솟값 3번째와 교환
// 1,6,22,13,2, i : 1, j : 3, 횟수 : 6 최솟값 : 3
// 1번째 위치에 최솟값 4번째에서 찾음
// 1번째 위치에 최솟값 4번째와 교환
// 1,2,22,13,6, i : 1, j : 4, 횟수 : 7 최솟값 : 4
// 1번째 최솟값 탐색 끝
// 
// 2번째 위치에 최솟값 3번째에서 찾음
// 2번째 위치에 최솟값 3번째와 교환
// 1,2,13,22,6, i : 2, j : 3, 횟수 : 8 최솟값 : 3
// 2번째 위치에 최솟값 4번째에서 찾음
// 2번째 위치에 최솟값 4번째와 교환
// 1,2,6,22,13, i : 2, j : 4, 횟수 : 9 최솟값 : 4
// 2번째 최솟값 탐색 끝
// 
// 3번째 위치에 최솟값 4번째에서 찾음
// 3번째 위치에 최솟값 4번째와 교환
// 1,2,6,13,22, i : 3, j : 4, 횟수 : 10 최솟값 : 4
// 3번째 최솟값 탐색 끝
// 
// 4번째 최솟값 탐색 끝