Data structure 자료 구조

안녕하세요 씨즈입니다:)
오늘은 자료구조에 대해서 알아봅시다!

1. Data Structure(자료구조)란?

• 자료구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법입니다.
• 자료구조의 종류에는 배열, 딕셔너리, 튜플, 리스트 등 여러가지가 있습니다. 하지만 모든 목적에 부합하는 자료 구조는 없습니다. 따라서 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하는 것이 중요합니다.
• 자료구조는 언어별로(ex. JavaCript, Python...) 지원하는 양상이 다릅니다.
• 각 언어가 가진 자료구조의 종류와 그것에 대한 사용 방법을 익히는 것이 중요하지만, 무엇보다 각 자료구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료구조를 선택하는 것이 중요합니다.
• 언어별로 지원하는 자료구조의 양상이 다르더라도 개념을 올바르게 이애한다면 해당 언어에 맞추어서 사용하기만 하면 됩니다.

2. 왜 자료구조를 사용할까?

데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼치기 때문입니다.

예를 들어 여성분들이 화장품을 담기에 효율적인 것은 캐리어? 백팩? 에코백? 파우치?
정답은 파우치입니다. 화장품 몇 개를 담으려고 캐리어를 갖고 다닌다면 얼마나 무겁고 힘들겠어요
정말 비효율적이죠?
캐리어는 언제 사용할까요? 해외 여행을 가는 경우처럼 많은 양의 짐을 한 번에 이동시킬 때 사용하죠

• 이처럼 자료구조란, 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말합니다.

3. 자바스크립트에서 사용되는 자료 구조

• Array
• Object
• Map, Set
• Stack & Queue
• Tree

4. Array 배열

키를 사용해 식별할 수 있는 값을 담은 컬렉션은 객체라는 자료구조를 이용해 저장합니다. 객체만으로도 다양한 작업을 할 수 있지만 개발을 진행하다보면 첫 번째 요소, 두 번째 요소, 세 번째 요소 등과 같이 순서가 있는 컬렉션이 필요할 때가 생깁니다.
이처럼 순서가 있는 컬렉션을 저장할 때 쓰는 자료구조가 배열 Array 입니다.

- 배열 선언

아래 두 문법을 사용하면 빈 배열을 만들 수 있습니다.

1. let arr = new Array();
2. let arr = [];

대부분 두 번째 방법으로 배열을 선언하는데, 이때 대괄호 안에 초기 요소를 넣어주는 것도 가능합니다.

let fruits = ["사과", "오렌지", "자두"];

5. Queue 큐

큐(queue)는 배열을 사용해 만들 수 있는 대표적인 자료구조로, 배열과 마찬가지로 순서가 있는 컬렉션을 저장하는 데 사용합니다.
아래처럼 배열을 사용해서 간단하게 큐를 구현할 수 있습니다.

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1

• 데이터를 집어 넣을 수 있는 선형(linear) 자료구조입니다.
• 먼저 집어넣은 데이터가 먼저 나옵니다. FIFO(First In First Out) 라고도 부릅니다.
• 데이터를 집어 넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있습니다.
• 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용됩니다.

6. Stack 스택

스택을 사용하면 가장 나중에 집어넣은 요소가 먼저 나옵니다. 이런 특징을 줄여서 후입선출(Last-In-First-Out, LIFO)이라고 부릅니다.
큐와 마찬가지로 배열을 사용해서 스택을 구현할 수 있습니다.

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3

• 데이터를 집어넣을 수 있는 선형(linear) 자료형입니다.
• 나중에 집어넣은 데이터가 먼저 나옵니다. 이 특징을 줄여서 LIFO(Last In First Out)라고 부릅니다.
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있습니다

7. Tree 트리

트리는 노드로 이루어진 자료 구조입니다. 앞서 보인 큐, 스택은 선형 주로의 자료 구조입니다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미하는데 트리는 비선형 구조입니다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적으로 구성 되어있습니다.
선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 들어나는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 포현에 초점이 맞춰져 있습니다.
컴퓨터의 directory 구조가 트리의 대표적인 예가 될 수 있습니다.

>관련 용어

