200903_TIL

Today I learned

• Data structure
• Stack
• Queue

@@ 오늘은 페어와 스택과 큐를 자바스크립트로 구현하는 페어 프로그래밍을 진행했다. 스택과 큐를 object로 구현하는 방식이었는데, 보통 스택과 큐는 linked list 혹은 배열로 구현한다고 하는데 자바스크립트 특성 상 동적 메모리 할당을 하기 때문에 문제가 너무 간단해져서 object 구현으로 대신 스프린트를 진행했다.

object로 진행해도 생각보다 어렵지 않게 구현을 마칠 수 있었다. 오늘 온라인세션으로 진행된 checkpoint solution 시간에 추가적으로 다뤘던 원형 큐나 우선순위 큐 같은 경우엔 비교적 까다로운 개념들이 이해하기 힘들었지만, 기본 개념들은 이해하기 어렵지 않았던 것 같다.

내일이 대망의 해시 테이블과 연결 리스트를 배우는데, 미리 예습하는 시간을 좀 가졌는데 해시 테이블이 역시나 이해하기 까다롭다.

자료구조에 대한 기본 베이스를 가져가기 위해, 저녁 시간을 활용해 블로그와 책들을 뒤져서 더듬더듬 짚어가면서 공부해보고 있다.

자료구조는 정말 다루지 않았던, 처음 접하는 쌩 지식들이라서 아직은 너무 낯설고 이 개념들을 갖고 있으면 어떤식으로 도움이 되고 활용이 되는지 아직은 까마득하게만 느껴진다.

그래도 10번 보다보면 1은 건질 수 있을거라고 생각하니까, 계속 정리한 내용들을 살펴봐야겠다.

Data structure

• 자료
  문자, 숫자, 소리, 그림, 영상, 단어 등의 형태로 된 의미 단어
  자료를 의미있게 정리하면 정보가 된다.

• 컴퓨터의 언어

  1. 명령

  2. 데이터

     컴퓨터의 언어는 0과 1로 이루어져있다.

     컴퓨터는 0과 1만 이해할 수 있기 때문에 사람과 다르고, 사람이 컴퓨터적 사고를 하기에 물리적 사고적 힘듦이 존재했기에 사람은 프로그래밍 언어를 개발하고, 이 언어와 컴퓨터 언어 사이에 번역기가 등장하게 된다 (컴파일러)

     컴파일러의 등장으로 인간의 언어로 컴퓨터에게 명령을 내릴 수 있게 됐다.

     이에 더불어 데이터 타입 또한 0,1이 아닌 사람이 알아보기 쉽게 만들어낸다.

     8 비트 = 1바이트 단위로 데이터를 읽어서 값을 만들어낸다.

• ASCII table
  숫자와 문자를 1대1로 연결하자는 약속.

• 데이터 타입

• 컴퓨터에 0과 1로 저장되어 있는 데이터를 인간이 사용하는 여러가지 데이터들의 종류로 해석하기 위한 장치

• 같은 이진 데이터라도 인간의 해석에 따라 다른 데이터가 될 수 있다.

• 원시 타입

  • 정수, 실수
  • 문자
  • 논리 (참, 거짓)
  • 사용자 정의 타입 (custom type)
  • 구조체, 클래스 등

• 자료구조

  • 여러 데이터들의 묶음을 어떻게 저장하고 사용할지에 대한 정의

  • 배열
    범용적으로 가장 많이 사용되는 자료구조

  • 자료구조 타입

    • 배열, 스택, 트리 등

  • 자료 구조의 활용

    • 1000만개의 데이터 안에서 원하는 데이터를 찾아야 한다면?
      배열에 있다면 1000만 번의 검색이 필요하다
      그러나, 자료구조의 변경 만으로 최대 25번 이하 안으로 데이터를 찾을 수 있다.

Stack

• last in, first out(LIFO)

• 데이터가 입력되면 입력되는 순서대로 쌓이고, 나중에 들어온 것 부터 먼저 사용하는 자료 구조

• 스택의 구현은 배열을 이용해도 되고, 연결 리스트를 이용해도 된다.

• 스택은 대표적으로 프로그램을 수행할 때 사용한다.
  함수 A를 호출하면 함수 A가 스택에 쌓이고 A함수 실행 중 B함수가 호출되면 스택 A 위에 B가 쌓인다.

• 사람이 이해하기 쉬운 중위 표기법을 컴퓨터는 후위 표기법 형태로 변형하여 처리한다.

