Today, I Learned

• 자료와 자료형, 그리고 자료구조의 이론적인 부분에 대해서 간략하게 학습했다. 먼저, 자료(Data)는 문자, 소리, 영상, 단어, 숫자 등 다양한 종류로 된 '의미 단위'이다. 그렇다면, 자료형은? 본래 컴퓨터는 0,1 만을 이해할 수 있다. 한국인이 자음, 모음, 다양한 바디랭귀지 등을 통해서 소통하는 것과 달리 컴퓨터는 단지 0과 1 두 개만을 가지고 소통한다는 것이다. 그렇기에 인간이 컴퓨터와 소통하려면, 0,1을 써서 해야했었다. 그러나, 요즘은 프로그래밍 언어를 쓰고, 프로그래밍 언어와 컴퓨터의 0,1 사이에 컴파일러(해석해보면 번역기 정도로 볼 수 있다)가 있어서 둘 사이의 징검다리 역할을 해준다. 이렇게 컴퓨터는 0,1만 이해할 수 있는데, 이러한 컴퓨터에게 0,1의 조합을 통해 앞서 말한 문자, 단어, 숫자 등을 이해시키려면, 일종의 약속이 필요하다. 인간이 쓰는 다양한 자료(숫자, 단어 등등)를 컴퓨터의 0,1로 표현하기 위한 규칙말이다. 그리고 이러한 규칙에 대한 정의가 자료형이라고 할 수 있다. 마지막으로, 자료구조(Data Structure)는 앞서 말한 자료에 대한 저장 및 사용에 관한 룰을 정의해놓은 것으로 예를 들어, 배열, linked List, 스택, 큐 등이 있다. 이러한 자료구조는 어떤 상황에 특화되어져 있기 때문에 상황에 맞는 자료 구조 사용은 효율을 높일 수 있기에 잘 알아두어야 한다.
  +a 지식 : 0,1은 1비트(bit) 에 담김. 그리고, 8비트는 1바이트(byte)라는 것을 알아두자
• 스택과 큐에 대해서 이론적인 부분 공부 : 이 부분은 사실 과거에 내가 포스팅해놓은 것이 잘해뒀다고 생각되어 그 부분을 복습해보았다.
  ( 스택 블로그, 큐 블로그 )
• 나만의 Queue 만들어보기

  class Queue {
      constructor() {
          this.storage = {},
          this.front = 0,
          this.rear = 0
      }
      enqueue(element) {
        this.storage[this.rear] = element;
        this.rear ++;
        return this.front 
      }
      dequeue() {
        if (this.front === this.rear ) {
          return ;
        }
        let val = this.storage[this.front];
        delete this.storage[this.front];
        this.front ++;
        return val;
      }
      size() {
        return this.rear - this.front;
      }
      peek() {
        return this.storage[this.front];
      }
      isEmpty() {
            return this.size() === 0;
      }
  }

• 나만의 Stack 만들어보기

  class Stack {
    constructor () {
      this.storage = {},
      this.top = 0
    }
    pop() {
      if (this.top === 0) {
        return ;
      }
      let val = this.storage[this.top-1];
      delete this.storage[this.top-1];
      this.top --;
      return val;
    }
    
    push(element) {
      this.storage[this.top] = element;
      this.top ++;
      return this.top;
    }
    
    size() {
      return this.top;
    }
    
    peek() {
      return this.storage[this.top-1];  
    }
    
    isEmpty() {
      return this.size() === 0;
    }
  }

