[자바스크립트로하는 자료구조와 알고리즘] 6- 10장

// 6-10장
// 6장 자바스크립트 객체
let javaScriptObject = {};
let testArray = [1,2,3,4];
javaScriptObject.array = testArray;
javaScriptObject.title = 'Algorithms';
console.log(javaScriptObject);

function ExampleClass() {
  this.name = "JavaScript";
  this.sayName = function() {
    console.log(this.name)
  }
}

let example1 = new ExampleClass();

example1.sayName();


function ExampleClass2() {
  this.name = "JavaScript";
  this.array = [1,2,3,4,5];
}

ExampleClass2.prototype.sayName = function() {
    console.log("prototype", this.name)
}

let example2 = new ExampleClass2();

example2.sayName();

function ExampleClass3(name, size) {
  let privateName = name;
  let privateSize = size;
  
  this.getName = function() { return privateName }
  this.setName = function(name) { privateName = name; }
  
  this.getSize = function() { return privateSize; }
  this.setSize = function(size) { privateSize = size; }
}

let example = new ExampleClass3("Sammie", 3);
example.setSize(12);
console.log(example.privateName);
console.log(example.getName());
console.log(example.size);
console.log(example.getSize());


function Animal(name, animalType){
  this.name = name;
  this.animalType = animalType;
}
Animal.prototype.sayName = function(){ console.log(this.name); }
Animal.prototype.sayAnimalType = function(){ console.log(this.animalType); }

function Dog(name){
  Animal.call(this, name, "Dog")
}

Dog.prototype = Object.create(Animal.prototype);
console.log("hello", Dog.prototype);


let myAnimal = new Animal("ditto", "pokemon");
myAnimal.sayName();
myAnimal.sayAnimalType();

let myDog = new Dog("candy", "dog");
myDog.sayName();
myDog.sayAnimalType();


// 7장 자바스크립트 메모리 관리
function someLargeArray() {
  return new Array(1000000);
}

let exampleObj = {
  'prop1': someLargeArray(),
  'prop2': someLargeArray()
}

function printProperty(prop){
  console.log(prop);
}

printProperty(exampleObj['prop1']);

// 8장 재귀
// 기저조건(종료조건)이 꼭 있어야한다. 
function countDownToZero(n){
  if(n < 0){
    return;
  }
  
  console.log(n);
  countDownToZero(n-1);
}

countDownToZero(12);

// 분할 정복 방식
const cache = {};
cache[0] = 0;
cache[1] = 1;
function getNthFibo(n){
  if(n <= 1){
    return n;
  }
  if(cache[n]){
    return cache[n];
  }
  const cur = getNthFibo(n-1) + getNthFibo(n-2);
  cache[n] = cur;
  return cur;
}

getNthFibo(10);

function getNthFiboBetter(n, lastlast, last){
  if(n === 0){
    return lastlast;
  }
  if(n === 1){
    return last;
  }
  return getNthFiboBetter(n-1, last, lastlast+last)
}

function pascalTriangle(row, col){
  if(col === 0){
    return 1;
  }
  
  if(row === 0){
    return 0;
  }
  
  return pascalTriangle(row-1, col) + pascalTriangle(row-1, col-1);
}

console.log(pascalTriangle(5, 2));

// 재귀 알고리즘은 점화식을 통해서 분석한다. 

function base10ToString(n){
  let binaryString = "";
  function base10ToStringHelper(n){
    if(n < 2) {
      binaryString += n;
      return;
    }
    
    base10ToStringHelper(Math.floor(n / 2)); // 나누는게 다끝나고 나서 나머지합산이 처리된다
    base10ToStringHelper(n % 2);
  }
  base10ToStringHelper(n);
  
  return binaryString;
}

console.log(base10ToString(232));

// 배열의 모든 순열 출력하기 
function swap(strArr, index1, index2){
  let temp = strArr[index1];
  strArr[index1] = strArr[index2];
  strArr[index2] = temp;
}

function permute(strArr, begin, end){
  if(begin === end){
    console.log(strArr);
    return;
  }
  
  for(let i = begin; i < end + 1; i++){
    swap(strArr, begin, i);
    permute(strArr, begin+1, end);
    swap(strArr, begin, i);
  }
}

function permuteArray(strArr){
  permute(strArr, 0, strArr.length - 1);
}

// permuteArray(["A", "B", "C", "D"]);

