: 그래프는 노드(node or vertaxl,정점)와 간선(edge)로 구성된 비선형 자료구조이다. 노드들을 도시라고 가정했을 때 간선은 도시들을 연결해주는 도로인 셈이다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할수 있다.

인접 행렬(Adjacent Matrix)

: 2차원 배열로 그래프의 연결 관계를 표현한 것. 각 연결된 노드는 1로, 연결되지 않는 노드는 0으로 표현한 행렬.위 그래프를 인접행렬로 표현하면 다음과 같다. (간선은 방향이 없다고 가정)

• 모든 노드 간의 관계를 나타내야 하므로 불필요한 메모리 공간을 차지한다는 단점이 있다. (노드 수의 비해 연결된 간선 수가 적다면 불필요한 메모리 공간을 매우 많이 차지함)

인접 리스트(Adjacent List)

: 노드 간에 연결관계를 리스트 형식으로 표현하는 것. 튜플형태로 배열로 구현할 수도 있고, 객체로 구현할 수 있다. 나는 map 객체를 이용 하기도 한다. JavaScript 객체로 그래프를 구현하면 아래와 같다. 노드를 key값으로 연결된 노드 리스트를 배열로 value값으로 지정해 준다.

let adjacentdList = {
  0: [1,4],
  1: [0,2,3,4],
  2: [1,3],
  3: [1,2,4],
  4: [0,1,3]
}

그래프를 이용한 알고리즘: 여행경로

문제: 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. (문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43164)

