20-09-07 TIL

Topics Learned

• Stack
  • LIFO 자료 구조로, Execution Stack 과 같이 일단 함수들이 쌓였다가 실행 단계가 되면서 가장 마지막 것 부터 처리해주는 방식이다.
  • Array.pop/Array.push 메소드로 쉽게 구현 가능하지만 학습 목적이기 때문에 객체 형태로 push, pop 메소드를 구현했다.
• Queue
  • FIFO 자료 구조로, 보통 서버 query 등을 처리할 때 이용된다.
  • 마찬가지로 객체로 구현 했으며, queue 를 등록시키는 enqueue, 큐를 삭제하는 dequeue 메소드를 구현했다.
  • Linear Queue (내가 구현한) 에서는 Queue 가 다 찬 후, 먼저 공간이 생기더라도 채워넣을 수 없는 문제점이 발생한다. 이는 자료구조가 선형적으로 이루어져 있기 때문인데, 이를 해결하기 위해 Circular Queue 라는 자료구조가 존재한다.
• Linked List
  • 각자의 node 가 다음의 node 값만 갖고 있는 가장 기본적인 Singly Linked List 를 구현했다.
  • Node 는 value 와 next 를 Linked List 는 head, tail, size 값을 갖고있다.
  • 만약 Linked List 에 Node 가 없다면 Head 를 만들어주고, 존재한다면 가장 최근 생성 된 node 가 곧 tail 이 된다.
  • 새로 노드를 만드는 메소드인, addToTail, 노드를 삭제하는 remove, 특정 인덱스에 있는 노드 값을 불러오는getNodeAt, 포함 유무를 리턴하는 contains, 노드 값을 받아 값이 일치할 경우 index 를 리턴하는 함수들을 구현했다.
• Hash Table
  • Hash Table 은 마치 JavaScript 에서 객체와 같은 형식의 자료 구조로, 키 값을 보내면 value 를 리턴해준다.
  • 이때 value 는 스트링 값과 해쉬 테이블 한계 크기를 받아 암호화 해주는 Hash Function 으로 만들어진 인덱스에 저장된다.
  • 문제는 이러한 해쉬 함수가 같은 인덱스에 저장하게 되는 경우가 발생하는데 이를 collision(충돌) 이라고 한다.
  • 이러한 문제를 해결하기 위해 bucket 을 만들어 각 키와 값 들로 이루어진 tuple 을 bucket 안에 넣어서, 같은 인덱스를 갖더라도 따로 저장될 수 있게 구현했다.
  • size 가 limit 의 75% 에 도달하거나, 25% 미만이 되면 동적으로 hash table 의 limit 을 조정해 줌으로써, 성능을 최적화 시킬 수 있도록 구현했다.
• Graph
  • 그래프는 node 와 node 사이를 이어주는 edge 로 이루어져 있다.
  • 무향, 유향 그래프들이 존재하며 edge 가 서로에게 존재하는 형태인 무향 그래프를 구현했다.
  • 그래프는 Adjacency Matrix 혹은 Adjacency List 가 존재하며 각기 다른 장단점이 있다.
  • Adjacency Matrix 는 공간 복잡도가 v^2 며, List 는 V+E 다.
  • 따라서 Adjacency List 는 각 노드의 간선을 이어주거나 노드를 삽입하는데 유리하며, Matrix 는 Search 를 더 쉽게 할 수 있다.
• Tree
  • Tree 부터는 본격적으로 재귀 개념이 적용된다.
  • root 이라는 가장 최상위 노드가 존재하며, 마치 나무처럼 가지 퍼지듯 퍼져나가는 데이터 구조다.
• BST (Binary Search Tree)
  • BST 는 트리와 비슷하지만, 각 노드당 2개의 자식만을 가질 수 있다.
  • 자식이 없는 노드는 leaf 라고 부른다.
  • 작은 수는 노드의 왼쪽에, 노드보다 큰 수는 오른쪽에 배치된다.
  • 일반 적인 경우 O log n 의 Big O notation 을 갖게되며, 많은 수들을 효과적으로 서치할 수 있다.
  • BST 를 순회하는 방법은, preorder, inorder, postorder 등이 있으며 단순하게 어떤 방향부터 돌아 value 를 체크 하느냐의 차이이다. 각 노드를 리턴한다고 했을 때 오름차순 으로 일정하게 리턴된다.

Summary

• 이전에 단순히 이론적으로 공부할 때는 잘 몰랐는데, 확실히 구현을 해보니까 조금 더 구조의 개념에 대해서 가까워진 느낌이다.
• 각 자료 구조들이 어떠한 특징을 갖고 있고, 어떨 때 유용하게 쓰일 수 있는지 어느정도 이해했다.
• 아무래도 자료 구조의 본질은 Big O 에 의해 결정되기 때문에, iteration 수를 최소한으로 줄이는데 주력했던 것 같다.