[Data_Structure] SET

먹보·2022년 12월 16일
0


업로드중..

✍ Set이란..

Set(집합)은 중복된 원소가 없는, 순서가 없는 자료구조입니다. Set은 수학에서의 집합 개념과 유사하며, 원소를 추가, 제거, 포함 여부 확인 등의 연산을 지원합니다.

📝 Set 의 특징

  • 중복된 원소가 없습니다.

  • 원소의 순서가 없습니다.

  • 원소는 유일한 식별자를 갖고 있습니다.

  • 집합 연산, 즉 원소 추가, 제거, 포함 여부 확인 등의 연산을 지원합니다.

📝 Set 구현 방식 및 작동 원리

  • 데이터들이 저장 될 때 순차적으로 저장되지 않는다.
  • Set에서 요소들이 저장될 때 우선 요소들의 hash 값이 구해지고 그 값에 해당하는 공간(bucket)에 저장된다. ⇒ 그렇기에, 순서가 없고 인덱싱도 없다.
  • 해쉬 값을 기반으로 데이터가 저장되기 때문에 LOOK UP 속도가 빠르다.

위의 내용을 요약해보자면

Set(집합)은 해시 테이블(hash table)을 기반으로 구현됩니다. 해시 테이블은 원소들을 키(key)와 값(value)의 쌍으로 저장하는 자료구조로, 매우 빠른 검색 속도를 제공합니다. Set에서는 각 원소가 유일한 키(key)를 가지며, 값(value)은 불필요합니다. 따라서 Set은 해시 테이블의 키(key)만을 사용하여 원소를 저장하고 검색합니다. 이를 통해 Set은 매우 빠른 검색 속도를 제공하며, 대규모 데이터에서도 효율적으로 작동합니다.

✍️ Set의 장단점 및 예시

📝 장점

  • 중복된 원소를 허용하지 않기 때문에, 데이터의 중복을 효과적으로 제거할 수 있습니다.

  • 원소 추가, 제거, 포함 여부 확인 등의 연산을 지원하기 때문에, 데이터를 관리하기 용이합니다.

  • 해시 테이블 기반으로 구현되기 때문에, 매우 빠른 검색 속도를 제공합니다.

📝 단점

  • 원소의 순서가 없기 때문에, 인덱스를 사용한 접근이 불가능합니다.

  • Set은 객체의 참조(reference)를 사용하여 원소를 저장하기 때문에, 객체를 사용하는 경우 주의해야 합니다. 객체를 수정하면 Set에서 저장된 원소도 함께 수정되기 때문입니다. 이를 방지하기 위해서는 객체를 복사하여 저장해야 합니다.

  • 일반적으로 배열(Array)보다는 검색 속도가 빠르지만, 특정한 상황에서는 성능이 떨어질 수 있습니다. 예를 들어, 원소 개수가 적은 경우 배열보다는 Set이 느릴 수 있습니다.

📝 예시

  • 수학: 수학에서는 집합 개념을 다루는 경우가 많습니다. 예를 들어, 집합 연산을 수행하거나 중복을 제거하고 고유한 원소를 추출하는 경우 Set을 사용할 수 있습니다.

  • 데이터베이스: 데이터베이스에서는 중복된 데이터를 제거하거나 고유한 값만을 추출하는 경우 Set을 사용할 수 있습니다.

  • 웹 프로그래밍: 웹 개발에서는 주로 중복된 값 제거나 고유한 값 추출 등의 작업에 Set을 사용할 수 있습니다. 예를 들어, 웹 페이지에서 중복된 태그를 제거하거나, 중복되지 않은 특정한 값을 추출해야 하는 경우 Set을 사용할 수 있습니다.

  • 자연어 처리: 자연어 처리에서는 특정한 단어나 문장 등의 중복을 제거하고 고유한 값만을 추출해야 하는 경우 Set을 사용할 수 있습니다.

  • 게임 프로그래밍: 게임에서는 플레이어의 고유한 ID나 아이템 등을 추출하기 위해 Set을 사용할 수 있습니다.

✍️ JavaScript 내에서의 Set

Map과 비슷하게 자바스크립트 내에서 Set을 구현하는 방식은 정말로 간단하다.

const mySet = new Set();
// Set 내 요소 추가
mySet.add('apple');
mySet.add('banana');
mySet.add('orange');

// Set 내 요소 확인 
console.log(mySet.has('apple')); // true
console.log(mySet.has('grape')); // false

// Set 내 요소 For 문으로 돌리는 법
for (const item of mySet) {
  console.log(item);
}
// Output: "apple", "banana", "orange"

// Set 내 요소 삭제
mySet.delete('banana');
console.log(mySet); // Set(2) {'apple', 'orange'}

// Set을 배열로 전환하기
const myArray = Array.from(mySet);
console.log(myArray); // ['apple', 'banana', 'orange']

위의 코드를 예제로 보면 알겠지만 Set은 일반적인 자료구조와 동일하기 때문에 배열로 바꾼 후 접근하는 방식이 유용하다.

그렇기 떄문에 Array.from 사용법을 알아두자.

이 방법 외에도 ...[spread] 연산자를 적용하면 배열로 바꿀 수 있지만 성능이 떨어진다고 나와있다.

✍️ Set 시간 복잡도

자바스크립트에서 Set의 기본적인 연산들의 시간 복잡도는 일반적으로 O(1)입니다. 이는 Set에 요소를 추가하거나 삭제하거나 존재 여부를 확인하는 작업을 포함합니다.

하지만 Set을 반복하는 작업의 시간 복잡도는 Set의 크기에 비례하므로 O(n)입니다. 따라서 Set을 반복하는 작업은 Set의 크기에 따라 성능이 영향을 받을 수 있습니다.

profile
🍖먹은 만큼 성장하는 개발자👩‍💻

0개의 댓글