TIL 21.05.12

Jaemin Jung·2021년 5월 15일

Today I Learned

목록 보기

18/62

오늘한일

오늘은 자료구조에 대해서 배웠다.
자료구조 stack queue를 코드로 구현하는 코플릿은 적절히 해결하였으나,
이 개념을 베이스로한 알고리즘에서 뚜드려 맞은것같다.
그동안은 문제를 못풀더라도 밤늦게까지 붙들어서 문제들을 해결했었으나,
오늘처럼 아예 문제해결 시도도 못해본건 처음이다.
자료 구조를 구현하는 문제 외에 알고리즘은 딱 한문제밖에 해결하지 못했다.

Achievement Goals

(이해한대로 작성하였기에 틀릴수도 있습니다. 계속 공부하며 수정해 나가겠습니다.)

자료구조가 무엇인지 설명할 수 있다.
Stack, Queue 자료구조에 대해 이해할 수 있다.
알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

자료구조

자료(data)는 문자, 숫자, 소리, 그림, 영상 등으로 실생활을 구성하고 있는것들이다.
이러한 각각의 자료들을 하나의 방법으로만 정리하고 활용한다면, 코드가 복잡해지고 효율성도 떨어질것이다.
그렇기에 해당 자료들의 특징을 잘 파악(분석)하여 정리하고, 활용되어야 한다.
자료구조란 여러 데이터들의 묶음을 어떻게 저장할 것이고, 사용할것인지 정의한 것이다.
자료구조중 가장 많이 쓰이는 네가지 자료구조는 (Stack, Queue, Tree, Graph)가 있다.
오늘은 Stack과 Queue에 대해서 작성하겠다.

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.
어떠한 자료를 저장하는 공간에서 가장 마지막에 쌓인 데이터를 사용하는 특성이다.
실생활에서 예를 들자면, 학창시절 친구들과 했던 장난인 햄버거놀이가 비슷하다.
철수 영희 훈이가 햄버거놀이를 할때 철수가 맨 밑에 누워있으면 영희가 철수 위로 누울것이고, 마지막에는 훈이가 영희 위로 누울것이다.
햄버거놀이가 끝나면 마지막으로 누웠던 훈이가 먼저 일어날것이고,
그다음은 영희, 그다음은 철수가 일어난다.
이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.

Stack 구현

Stack 자료구조를 class를 이용해 코드로 구현해본다.
LIFO(Last In First Out)은 array.pop()메소드와 비슷하다.

class Stack { // class를 이용한 Stack 자료구조 구현
  constructor() { // 생성자 함수로 자료 저장할 공간을 생성
    this.storage = {};
    this.top = 0; // Stack의 가장 상단을 가리키는 포인터 변수
  }

  size() { // Stack의 사이즈를 구하는 메소드
    return this.top;
  }

  push(element) { // Stack은 가장 최근에 들어간 자료가 가장 상단에 위치
    this.storage[this.top] = element;
    this.top += 1; // 자료가 추가되었으니, 최상단을 가리키는 변수에 +1
  }
	
	
  pop() {// LIFO(Last In First Out) 구현
    
    if (this.top <= 0) {// 빈 Stack에 pop 연산을 적용해도 에러가 발생하지 않도록 조건 작성
      return;
    }

    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];// 최상단 데이터 제거
    this.top -= 1; // 최상단 데이터가 제거되었으니, 최상단을 가리키는 변수에 -1
    
    return result; // 어떤 데이터가 제거되었는지 리턴
  }
}

Queue

Queue는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있다.
어떠한 자료를 저장하는 공간에서 가장 처음에 쌓인 데이터를 사용하는 특성이다.
실생활에서는 놀이공원을 예로 들수있겠다.
줄을 서서 기다리다.라는 말처럼 놀이기구를 타기위해서 사람들은 줄을선다.
그리고 가장 먼저 줄선사람이 가장 먼저 놀이기구를 타게되고,
그다음은 두번째로 줄선사람이 먼저 놀이기구를 탈것이다.
이런 Queu 자료구조의 정책을 FIFO(First In First Out) 혹은 LILO(Last In Last Out)이라고 부르기도 한다.

Queue 구현

Queue 자료구조를 class를 이용해 코드로 구현해본다.
FIFO(First In First Out)은 array.shift메소드와 비슷하다.

class Queue { // class를 이용한 Queue 자료구조 구현
  constructor() { // 생성자 함수로 자료 저장할 공간을 생성
    this.storage = {};
    this.front = 0; // 자료중 가장 첫 순번을 가리키는 포인터 변수와, 마지막 순번을 가리키는 포인터 변수
    this.rear = 0;
  }

  size() { // Queue의 사이즈를 구하는 메소드
    return this.rear - this.front;
  }
	
	
  enqueue(element) { // Queue는 가장 최근에 들어간 자료가 가장 마지막 순번
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
  dequeue() { // FIFO(First In First Out) 구현
    
    if (this.rear === this.front) {// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않도록 조건 작성
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];// 첫순번 데이터를 제거
    this.front += 1;// 첫순번 데이터가 제거되었으니, 그다음 순번을 가리켜야함

    return result; // 어떤 데이터가 제거되었는지 리턴
  }
}