Immersive #11 first test

Immersive 3주차 4가지 sprint가 끝났습니다. 언어에 익숙해지고 여러 컴퓨터공학의 이론 자료구조 알고리즘, 상속에 대해 알아보는 sprint였습니다. 4가지 sprint가 끝나고 공부한 내용에 대해서 immersive 첫번째 시험이 주어졌습니다. 이번 포스팅은 첫번째 시험을 보면서 막혔던 부분과 문제를 어떻게 해결 했는지 알아보려고 합니다.

< 오늘 알게 된 것 > 🤣

• psuedo-classical inheritance에서의 상속 받은 함수 사용 방법

• function의 사용

1. ds-queue

큐의 기본적인 삽입과 삭제에 대해 구현 해보는 문제가 주어졌습니다.

var Queue = function() {
  this.storage = {}; // queue의 저장소 
  this.rear = 0; // queue의 꼬리 
  this.front = 0; // queue의 머리 
};

Queue.prototype.add = function(value) {
  this.rear++; 
  this.storage[this.rear] = value;
};

Queue.prototype.remove = function() {
  if (this.rear === this.front) {
    return undefined;
  }
  this.front++;
  return this.storage[this.front];
};

Queue문제는 기존에 많이 숙달했던 부분이기 때문에 큰 문제 없이 해결 할 수 있었습니다.

2. js-inheritance-pseudo-classical

기존의 functional 코드가 주어지고 functional 코드를 pseudo-classical로 구현 해주는 문제가 출제 되었습니다.

var Horse = function(name) {
  this.name = name;
};

Horse.prototype.goSomewhere = function(destination) {
  return this.name + " is galloping to " + destination + "!";
};

var FlyingHorse = function(name, color) {
  Horse.call(this);
  this.name = name;
  this.color = color;
};

FlyingHorse.prototype = Object.create(Horse.prototype);

FlyingHorse.prototype.constructor = FlyingHorse;

FlyingHorse.prototype.goSomewhere = function(destination, milesToDestination) {
  if (milesToDestination < 10) {
    return Horse.prototype.goSomewhere.call(this, destination); //  잘 몰랐던 부분 
  } else {
    return this.name + " is flying to " + destination + "!";
  }
};

문제를 해결 하는데에 있어서 기존의 Horse를 FlyingHorse에 상속 시켜 주고 Horse함수를 FlyingHorse에서 사용하는데 있어서 개념이 부족해서 문제를 해결하는 데 애를 조금 먹었습니다.

Horse.prototype.goSomewhere.call의 작성을 통해 해결 할 수 있었는데 call메소드를 사용하는데에 있어서 call(this)로만 사용을 하다보니 call 메소드의 개념을 잊어버려 두번째로 헤메게 되었습니다. call(this)를 call(this,desitination) 매개변수를 받게 해줌으로 처리를 하였습니다.

3. this-keyword

this의 개념을 이용하여 문제를 접근하고 해결하는 문제가 출제되었습니다. this키워드에 대해 다시 찾아보게 되는 문제였습니다.

var sport = {
  name: "basketball",
  players: [
    { name: "LeBron James", age: 31 },
    { name: "Kevin Durant", age: 28 }
  ],
  playerNames: function() {
    let result = [];
    for (let i = 0; i < this.players.length; i++) {
      result.push(`${this.players[i].name} plays ${this.name}`);
    }
    return result;
  }
};

// sport.playerNames(); -> ["Lebron James plays basketball", "Kevin Durant plays basketball"]

4. tree-map

이전에 im-self-assignment 동일한 문제입니다. 기존의 tree에 자식을 추가하는 tree의 value에 map 메소드를 적용하는 문제가 출제 되었습니다.

var Tree = function(value) {
  this.value = value;
  this.children = [];
};

Tree.prototype.addChild = function(value) {
  let childNode = new Tree(value);
  this.children.push(childNode);
};

Tree.prototype.map = function(callback) {
  let newNode = new Tree();
  // map 함수
  newNode.value = callback(this.value);
  //자식이 있는 경우 
  if (this.children) {
    for (let i = 0; i < this.children.length; i++) {
      newNode.children[i] = this.children[i].map(callback);
    }
  }
  return newNode;
};