Input 예시: [['ICN', 'SFO'], ['ICN', 'ATL'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL','SFO']]

Ouput 예시: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']

function solution(tickets) {

    // create airports array (will be Nodes)
    const airports = [];
    for(let ticket of tickets){
        const origin = ticket[0];
        const destination = ticket[1];
        if(!airports.includes(origin)){
            airports.push(origin)
        }
        if(!airports.includes(destination)){
            airports.push(destination)
        }
    }

    const map = new Map();

    function addNode(airport){
        map.set(airport, []);
    }

    function addEdge(origin, destination){
        map.get(origin).push(destination);
    }

    // create the graph using MAP 
    // key:origin airport / value:destination
    airports.forEach(addNode);
    tickets.forEach(ticket => addEdge(...ticket));

    for(let airport of airports){
        map.get(airport).sort();
    }

    // DFS
    let routes = [];
    function dfs(start){
        routes.push(start);
        if(map.get(start).length === 0){
            return;
        }
        const destination = map.get(start).shift();
        dfs(destination);
    }

    dfs('ICN');
    return routes;

}

풀이) 우선 작성한 위 코드로는 일부 테스트를 통과하지 못했다 :( 어떤 input일때 실패하는지 알 수 없어 왜 안되는지 모르겠다. 계속 건드려도 해결하지 못해 일단 이 코드라도 정리해둔다.

먼저 mapobject를 이용해 주어진 항공권에서 출발하는 공항을 node(key)로, 도착지를 edge(value)로 하는 graph를 구현했다.

이후 이 그래프에서 DFS(deapth-first search, 깊이 우선 탐색)를 이용해 여행경로를 탐색했다.

Subclassing - prototype chain

JavaScript는 원래 객체지향을 염두에 두고 만들어진 언어가 아니다. prototype 기반 언어이다. javascript에서 어떻게 객체지향 방법론을 구현할지... 프로토타입은 원형객체(original form)이다. 즉 복제품을 만들기위한 설계도인 셈이다. 클래스 생성 시 prototype이 생성된다.

function Car(brand, name, color) {
  this.brand = brand; 
  this.name = name;
  this.color = color;
} // ES6 클래스에서 constructor(생성자)의 역할 -> instance 초기화시 실행...
Car.prototype.dirve = function() {
  console.log(this.name + '가 운전을 시작합니다');
}
let avante = new Car('hyundai', 'avante', 'black'); // this가 avante가됨.
avante.color; // black
avante.dirve(); // avante가 운전을 시작합니다.

• this: 함수 scope마다 생성되는 고유한 실행 context(excution context). 인스턴스 생성 시 해당 인스턴스가 this가 됨.
• prototype: 프로토타입은 할당이 가능하다. 따라서, 프로토타입안에 자신이 만든 메소드를 할당할 수 있다.

Object.create();

: 인자로 들어온 프로토타입을 바탕으로 프로토타입 복사본을 만든다. 이 메소드를 사용하는 이유는 2개의 프로토타입이 있을 때, 하나의 프로토타입이 다른 하나의 프로토타입을 참조하고 싶을때 사용된다. Object.create() 메소드를 활용하면 참조된 프로토타입에 영향없이 참조받은 프로토타입에 새로운 메소드 추가가 가능하다. Object.create() 메소드 없이 하나의 프로토타입에 다른하나의 프로토타입을 바로 참조하게 되면 서로 영향을 끼치게된다.

• O: a.prototype = Object.create(b.prototype)
• X: a.prototype = b.prototype

function Human(name) {
  this.name = name;
};

function Student(){
};

Student.prototype = Object.create(Human.prototype);
// 정확한 prototype chain 구현을 위해 prototype의 constructor를 다시 Student로 바꿔주는 작업을 해야함 (javascript는 애초에 OOP 고려하지 않고 만들어져서..)
Student.prototype.constructor = Student; 
Student.prototype.learn = function(){console.log('learning...')};
Human.prototype.sleep = function(){console.log('zzz')};
Human.prototype // 여기에는 learn 메소드 없음. but Student에서 sleep메소드 사용가능

let student1 = new Student();
student1.learn() // learning...
student1.sleep() // zzz

여기서 Student의 this가 Human까지 가지 않는다. 따라서 Human까지 this를 전달해주기 위해 아래와 같이 call method를 사용해야 한다.

function Student(){
  Human.call(this, name);
};

Class (ES6)

: 위에서 본 prototype chain을 쉽게 구현하기 위해 ES6에서 class 키워드가 등장했다. 이후 위에 방법은 legacy가 돼버렸다.

class Human {
  constructor(name) {
    this.name = name;
  }
  sleep() {
  }
}

var woojun = new Human('woojun');

class Student extends Human {
    /* 생략가능 */
  constructor(name) {
    super(name); // Human의 속성과 메소드를 호출할 때 사용됨.
  }
     /* 여기까지 */
  learn() {
  }
  // sleep() 메소드 재정의 가능
}
var john = new Student('john');
john.learn();
john.sleep();

• 자식 클래서에서 부모 클래스어 속성이 같은 경우 constructors는 생략이 가능하다.

프로그래밍 언어에는 3가지 종류가 있다. 기계어는 컴퓨터의 CPU가 멍령을 처리할 수 있게 0과 1로 구성된 언어이다. 따라서 사람이 이해하기는 너무 복잡해 이를 이용해 프로그래밍을 구축하기 어렵다. 따라서 이를 사람이 이해하기 쉽게 즉, 자연어와 비슷하게 만들어진 언어가 고급언어이다.

• Machine Langauge(기계어)
• Assembly Language(어셈블리어)
• High-Level Language(고급언어)

우리가 사용하는 대부분의 프로그래밍 언어가 고급언어에 속한다. 어셈블리어는 고급언어가 기계어로 바뀌는 과정에서 사용되는 언어이다. 고급언어로 코딩을 하면 이를 1) 컴파일러를 통해 어셈블리어로 변환하고, 2) 어셈블리어를 어셈블러를 통해 기계어로 바꾸는 작업을 해야 비로소 우리가 짠 코드를 컴퓨터가 이해하고 처리할 수 있다.

⚙️ 객체지향 언어의 특징

절차지향 언어(Process-oriented Programming) : 순차적으로 처리되는 것이 중요시되는 언어로써 객체지향 언어에 비해 처리 속도가 빠르다는 특징이있다. 반면에 순서를 반드시 지켜야 되고, 코드를 재사용하기 어렵다. 이러한 이유로 유지보수가 어렵다는 단점이 있다.

: 객체지향 언어(Object-oriented Programming)은 절차지향 언어와 달리 코드를 기능별로 묶어 모듈화를 한다. 이로써 중복으로 연산하지 않고 모듈 재활용이 가능하다. 이로써 코드의 유지보수가 수월하다는 장점이 있다.

객체지향 언어의 대표적인 특징으로는 4가지가 있다.

