자료구조란 무엇일까

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

먼저 데이터는 무엇일까?

데이터는 문자, 숫자, 소리, 그림, 영상등 실생활을 구성하고 있는 모든 값이다. 나이라는 데이터만 가지고 있으면 사람의 나이인지, 강아지의 나이인지 알수 없기 때문에, 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.
뿐만 아니라, 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용한다. 전화번호를 저장할때 -이 필요하지 않는데, 이런 방식으로 데이터를 저장한다면, 모든 숫자에 필요하지 않은 이름을 굳이 붙여야한다. 이렇게 필요에 따라서 데이터의 특징을 잘 파악(분석)하여 정리하고 활용해야한다. 데이터를 정해진 규칙없이 저장하거나 , 하나의 구조로만 정리하고 활용하는 것보다 데이터를 체계적으로 정리하여 저장해두는 것이 데이터를 활용하는데 있어 훨씬 유리하다.

자주 등장하는 네 가지의 자료구조

Stack, Queue, Tree, Graph

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어 있다. 그렇기 때문에 많은 자료구조를 알아둔다면, 상황별로 적합한 자료구조를 빠르고 정확하게 적용해서 문제를 해결할 수 있다. 이것은 문제 해결력을 필요로하는 알고리즘 테스트와 깊은 연관이 있다. 특정 문제를 해결하는데 적합한 자료구조를 찾아서 데이터를 정리하고 활용할줄 안다면, 상황에 가장 적합하고 정확한 코드를 작성할 수 있다.

Sprint Roadmap

Stack 이나 Queue 등의 단어는 생소하지만 대표적인 자료구조인 array 인 배열을 써왔다. 이처럼 데이터를 순서대로 쭉 나열하여 저장한 배열이라는 자료구조의 특징과 활용 방안을 미리 알고있다. 자료구조와 비슷한 면이 있다.

핵심내용

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

1. class 키워드를 사용해서 자료구조의 데이터 타입을 직접 정의한다. 이를 진행하면서 필요한 속성과 메소드를 익힌다.

class Person {
  constructor(name, hand, foot) {
    this.name = name;
    this.hand = hand;
    this.foot = foot;
  }
    speak() {
      return `저는 ${this.name}입니다.`
    }
}
const kimcoding = new Person('김코딩', 2, 2);
console.log(kimcoding.speak()); => '저는 김코딩입니다.'

2. 자료구조를 활용해 알고리즘을 푼다.

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

Stack

Stack은 쌓다, 쌓이다는 의미를 가지고 있듯이, 마치 접시를 쌓아 놓은 형태와 비슷한 자료구조이다.
말 그대로 데이터를 순서대로 쌓는 자료구조이다.

일상 생활에서 Stack과 비슷한 예를 찾아볼 수 있다.

Ex)

좁은 골목에 차들이 천천히 들어가는데 알고보니 막힌 골목이었다. 다섯대의 차들이 있었는데 마지막에 있는 다섯번째 자동차가 먼저 후진하여 나와야하는 상황이다.
여기서 골목은 자료구조 Stack, 자동차는 데이터로 비유할 수 있다.
예시에서 말하듯이, 가장 먼저 들어간 자동차는 가장 나중에 나올 수 있다. 반대로 가장 나중에 들어간 자동차는 가장 먼저 나올 수 있다. Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다. 이런 Stack 자료구조의 정책을 LIFO (Last In First Out) 혹은 FILO (First In Last Out)이라고 부른다.

실사용 예시

컴퓨터에서 Stack은 브라우저의 뒤로가기, 앞으로가기 기능을 구현할 때 활용된다.

브라우저에서 자료구조 Stack이 사용될 때에는 다음과 같은 순서를 거친다.
1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
2. 뒤로가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

이렇게 자료구조 Stack을 이용하면, 뒤로가기 와 앞으로 가기 버튼을 구현할 수 있다.

Queue

Queue는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다. Stack과는 반대되는 개념으로, 먼저 들어간 데이터가 먼저 나오는 FIFO 또는 LILO을 특징으로 가지고 있다.

일상생활에서의 예시

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

이렇게 가장 먼저 진입한 자동차가 가장 먼저 빠져나간다. 반대로 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.

실사용 예시

Queue는 컴퓨터에서도 광범위하게 활용된다. 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하려면 어떻게 해야하나?

1. 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 Queue에 들어간다
2. 그리고 Queue에 들어온 문서를 순서대로 인쇄한다.
   만약 Queue 에 들어온 순서대로 출력하지 않는다면, 결과물이 뒤죽박죽일 것이다.

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

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

• 일반적으로 프린터는 속도가 느리다.

• CPU는 프린터와 비교하여 , 데이터를 처리하는 속도가 빠르다.

• 따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 후, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.

• 프린터는 인쇄작업 Queue에서 데이터를 받아 일정한 속도로 인쇄한다.

• 유튜브와 같은 동영상 스트리밍 앱을 통해 영상을 볼때, 다운로드 된 데이터가 영상을 재생하기에 충분하지 않은 경우가 있다. 이때 영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생한다.

퀴즈

• Array.prototype 에는 Stack, Queue 사용을 위해 어떤 메서드가 존재하는가?
  => Stack은 FILO 이니까 pop을 사용해서 뒤의 값을 제거한다. Queue는 FIFO이니까 shift로 앞에 값을 제거해준다.

• 배열로 Stack, Queue를 사용할 때 주의해야 할 사항은 어떤 것이 있는가?

• 배열로 Stack을 사용할 때 , push, pop이외에 필요한 메서드를 어떻게 구현하는가?

• 반대로 Queue를 사용할 때 push, shift 이외에 필요한 메서드를 어떻게 구현하는가?

• JS의 배열과 Stack, Queue는 어떤 차이가 있는가?