문제를 푸는데에 있어서 재귀함수의 사용을 통해 문제를 해결 하였습니다.

5. algo-complexity

주어진 문제에 있어서 시간 복잡도를 계산하는 문제가 출제 되었습니다. 시간 복잡도 계산 문제를 접할 계기가 많이 없었는데 이번 계기로 접하게 되었습니다.

1) sumSquaresTimeComplexity

var sumSquares = function(array) {
  return array.reduce(function(memo, val) {
    return memo + (Math.pow(val, 2));
  });
};

* Complexity: 
  1) 기본단위: memo + (Math.pow(val,2))
  시간 복잡도를 계산하기 위해서는 먼저 기본 단위를 설정해야 합니다.
  memo + (Math.pow(val,2))의 계산에 드는 시간은 상수입니다.
  또한 본 계산은 배열의 길이가 길어질 때 가장 큰 리소스를 소모합니다.
  따라서 본 계산을 기본단위로 설정하는 것이 타당합니다.
  2) n의 기준: array.length
  배열의 길이가 n이 됩니다.
  
  3) 시간복잡도: O(n);
  기본단위에 해당하는 계산은 배열의 길이(n)만큼 반복됩니다.
  따라서 아래 알고리즘의 시간복잡도는 O(n)입니다.

2) nthPowerTimeComplexity

var nthPower = function(base, exponent) {
  // Base case:
  if (exponent === 0) {
    return 1;
  // If exponent is odd
  } else if (exponent % 2 !== 0) {
    return base * nthPower(base, exponent - 1);
  // If exponent is even
  } else {
    return nthPower(base * base, exponent / 2);
  }
};

 * Complexity:
  1) 기본단위: nthPower함수 자체
  nthPower함수는 재귀함수이며, 이 함수는 1회 시행 시 항상 비슷한 리소스를 요구합니다.
  따라서 아래 함수에서는 nthPower함수 자체가 시간복잡도 측정의 기본단위입니다.    
  
  2) n의 기준: exponent;
  
  3) 시간복잡도: O(log(n));
  exponent는 홀수일 때 1씩 줄어들고, 짝수일 때 절반으로 줄어듭니다.
  exponent가 10이라면 10, 5, 4, 2, 1, 0 순으로 exponent가 줄어듭니다.
  exponent가 1000이라면 1000, 500, 250, 120, 60, 30, 15, 14, 7, 6, 3, 2, 1, 0 순으로 exponent가 줄어듭니다.
  이때 exponent는 세제곱배 증가했지만 계산횟수는 약 3배만 증가했습니다.
  따라서 시간복잡도는 O(long(n))입니다.

3) rockPaperScissorsTimeComplexity

var rockPaperScissors = function(rounds) {
  var sequences = [];
  var plays = ['rock', 'paper', 'scissors'];

  var generate = function(sequence, round) {
    // Base case:
    if (round === rounds) {
      sequences.push(sequence);
    } else {
      plays.forEach(function(play) {
        generate(sequence.concat(play), round + 1);
      });
    }
  };

  generate([], 0);
  return sequences;
};

 * Complexity:
  * Complexity:
  1) 기본단위: generate함수
  generate함수는 재귀함수이며, 이 함수는 1 회 시행 시 항상 비슷한 리소스를 요구합니다.
  따라서 아래 함수에서는 generate함수 자체가 시간복잡도 측정의 기본단위입니다.
 
  2) n의 기준: rounds;
  
  3) 시간복잡도: O(3^n);
  rounds가 1증가할 때마다 generate함수의 실행횟수가 3배씩 증가합니다.
  generate함수는 sequence가 패러미터로 주어졌을 때
    해당 sequece에 각 가위바위보의 수를 순서대로 추가하여
    round가 rounds에 수렴할 때까지 반복합니다.
  예를 들어, 빈 배열이 주어지고 rounds가 1일때,
    generate함수는 ['rock'], ['paper'], ['scissors']를 다시 generate함수에 넣어 실행합니다.
    이때 1회 시행하면 round가 rounds와 같기 때문에 새로 생성된 sequence가 sequences에 답기지만
    만일 n 이 1보다 크다면 각 시퀀스가 각각 다시 3가지 경우로 나뉘어 증가합니다.
  따라서 아래 알고리즘의 시간복잡도는 O(3^n)입니다.