• 하나의 공간에 2개의 스택을 구현하여 각자 사용하는 것을 다중 스택이라고 한다.

• 뒤로 넣고 뺄수만 있다. 앞으로는 넣지도 빼지도 못하는 구조.

• 스택의 주요 연산

  • .top() ( = .peek())
  • .pop()
  • .push()
  • .empty()

• push, pop이라는 메소드 이름은 스택에서 나온 것이다.

• stack.peek()
  Java 스택, pop()과 유사하지만 스택을 수정하지 않는다.

• 스택의 마지막 요소를 top이라고 부르기도 한다.

• 함수를 연이어 호출하면 스택처럼 메모리에 쌓이고, 역순으로 하나씩 실행된다.

• 함수는 일정 메모리를 차지하기 때문에 스택 메모리 안에 너무 많이 쌓이면 메모리 에러가 발생한다.

• 탈출 코드가 없이 재귀함수를 호출하면 스택 메모리가 다 찰 때까지 다 쌓이다가 스택 오버플로우 에러를 발생시킨다.

Queue

• first in , first out (FIFO)
• 데이터가 입력되면 입력되는 순서대로 쌓고 먼저 들어온 것부터 먼저 사용하는 자료구조

• 큐의 구현은 배열을 이용하거나(순환 큐), 연결리스트(linked queue)를 이용한다.

• 큐 자료구조 용도
  컴퓨터 안에 여러 개의 프로세스가 수행중인데 새로운 프로세스가 수행되어야 하는 경우 기존에 수행되던 프로세스 중에서 가장 먼저 메모리에 올라온 프로세스가 아웃되고, 새로운 프로세스를 큐의 형태로 관리한다.

  윈도우 체제를 사용하는 컴퓨터 중에서 수행 중인 프로그램에 이벤트가 발생하면, 발생한 이벤트가 큐에 저장되고, 수행 중인 프로그램이 큐에 저장된 것을 앞에서부터 읽어와서 처리한다.
  

• 실생활 예시 : 대기 줄

• 자바스크립트 배열 중 push, shift만 존재한다고 생각할 수 있다.

• enqueue , dequeue

• 제일 앞의 데이터를 알 수 있는 front가 존재한다.

• 큐 종류

  • 순환 큐

    • 메모리 관리가 쉽다.

    • 자바스크립트에선 메모리를 알아서 정리하기 때문에 효용성이 떨어진다.

    • 메모리 크기가 정해져있을 때 순환 큐는 유용하게 사용될 수 있는데, 왜냐면 선형 큐가 단점을 갖고 있기 때문이다.

      • 선형큐의 문제점

        1. dequeue할 때마다 모든 데이터를 한칸 씩 앞으로 당기면 그만큼 시간 복잡도는 O(n)으로 증가된다. 또한 Front를 사용하는 이유가 없어지기 때문에 비효율 적이며 메모리가 소모된다.
        2. Front를 다음 인덱스로 넘겨주면 간단하게 처리할 수 있지만, 요소가 제거될 때마다 저장할수 있는 데이터 공간이 그만큼 줄어든다. 메모리 공간이 4칸이라고 가정할 때, 4칸을 다 사용하지 않고 있는데도 아이템을 추가할 수 없게 된다.

      • 순환 큐는 이런 선형 큐의 문제점을 보완할 수 있다.

        • 원형큐의 문제점

          • 원형큐에서 Front를 비워두지 않고 일반적으로 사용했을 때의 문제점

            원형큐는 데이터 공간이 한정적일 때 유용하게 사용될 수 있으나, enqueue 와 dequeue를 반복할 때,
            문제점이 생기는데 4칸인 데이터 공간에 데이터를 모두 가득 채웠다가 dequeue로 삭제했을 때, front는 0 rear는 3을 가리키게 되는데 이것이 데이터가 가득 찼을 때와 다르지 않다. 즉 데이터가 가득 찼는지, 하나도 없는지 상태를 구분할 수 없게 된다.

          • 해결 방법은 Front를 비워두는 방식으로 해결될 수 있다.

            참고: [자료구조] 원형 큐의 기능 및 구현

  • 우선 순위 큐

    • enqueue 할 때 데이터의 우선순위를 따져서 데이터를 넣는다.
    • 우선 순위 큐는 큐로 구현하면 데이터 삽입이 어렵다. 힙이라는 구조를 사용해 구한다.