// 객체 펼치기
let dic = {
  "key1": "1", 
  "key2": {
    "a": "2", 
    "b": "3", 
    "c": {
      "d": "3", 
      "e": "1"
    }
  }
}

// 문제를 쪼개다가, 입력이 객체가 아닐때 종료한다
function flattenDictionary(dictionary){
  let flattenedDictionary = {};
  function flattenDictionaryHelper(dictionary, propName){
    if(typeof dictionary !== 'object'){
      flattenedDictionary[propName] = dictionary;
      return;
    }
    
    for(const [key, value] of Object.entries(dictionary)){
      if(propName === ""){
        flattenDictionaryHelper(dictionary[key], propName + key);
      }else{
        flattenDictionaryHelper(dictionary[key], propName + "." + key);
      }
    }
  }
  
  flattenDictionaryHelper(dictionary, "");
  return flattenedDictionary;
}


console.log(flattenDictionary(dic));


function isPalindromeRecursive(word){
  return isPalindromeHelper(word, 0, word.length-1);
}

function isPalindromeHelper(word, beginPos, endPos){
  if(beginPos >= endPos) return true;
  
  if(word.charAt(beginPos) !== word.charAt(endPos)){
    return false;
  }
  
  return isPalindromeHelper(word, beginPos+1, endPos-1);
}

isPalindromeRecursive("hi");

// 9장 집합
function intersectSets(setA, setB){
  const intersection = new Set();
  for(let elem of setB){
    if(setA.has(elem)){
      intersection.add(elem);
    }
  }
  return intersection;
}

const setA = new Set([1, 2, 3, 4]);
const setB = new Set([2, 3]);

console.log(intersectSets(setA, setB));

function isSuperset(setA, subset){
  for(let elem of subset){
    if(!setA.has(elem)){
      return false;
    }
  }
  return true;
}

let setAA = new Set([1, 2, 3, 4]);
let setBB = new Set([2, 3]);
let setC = new Set([5]);

console.log(isSuperset(setAA, setBB));
console.log(isSuperset(setAA, setC));

function unionSet(setA, setB){
  const union = new Set(setA);
  for(let elem of setB){
    union.add(elem);
  }
  
  return union;
}

// console.log(unionSet(setAA, setBB))
// console.log(unionSet(setAA, setC))
// console.log(unionSet(setBB, setC))

function differenceSet(setA, setB){
  const difference = new Set(setA);
  for(let elem of setB){
   difference.delete(elem);
  }
  
  return difference;
}

console.log(differenceSet(setAA, setBB))
console.log(differenceSet(setAA, setC))
console.log(differenceSet(setBB, setC))

function checkDuplicates(arr){
  const mySet = new Set(arr);
  return mySet.size < arr.length;
}

console.log(checkDuplicates([1,2,3,4,5,6]));
console.log(checkDuplicates([1,1,2,3,4,5,6]))

function uniqueList(arr1, arr2){
  const mySet = new Set(arr1.concat(arr2));
  return Array.from(mySet);
}

uniqueList([1,1,2,2], [2,3,4,5]);

// 10장 검색과 정렬

function binarySearch(array, n){
  let lowIndex = 0, highIndex = array.length - 1;
  
  while(lowIndex <= highIndex){
    let midIndex = Math.floor((highIndex + lowIndex) / 2);
    
    if(array[midIndex] === n){
      return midIndex;
    }
    
    if(n > array[midIndex]){
      lowIndex = midIndex + 1;
      continue;
    }
    
    highIndex = midIndex - 1;
  }
  
  return -1;
}

console.log(binarySearch([1,2,3,4], 4));
console.log(binarySearch([1,2,3,4], 5));

// function swap(strArr, index1, index2){
//   let temp = strArr[index1];
//   strArr[index1] = strArr[index2];
//   strArr[index2] = temp;
// }

// bubble sort
function bubbleSort(array){
  // i번째까지 체크(매 루프마다 끝나는데가 하나씩 준다
  for(let i = array.length - 1; i > 0; i--){
    for(let j = 0; j < i; j++){
      if(array[j] > array[j+1]){
        swap(array, j, j+1);
      }
    }
  }
  return array;
}

console.log(bubbleSort([6, 1, 2, 3, 4, 5]));