1. Abstraction
2. Encapsulation
3. Inheritance
4. Polymorphism

1. Abstraction: 추상화

• 구체적인것은 숨긴 채 대표적인 것만 나타냄
• 예를들어 핸드폰으로 통화를 할때 핸드폰에 전화번호만 입력하면 전화가 간다. 핸드폰 화면에는 상대방의 전화번호정도만 보인다. 이 전화가 어떠한 원리로 상대방과 통화를 가능하게끔 하는지는 모른다. 이것이 abstraction이다.
• 즉, 전화라는 class를 정의하는 것 = 추상화

2. Encapsulation: 캡슐화

• Method와 data를 하나의 캡슐(class)에 저장하는 것
• Encapsulation = Abstraction + Data Hiding

3. Inheritance: 상속

• 부모 객체의 속성과 method를 물려받는 것
• 예를들어 iphone, galaxy 등 여러 휴대폰이 있을때 전화라는 class가 갖는 속성과 method를 그대로 물려받아 사용하는 것.
• 더해서 전화라는 부모 객체가 갖지 않는 기능(영상통화기능)도 추가할 수도 있다.(extends)
• 상속으로 인해 함수의 재사용성이 크게 증가한다.

4. Polymorphism: 다형성

• 부모 객체에서 물려받은 것을 자식 객체에서 각 각 사용하는 것.
• 전화를 거는 기능을 물려받고 이를 실행했을때, iphone과 galaxy는 각 각 다르게 기능을 수행하는게 가능하다.(오버라이딩, overriding) 예를들어 전화를 걸어! 했을 때 iphone은 facetime으로 전화가 가게 만드는 것.
• 파라미터가 달라서 구현이 다른경우를 overloading이라 하는데 이는 자바스크립트에 없다.

OOP, 객체지향은 한 마디로 "사람이 세계를 보고 이해하는 방법을 흉내낸 방법론"

🚗 Instantiation Patterns

: ES6 class가 나오기 전 JavaScript를 객체지향적으로 사용하기 위해 다양한 방법을 사용했다. 인스턴스를 만드는 과정(클래스 선언 방식), Instantiaion Pattern에는 크게 4가지가 있다. Class는 하나의 정형화된 모델을 만들어, 이를 기반으로 인스턴스(복제품)을 만들기 위해 사용한다. 즉, 코드의 재사용성을 대폭 늘려준다.

1. Functional

var Car = function() {
  var somInstance = {};
  someInstance.position = 0;
  someInstance.move = function() {
    this.position += 1;
  }
  return soneInstance;
};
var car1 = Car();
var car2 = Car();
car1.move();

2. Functional Shared

var extend = function(to,from) {
  for(var key in from){
    to[key] = form[key];
  }
};

var smoeMethods = {};
someMethods.move = function(){
  this.position += 1;
};

var Car = function(position){
  var someInstance = {
    position: position,
  };
  extend(someInstance, someMethods);
  return someInstance;
};
var car1 = Car(5);
var car2 = Car(10);

3. Prototypal

var someMethods = {};
someMethods.move = function() {
  this.position += 1;
};
var Car = function(position) {
  // 특정 객체를 prototype으로 하는 객체
  var someInstance = Object.create(someMethods); 를 생성
  someInstance.position = position;
  return someInstance;
};
var car1 = Car(5);
var car2 = Car(10);

4. Pseudoclassical (가장 많이 사용)

var Car = function(position) {
  this.position = position;
};
Car.prototype.move = function() {
  this.position += 1;
};
var car1 = new Car(5);
var car2 = new Car(10);

_Map은 키와 value를 pair로 갖고 있는 자료구조이다. 학번과 이름의 관계와 비슷하다. 학생을 나타내는 고유한 키값(학변)을 이용하면 동일 인물도 구분할 수 있다. 따라서 이 두가지 데이터를 하나의 쌍으로 저장하는 형식이 Map이다.(일반적인 Object와 매우 유사하지만 차이점 존재. 대표적으로 map은 어떠한 데이터 타입도 key값으로 저장 가능.) _

