Today, I Learned

• 변수를 만든 뒤에 둘 중 true인 것을 넣고 싶을 때, 예를 들어,
  let val;
  val = [1,2,3] || false;
  이렇게하면, val에 true가 들어가지 않고, true를 가능하게 해준 [1,2,3]이 들어간다. 이 문법을 잘 써먹으면 코딩할 때 편할 것이라고 생각된다.
• About Graph
  
  • Graph의 구성 요소 : edge, node
  • Graph의 종류 : directed graph(인스타의 팔로우 방식), indirected graph(페이스북 친추방식)/
    weighted graph(edge에 숫자 값이 있는 것), unweighted graph(edge에 숫자 값이 없는 것)
    ** directed graph에서 진입 차수 : 노드로 들어오는 edge의 수, 진출 차수 : 노드로부터 뻗어나가는 edge의 수
  • Graph 표현 방식 : adjacency list(인접 리스트 방식) / adjacency matrix(인접 행렬 방식)
  • 인접 행렬 방식과 인접 리스트 방식의 비교 : 인접 행렬 방식은 인접 리스트 방식보다 자료 구조를 차지하는 자료의 양이 많을 수 밖에 없다. edge로 연결되어 있지 않은 자료도 false 혹은 0의 형태로 자료를 저장하기 때문이다. 이에 반해, 인접 리스트 방식은 hasEdge 인 자료만을 저장하기 때문에 자료의 크기가 상대적으로 적다. 이러한 비교에 더해서, 인접 행렬 방식은 두 노드가 연결되어 있는지를 확인하기 위해서 O(n)의 복잡도를 갖는 작업을 해야한다. 이는 상당히 낭비인데, 그 이유는 아까 말했듯이 인접 행렬 방식에서는 연결되지 않은 자료도 false 혹은 0의 형태로 보관하기 때문에 인접하는지를 알려면 탐색하는 노드는 1억개인데, 정작 인접하는 노드는 두개인 경우에도 1억번을 탐색해야하는 낭비가 따르게 된다. 그러나, 인접 리스트 방식은 연결된 자료만 보관하므로 위와 같은 낭비를 할 필요가 없다. 여기서 포인트는 인접 행렬 방식은 메모리 측면에 있어서 hasEdge가 아닌 노드들도 저장한다는 점에서 낭비하는 부분이 있고, 인접 리스트 방식은 그런 부분에 있어서 효율적이라는 점이다. 하지만, 인접 행렬 방식과 달리 인접 리스트 방식은 특정한 두 노드가 인접하는지를 알려면, O(n)의 작업을 해야한다. 이에 반해, 인접 행렬 방식은 adj[i][j], 즉, O(1)의 작업으로 한 번에 확인이 가능하다는 점에서 차이를 보인다. 따라서, edged 노드가 많은 경우, 그리고 edged 여부를 자주 확인해야할 때는 인접 행렬 방식, edged 노드가 적고, edged 여부를 자주 확인하지는 않을 때는 인접 리스트 방식이 좋다고 할 수 있다.
• About Tree data structure : tree 자료구조 구현해보기 by js

Planning to Study

• binary search tree 구현해보기
• binary search 개념 심화 공부