function selectionSort(items){
  let len = items.length;
  let min = 0;
  
  for(let i = 0; i < len; i++){
    min = i; // 항상 제일앞이 최솟값이라고치고, 이 위치에다가 가져온다. 
    for(let j = i+1; j < len; j++){
      if(items[j] < items[min]){
        min = j;
      }
    }
    if(i !== min){
      swap(items, i, min);
    }
  }
  
  return items;
}

console.log(selectionSort([6, 1, 2, 3, 4, 5]));

function insertSort(items){
  let len = items.length; // 배열의 항목수
  let value = 0; // 현재 비교중인 값
  // let i = 0; // 정렬되지 않은 부분의 인덱스
  // let j = 0; // 정렬된 부분까지의 인덱스
  
  for(let i = 0; i < len; i++){
    value = items[i]; // value는 현재선택된값
    
    let j = i-1;
    while(j >= 0 && items[j] > value){
      // value가 들어갈자리를 계속 한칸씩 밀어준다
      items[j+1] = items[j];
      j--;
    }
    items[j+1] = value;
  }
  return items;
}

console.log(insertSort([6, 1, 2, 3, 4, 5]));

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

function quickSortHelper(items, left, right){
  if(items.length > 1){
    let index = partition(items, left, right); // 쪼갠다  
    if(left < index - 1){
      quickSortHelper(items, left, index-1);
    }
    if(index < right){ // 계속 pivot기준도 어딘가에 포함을 시켜준다. 
      quickSortHelper(items, index, right)
    }
  }
  return items;
}

function partition(array, left, right){
  let pivot = array[Math.floor((left+right) / 2)];
 
  while(left <= right){
    while(pivot > array[left]){
      left++; // pivot보다 큰데서 멈춘다
    }
    
    while(pivot < array[right]){
      right--; // pivot보다 작은데서 멈춘다
    }
    
    if(left <= right){
      let temp = array[left];
      array[left] = array[right];
      array[right] = temp;
      left++;
      right--;
    }
  }
  return left;
}

console.log("quick", quickSort([6, 1, 3, 2, 5, 4]));
console.log(quickSort([6, 1, 23, 4, 2, 3]));

// quickSelect: 정렬되지 않은 목록에서 k번째로 작은 항목을 찾는 선택 알고리즘
// quick소트처럼 하는데 반쪽씩만 재귀적으로 수행한다. 
const array = [1, 3, 3, -2, 3, 14, 7, 8, 1, 2, 2];

function quickSelectInPlace(A, l, h, k){
  const p = partition(A, l, h);
  if(p === (k-1)){
    return A[p];
  }
  if(p > k-1){
    // 앞에
    return quickSelectInPlace(A, l, p-1, k);
  }else{
    // 뒤에
    return quickSelectInPlace(A, p+1, h, k);
  }
}

quickSelectInPlace(array, 0, array.length-1, 5);
quickSelectInPlace(array, 0, array.length-1, 10);

// merge소트
function merge(leftA, rightA){
  const results = [];
  let leftIndex = 0, rightIndex = 0;
  
  while(leftIndex < leftA.length && rightIndex < rightA.length){
    if(leftA[leftIndex] < rightA[rightIndex]){
      results.push(leftA[leftIndex++]);
    }else{
      results.push(rightA[rightIndex++]);
    }
  }
  
  let leftRemains = leftA.slice(leftIndex), 
      rightRemains = rightA.slice(rightIndex);
  return results.concat(leftRemains).concat(rightRemains);
}

function mergeSort(array){
  if(array.length < 2){
    return array;
  }
  
  let midpoint = Math.floor((array.length)/2),
  leftArray = array.slice(0, midpoint),
  rightArray = array.slice(midpoint);
  
  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

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


// 계수 정렬
function countSort(array){
  const hash = {}, countArr = [];
  
  for(let i = 0; i < array.length; i++){
    if(!hash[array[i]]){
      hash[array[i]] = 1;
    }else{
      hash[array[i]]++;
    }
  }
  
  for(let key in hash){
    for(let i = 0; i < hash[key]; i++){
      countArr.push(parseInt(key));
    }
  }
  
  return countArr;
}

countSort([6,1,23,2,3,2,1,2,2,3,3,1,123,123,4,2,3]);

 

정렬은 어떻게 할때마다 조금씩 까먹는건지, 아주 놀라울따름... 이런 자료구조들을 얼른 좀 더 잘다룰수 있길.