• Root Node: 트리 구조에서 최상위에 존재하는 노드
• Node: 트리의 구성요소에 해당하는 요소
• Edge: 노드와 노드를 연결하는 연결선
• Leaf Node: 밑으로 또 다른 노드가 연결되어 있지 않은 노드
• Sub-Tree: 큰 트리(전체)에 속하는 작은 트리
• Level: 트리에서 각 층별로 숫자를 매김
• Height: 트리의 최고 레벨

8. Map, Set

맵(Map)

맵은 키가 있는 데이터를 저장한다는 점에서 객체와 유사합니다. 다만, 맵은 키에 다양한 자료형을 허용한다는 점에서 차이가 있습니다.
맵에는 다음과 같은 주요 메서드와 프로퍼티가 있습니니다.

• new Map() - 맵을 만듭니다.
• map.set(key, value) - key를 이용해 value를 저장합니다.
• map.get(key) - key에 해당하는 값을 반환합니다. key가 존재하지 않으면 undefined를 반환합니다.
• map.has(key) - key가 존재하면 true, 존재하지 않으면 false를 반환합니다.
  map.delete(key) - key에 해당하는 값을 삭제합니다.
  map.clear() - 맵 안의 모든 요소를 제거합니다.
  map.size - 요소의 개수를 반환합니다.

예시:

let map = new Map();
map.set('1', 'str1');	// 문자형 키
map.set(1, 'num1');		// 숫자형 키
map.ste(true, 'bool1')  // 불린형 키
// 객체는 키를 문자형으로 변환시킵니다.
// 맵은 키의 타입을 변환시키지 않고 그대로 유지합니다. 따라서 아래의 코드는 출력되는 값이 다릅니다.
alert(map.get(1));	// 'num1'
alert(map.get('1')); // 'str1'
alert(map.size);	// 3

-맵은 키로 객체를 허용합니다. 객체를 키로 사용할 수 있다는 점은 맵의 가장 중요한 기능 중 하나입니다. 객체에는 문자열 키를 사용할 수 있지만 객체 키는 사용할 수 없습니다.

• 맵은 삽입 순서를 기억하기 때문에 맵의 요소를 반복 작업할 수 있습니다. 객체가 프로퍼티 순서를 기억하지 못하는 것과는 다릅니다.

셋(Set)

셋은 중복을 허용하지 않는 값을 모아놓은 특별한 컬렉션입니다.
주요 메서드는 다음과 같습니다.

• new Set(iterable) - 셋을 만듭니다. 이터러블 객체를 전달 받으면(대개 배열을 전달받음) 그 안의 값을 복사해 셋에 넣어줍니디ㅏ.
• set.add(value) - 값을 추가하고 셋 자신을 반환합니다.
• set.delete(value) - 값을 제거합니다. 호출 시점에 셋 내에 값이 있어서 제거에 성공하면 true, 아니면 false를 반환합니다.
• set.has(value) - 셋 내에 값이 존재하면 true, 아니면 false를 반환합니다.
• set.clear() - 셋을 비웁니다.
• set.size - 셋에 몇 개의 값이 있는지 세줍니다.
  셋 내에 동일한 값(value)이 있다면 set.add(value)을 아무리 많이 호출하더라도 아무런 반응이 없을 겁니다. 셋 내의 값에 중복이 없는 이유가 바로 이 때문입니다.

방문자 방명록을 만든다고 가정해 봅시다. 한 방문자가 여러 번 방문해도 방문자를 중복해서 기록하지 않겠다고 결정 내린 상황입니다. 즉, 한 방문자는 '단 한 번만 기록’되어야 합니다.

이때 적합한 자료구조가 바로 셋입니다.

let set = new Set();

let john = { name: "John" };
let pete = { name: "Pete" };
let mary = { name: "Mary" };

// 어떤 고객(john, mary)은 여러 번 방문할 수 있습니다.
set.add(john);
set.add(pete);
set.add(mary);
set.add(john);
set.add(mary);

//셋에는 유일무이한 값만 저장됩니다.
alert(set.size); // 3

for (let user of set) {
  alert(user.name); // John, Pete, Mary 순으로 출력됩니다.
}

• 셋은 값의 유일무이함을 확인하는데 최적화되어있습니다.
• 셋은 중복이 없는 값을 저장할 때 쓰이는 자료구조입니다.

Today I Leaned

---

제 글이 조금이라도 도움이 되었으면 좋겠습니다.
읽어주셔서 감사합니다.

Seize the day!

---