: Hash Map은 Map과 같이 key&value를 쌍으로 저장한다는 점에서 동일하지만, Hash Function을 통해 key를 index로 변환한다는 차이점이 있다. 필요한 경우에만 할당된 메모리 크기를 조절하며 가능한 작은 크기를 유지한다.

What is Hash Function

: 어떠한 값을 넣으면 특정 값으로 변환 후 반환해주는 함수이다. 이때 동일한 input일 경우 항상 같은 ouput을 반환해주어야 좋은 hash function이라 할 수 있다. git commit이 대표적인 hash function을 사용한 예시이다. hash function은 비밀번호와 같이 암호화 후 저장해야 할 경우에 많이 사용된다.(※ 암호화 코드는 충분히 검증된 것을 사용해야 함. 만들어서 사용하려는 생각은 버리자 !)

아래는 스트링 값을 넣어주게될 경우 특정 interger값을 반환해 주는 간단한 hash function이다.

hashCode = function(str) {
    var hash = 0;
    if (str.length == 0) {
        return hash;
    }
    for (var i = 0; i < str.length; i++) {
        var char = str.charCodeAt(i); // returns an integer between 0 and 65535
        hash = ((hash<<5)-hash)+char;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

Hash Collisions

: hash code로 생성된 index가 key별 unique한게 가장 이상적이지만, 겹치는 경우는 어떻게 될까. 여러개의 key가 동일한 index를 부여받을 때 이를 hash collision이라 한다. 여러 방법이 있지만, 나는 충돌이 발생한 index번째 버킷에 key와 value를 쌍으로 하는 튜블을 배열의 형태로 추가해 해결했다.

Map을 이용한 알고리즘: 완주하지 못한 선수

문제: 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 찾는 알고리즘이다. 동명이인이 있는데 완료명단에는 한명의 이름만 있을 경우, 해당 선수는 완료하지 못했다고 가정한다. (문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42576)

해결: 참여 선수명단을 이용해 선수명을 key로 참여횟수를 value로하는 map object를 생성했다. 이후 완료 명단에 있을 경우 참여횟수를 1씩 줄였다. 최종적으로 참여횟수가 1이 넘어갈 경우 해당 선수를 완료하지 못한 선수로 가정했다.

map도 보통의 객체처럼 object[key]와 같은 형식으로 value값을 찾을 수 있지만, object.get(key)처럼 get method를 사용하는 것이 바람직하다. value를 지정할 때도 object[key] = 1이 아닌 object.set(key,1)를 사용하자!

function solution(participant, completion) {
    const map = new Map();

      // 참여선수 이름을 key로 default value로 1, 동명이인일 경우 +1
    participant.forEach(name => {
        if(map.get(name)===undefined){
            map.set(name,1);
        } else {
            map.set(name,map.get(name)+1);
        }
    });

      // 완료선수명단에 이름이 있을 경우 value -1
    completion.forEach(name => {
        if(map.get(name)){
            map.set(name,map.get(name)-1);
        }
    });

    for(let [key, value] of map){
        if(value >= 1){
            return key;
        }
    }
}

: stack은 책이 일자로 쌓여있는 형태의 자료구조이다. 새로운 책을 쌓을 때 가장 위에 놓이게 되고, 책을 꺼낼때에도 가장 위에 책을 꺼낸다. 마지막에 추가된 데이터가 가장 먼저 나가는 이러한 특징을 LIFO(Last in, First out)라 한다.

Stack Implementation

: Javascript의 Array API 중 push()와 pop()이 stack의 특징을 대표하는 예시이다. stack을 배열로 구현하면 다음과 같다.

class Stack {
    constructor(){
        this.data = [];
        this.top = 0;
    }
}

push

: 가장 마지막(top position)에 element를 추가. top포지션은 가장 위에 빈 공간, 즉 새로 element가 추가될 공간을 가르키기에 요소 추가 시 1씩 증가.

push(element) { 
  this.data[this.top] = element;
  this.top++;
  // no return value

peek

: top 포지션에 위치한 element 반환. pop()와 리턴 값이 같으나, peek()은 전체 stack의 변화 없음.

peek() {
  return this.data[this.top-1];
}

pop

: top 포지션에 위치한 element stack에서 제거. 제거된 요소를 반환.

pop() {
  let topIdx = this.top-1;
  let deletedVal = this.data[topIdx];
  this.data = this.data.slice(0,topIdx);
  this.top === 0 ? 0 : this.top--; // 0이 아닐 때 1씩 감소
  return deletedVal;

Queue

: queue는 식당에 줄 서있는 형태와 유사한 자료구조이다. 가장 마지막에 들어온 손님(element)이 가장 마지막에 식당에 들어가는 LILI(Last in, Last out)의 특징을 갖는다.

Queue Implementation

: 자료가 추가될 때에는 stack과 마찬가지로 push()를 사용할 수 있고, 자료를 제거할 때에는 array API에 shift()를 활용할 수 있다.

enqueue

enqueue(element) {
  this.data.push(element);
}

dequeue

dequeue() {
 return this.data.shift(); 
}

이 시간을 이용하여 그동안 미뤄놨던 twittler를 mongo DB와 연결하는 작업을 마무리 했다. 또 이를 Heroku를 이용하여 배포까지 해보았다. 데이터 분석가로 일할 당시 개발자들에게 "데이터 적재해주세요 ~"하고 요청만 하다가 직접 적재하는 일을 해보니 재밌었다.

twittler는 Pre course 2주차때 HTML과 CSS 실습으로 만들었던 것으로 메시지를 작성하면 이를 보여주는 웹이다.

Twittler URL: https://twittler-miniproject.herokuapp.com/

미니 프로젝트의 목적 및 방향은 다음과 같았다.

• 기능을 최소화, 백엔드 구축 & 실제 배포까지의 경험을 목적.
• 웹의 기능은 글 작성, 글 삭제로 제한.
• 클라이언트에서 받는 정보는 1) 작성자, 2) 글 내용
• 글 삭제 시 DB에서 is_deleted 값을 false에서 true값으로 업데이트 (웹에 노출되는 것은 해당 컬럼이 false인 것만)

DB Schema (v1.0)

RESTful API

간단해 보였지만 역시 막상해보니 수월하지는 않았다. 정말 간단하게 해결했지만 시간이 꽤 소요됐던 부분은 post방식으로 DB에 데이터를 적재한 뒤 DB에서 가져온 tweet리스트를 보여주는 것이었다. DB에 보낸 후 화면에서는 저장된 JSON값이 표현된다. 저장 후에 메인페이지('/')로 redirect 해주어서 해결했다. 정리하면 아래와 같다.

1) submit event발생 -> 2) post방식으로 DB에 저장('/content') -> 3) 메인페이지 redirect('/') -> 4) 메인페이지 진입시 fetch로 '/contents' 요청 -> 5) get방식으로 전체 트윗 전달 & li엘리먼트로 append