• +a with queue and stack : 큐나 스택은 index를 쓰지 않는다. 인덱스를 이용해서 개별 값을 참조하고자 할 때는 배열을 써야한다. 스택 혹은 큐라는 자료구조는 인덱싱을 해서 자료를 찾기 위한 자료구조가 아니고, 큐는 FIFO구조로 쓰기 위해서, 스택은 FILO구조로 쓰기 위해서 존재하는 자료구조이다(그러나, 만약 이번 미션이 자바나 C언어로 구현하는 미션이였다면, 위와 같은 방식으로 하면 자료구조의 낭비가 일어날 것! why?큐로 하면 인덱스가 하나씩 밀리기 때문에 만약 dequeue를 한번이라도 하면, 그 부분은 위의 로직으로는 더 이상 쓸 수 없는 것이 됨. 자바나 C는 배열에 있어서 크기가 정해지고 시작하기 때문에 이렇게 되면 자료구조의 낭비가 발생함. 이 부분에 대해서 자바나 씨언어를 가정하고 풀어보자). + 큐는 포인터가 2개고, 스택은 1개인 것으로 생각해도 좋을듯하다.
• 나만의 Circular Queue 만들어보기
  

  class CircularQueue {
      constructor(maxLength) {
          this.storage = {},
              this.front_pointer = 0,
              this.rear_pointer = 0,
              this.len = maxLength
      }
  enqueue(element) {
      let front = this.front_pointer % this.len;
      if (Object.prototype.hasOwnProperty.call(this.storage, front)) {
          return this.front_pointer - this.rear_pointer;
      }
      this.storage[front] = element;
      this.front_pointer++;
      return this.front_pointer - this.rear_pointer;
  }
  
  dequeue() {
      if (this.rear_pointer === this.front_pointer) {
          return;
      }
      let rear = this.rear_pointer++ % this.len;
      let val = this.storage[rear];
      delete this.storage[rear];
      return val;
  }
  
  size() {
      return this.front_pointer - this.rear_pointer;
  }
  
  isEmpty() {
      return this.front_pointer - this.rear_pointer === 0;
  }
  
  peek() {
      let rear = this.rear_pointer++ % this.len;
      return this.storage[rear];
  }
  }

  여기서 사용한 0부터 차례대로 n+1개의 숫자를 순환시키는 방법을 기억해두자.
• Array list vs Singly Linked List vs Doubly Linked List :
  : 솔직히, 아직 제대로 정리가 안된 느낌이지만, 오늘 얻은 내용을 토대로 정리해보면, 먼저, 배열은 자바스크립트가 아닌 다른 언어(java, c언어 등)에서는 메모리 할당이 정해지고 만들어진다. 즉, 자료의 크기가 유동적이지 않다는 것이다. 그렇기에 자료구조에 몇개의 자료를 넣을지를 미리 제대로 예측해야 자료의 낭비를 막는다(30개를 넣을 것이라고 생각하고 30개짜리 배열을 만들었는데 막상 5개만 넣으면 25칸이 낭비됨). 이에 반해, linked list는 유동적인 자료구조의 사용이 가능하다. 일단 초기에 할당 제한이 없기에 만드는 대로 자료구조의 크기가 된다. 하지만, 각 노드에 포인터를 넣어야하기 때문에 메모리를 추가적으로 쓰게 된다. 또한, linked list가 포인터로 연결되어있기 때문에(각 노드들이) 추가와 삭제가 배열에 비해서[O(n)] 효율적이라고 할 수 있는데, 자세히 살펴보면, 만약 추가와 삭제할 자료가 어디에 있는지 명확한 예를 들어, 맨 앞 혹은 이중 연결 리스트에서 맨 앞, 맨 뒤의 경우가 아닌 이상 결국 탐색을 해서 찾고, 지우거나 추가해야한다. 따라서, 결국 탐색에 O(n)이 쓰여 비슷하게 된다. 이 때, 싱글 linked list와 이중 linked list의 차이는 메모리 차이(싱글은 포인터가 한개, 이중은 포인터가 한 노드에 두개)가 있고, 두 개의 포인터가 양 옆으로의 이동을 가능하게 해주는 이중 linked list가 좀 더 속도가 빠르다는 점이 차이가 난다. 하지만, 이는 추상적인 혹은 이론적인 내용이며, 실제로 이것이 얼마나 효율성에 있어서(시간 복잡도) 차이가 나고, 언제 뭐를 쓸지는 정확히 파악하지 못했기에 추가 학습이 필요하다(+원형 연결 리스트).

Planning to Study

• array, linked list(singly, doubly, circular)를 시간 복잡도 및 실제 활용하는 곳과 관련해서 심화 학습해보기
• 원형 큐 복습
• 스택으로 계산기 만들어보기
• 질문 해결하기 :

  1)linked list는 결국 추가 및 삭제를 할 때
  처음부터 추가 및 삭제를 할 곳을 탐색한 뒤에 O(n)
  추가 및 삭제O(1)하기 때문에 결국 O(n)이 아닌가?
  2)이중 연결리스트, 단일 연결 리스트, 원형 연결 리스트의 차이(시간 복잡도에 관해서)
  + 각각 어디에 쓰이는지