[Week3] 자료구조 기초

## 자료구조 기초

 

### 목표

• 자료구조가 무엇인지 설명할 수 있다.
• Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
  • 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
  • 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
  • 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
• 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
  • Binary Search Tree를 이해할 수 있다.
  • BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
• 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다. 

자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의하는 것을 말한다.

데이터는 분석하고 정리하여 활용해야만 의미가 있다.

 

데이터를 효율적으로 다룬 상황의 예시 ↓

• 번호를 다 알지 않아도, 이름을 아는 것만으로 전화를 할 수 있는 방법은 무엇이 있을까?
• 웹 브라우저에서 뒤로 / 앞으로 가는 방법은 무엇이 있을까?
• 게임 매칭을 잡을 때, 수많은 사람들을 통제하는 방법엔 무엇이 있을까? ...등등

 

자료구조의 종류와 구분

이중에서 알고리즘 테스트에 자주 등장하는 네 가지를 학습해 보도록 한다.

자주 등장하는 네 가지의 자료구조
Stack, Queue, Tree, Graph

 

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어 있다.

핵심은

• 각 자료구조가 가진 특징을 학습한다.
• 각 자료구조를 사용하기 적합한 상황을 이해한다.
• 다른 자료구조와의 차이점을 이해하기 위해 자료구조 내부를 직접 구현한다.
• 자료구조를 구현하며, 자료구조의 동작원리를 이해한다.

테스트에 걸리는 시간을 단축하고 알고리즘 문제 풀이에 집중하기 위해, JavaScript에서 제공하는 배열(Array)과 같은 데이터 타입을 이용해 자료구조의 형태와 유사하게 구현하여 문제를 해결한다.

 

### Stack

Stack은 "쌓다"의 뜻으로 접시를 쌓아 놓은듯한 형태를 가진 자료구조이다. 직역 그대로 데이터를 쌓는 자료구조이다.

예를 들자면

다섯 대의 자동차가 순서대로 좁은 골목을 지나고 있다. 좁은 골목에 진입한 차량은 곧 맞이할 미래를 모르고 있지만,
이 골목의 끝은 막혀 있다.
첫 번째 자동차는 이 골목을 통과하기 위해 직진했고, 나머지 자동차도 앞 자동차의 꽁무니를 따라 직진했다. 그러나 첫 번째 차량이 막다른 길을 맞이했다.
마지막으로 들어온 다섯번 째 자동차가 먼저 후진하여 나와야 하는 상황
이 되어버렸다.

 

골목을 자료구조 stack, 자동차는 data로 구분할 수 있다.

특징은 입출력이 하나의 방향에서 이루어지는 제한적 접근이다. 이런 Stack 자료구조의 정책을 LIFO(Last in first out), FILO(First in last out)라고 부르기도 한다.

대표적으로 사용되는 방식은 바로 브라우저에서 페이지 뒤로 가기, 앞으로 가기 기능이다. ↓

브라우저 뒤로 가기 앞으로 가기에 사용된 stack

 

### Queue

자료구조 Queue는 "줄서서 기다리다"의 뜻을 가지고 있어서 자료구조에서는 Stack와 반대되는 개념으로 사용된다.

바로 먼저들어간 데이터가 먼저 나가는 FIFO(First in first out) 혹은 LILO(Last in last out)을 특징으로 가지고 있다.

역시 일상생활의 예로 설명하자면

명절에는 고향으로 가기 위해 많은 자동차들이 고속도로를 지난다. 고속도로에는 톨게이트가 있고, 자동차는 톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과한다.

 

톨게이트를 Queue 자료구조, 자동차를 data로 비유할 수 있다.Queue의 실사용 예제는 바로 프린터다.

인쇄 작업 Queue는 Queue에 들어온 문서를 순서대로 출력

컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 순서대로 인쇄

위 예시처럼 컴퓨터 장치들 사이에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도 차이, 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 버퍼(Buffer)라고 한다.

대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생한다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용한다.

(왼쪽) CPU에서는 이벤트를 규칙적으로 처리. (오른쪽) 대부분의 컴퓨터 장치에서는 이벤트가 불규칙하게 발생

컴퓨터와 프린터 사이의 데이터 통신을 정리하면 다음과 같다.

• 일반적으로 프린터는 속도가 느리다.
• CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠르다.
• 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
• 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄한다.

다른 예시로는 유튜브와 같은 동영상 스트리밍 사이트를 들 수 있는데, 동영상을 시청할 때, 다운로드된 데이터가 영상을 재생하기 충분하지 않은 경우가 있다. 이때 동영상을 정상적으로 재생할 수 있도록 Queue에 모아 두었다가 동영상 재생하기 충분한 양의 데이터가 모였을 때 동영상을 제공한다.

 

### Implementation Stack / Queue

JS 사용자 정의 데이터 타입을 만들어 내는 여러 방법 중에서, ES6의 문법 중 하나인 class 키워드로 사용자 정의 데이터 타입을 만들고, Stack 과 Queue의 데이터 타입을 정의한다. 이렇게 생성한 사용자 정의 데이터 타입은 Stack과 Queue를 Arrary와 Object 처럼 사용할 수 있다.

사용자 정의 타입으로 Stack / Queue를 정의하면, new 키워드를 통해 새로운 객체(인스턴스)를 만들 수 있다. 그리고 생성한 인스턴스를 이용해서 다양한 메서드를 사용할 수 있다. 

 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Classes

Classes - JavaScript | MDN

class 키워드에 참조할 만한 글 ↑

함수 선언과 클래스 선언의 가장 큰 차이는 함수의 경우 정의하기 전에 호출할 수 있지만, 클래스는 반드시 정의한 뒤에 사용할 수 있다.