전체 코드는 github에서 확인 가능하다.

1. 함수 선언식(Function Declarations)

function addOne(num) {
  return num + 1;
}

2. 함수 표현식(Function Experssions)

let addOne = function(num) {
  return num + 1;
}

3. 차이점

위 두 형식으로 만들어진 함수의 가장 큰 차이점은 호이스팅 영향을 받는지 유무이다. 아래와 같이 함수 선언식은 함수를 선언하기 이전에 함수를 실행해도 정상적인 값이 반환된다.

addOne(1);
function addOne(num) {
  return num + 1;
}
// 2 <-- 실행 결과

반면에 함수 표현식으로 함수를 만들게 되면 정상 작동하지 않는다.

addOne(1);
let addOne = function(num) {
  return num + 1;
}
// Uncaught ReferenceError <-- 실행 결과

차이는 함수가 언제 호출되는지 즉 호이스팅으로 인한 것이다. 함수 선언문은 정의되기 전(실행흐름과 상관없이)에도 호출된다. 따라서 스크립트 어디에 있는지에 상관없이 어디서든 해당 함수를 사용할 수 있다. 반면에 함수 표현문은 실행흐름에 따라 먼저 함수가 정의 되어야지만 해당 함수 사용이 가능하다.

이는 스크립트 작동원리로 인한 것인데, 자바스크립트는 실행하기 전, 전역에 선언된 함수 선언문을 찾고, 해당 함수를 생성한다. 따라서 함수 선언문으로 만들어진 함수는 어느 위치에서든 사용이 가능하다.