[자료구조] Set 객체 뽀개기 feat. 해시테이블

서두

코딩테스트 문제를 푸는데 중복된 문자열을 제외해야 쉽게 풀 수 있는 문제가 있었다. 

문제에서는 그룹단어를 판별하는 문제였는데, 그룹 단어는 문자열이 반복되거나 1개만 나오면 괜찮은데 다른 문자열이 나열된 이후 기존 문자열이 있으면 그룹단어가 아니다.

ex1) acsssc 여기서 c가 처음에 등장하고, 뒤에 다시 등장하기 때문에 그룹단어가 아니다. 

ex2) acsssd 다시 반복되는 문자열이 없기 때문에 그룹단어다. 

 

배열로 반복문 돌리면서 인덱스에 1을 더해가며 확인하고, 별짓을 다해서 어찌 풀긴 풀었는데 아무리 봐도 이게 효율적이라고 느껴지지는 않았다. 다른 풀이는 어떻게 되는지 구글링을 하는데, 꽤 문제를 오래걸려서 풀면서 여러 방법을 고민하다보니 다들 생각이 비슷했다. 

 

slice이나 split을 사용해서 나열된 값을 분해해서 다른 값을 찾고 그런 식으로 풀었다. 

 

여러 인사이트를 갖기 위해 다른 사람의 풀이도 보지만, gpt에게 똑같이 복붙해서 문제를 어떻게 푸는지도 보고 있는데, Set을 사용하고 있었다. 거의 모르다시피 하고 있어서 이번 기회에 포스팅을 하면서 제대로 알아가려 한다. 

 

Set 을 간단하게 정리하면 다음과 같다. 

• set 객체는 중복되지 않는 유일한 값들의 집합이다.
• set 객체는 다음과 같은 특징을 가진다.
  1. 동일한 값을 중복하여 포함할수 없다.
  2. 요소 순서에 의미가 없다.
  3. 인덱스로 요소에 접근할 수 없다.

 

순서에 관련된 부분을 익히면서 이전에 공부했던 Linked List가 떠올랐다. 

그러나 둘이 다른 점은, Set은 순서를 보장하지 않고, Linked List는 분명한 순서가 있다. 

인덱스가 없다는 공통점이 있는데, 똑같이 인덱스가 없지만 Set은 해당 값이 있는지 바로 확인할 수 있고, Linked List는 처음부터 확인해야 한다. 

 

Set는 요소의 존재 여부를 빠르게 확인할 수 있는 특징을 가지고 있다. O(1)에 바로 찾을 수 있다.

반면에 Linked List는 찾으려면 처음부터 확인해야 하기 때문에 O(n)의 시간이 걸릴 수 있다. 

 

Set은 위치 자체를 지정하지 않기 때문에 값을 삭제할 수는 있지만 값의 위치를 추적할 수는 없다. 

Linked List는 위치를 인덱스로 지정하지 않을 뿐, 노드로 연결되어 있어서 주변 관계를 알기 때문에 위치를 추적할 수는 있다. 다만 O(n)의 시간이 걸린다. 

 

결국 용도의 차이가 있다. Set은 요소의 존재 여부를 빠르게 확인하고 중복을 방지하는데 유용하며,

Linked List는 삽입, 삭제가 빈번한 상황에서 유용하다.

 

Set의 장점

이 둘을 비교하는 것은 사실 부수적인 것이고, Set의 장점을 설명하려 한다. 

처음에 Set이 존재여부를 O(1)에 찾는다고 했는데, 납득이 되지 않았다. 

배열을 떠올려보자. Array.includes 로 확인하거나 indexOf 이런 메서드가 있을 것이다. 

0번 인덱스부터 O(n)의 시간이 걸려야 정상 아닌가?

 

하나 하나씩 찾는게 아니라는 소린데 뭐지?

찾는 것 뿐 아니라 Set의 다른 메서드인 add, delete 또한 O(1)의 시간복잡도가 소요된다. 

 

더하는 것이야 뭐 push도 위치 상관없이 더하니까 O(1)인 것처럼 이해가 되는데, 삭제하는데 어떻게 한번에 삭제한다는거지? 

 

Set은 해시테이블 구조를 사용한다. 

웹서핑만으로는 잘 이해가 되지 않았는데, 자세히 설명되어있는 유튜브 영상을 통해 한번에 이해하게 되었다. 

https://youtu.be/ZBu_slSH5Sk

 

Set 이 중복 여부를 확인하는 과정

간략하게 내가 이해한대로 설명해보자면, 값을 해쉬해서 연산과정을 거쳐 내부적으로 인덱스 넘버링을 하고, 해당 넘버의 위치를 인덱스로 바로 찾는 것이다. 그러니까 결국 값 자체가 하나의 인덱스인 것이다.

 

그래서 해쉬하고 연산과정을 겨쳤을 때 같은 인덱스넘버를 가지게 되면 값이 다른데도 불구하고 같은 해쉬 코드를 가지게 되어 충돌이 발생할 수 있다. 이 때 위에서 언급했던 linked list, tree 등의 자료구조들을 통해 실제로 이 값이 동일한 값이 맞는지를 파악한다. 

 

Set객체는 key : value 의 일반적인 구조가 아니라 value만 있다.

ex) {1,2,3}

 

set.add(3) 을 하게 되면, 3이 어디있는지 1,2,3 하나씩 찾는게 아니라, 3이라는 값을 해쉬해서 해당하는 넘버의 인덱스를 찾고, 값이 없으면 넣게 되고, 값이 있으면 덮어쓰는 것이다. 이를 개방 주소법(Open Addressing)이란 충돌이 일어난 키 값을 비어 있는 다른 주소를 찾아 저장하는 방법이라고 한다. 

그리고 값이 있는지 찾는 방식은 아래와 같은 방식이 있는데, 지금의 지식으로는 이것들을 다 이해하지도, 설명하기도 어려운 것 같다. 내가 설명한 부분은 하나씩 차례로 확인하는 선형 탐색이다. 

선형 탐색 (Linear Probing)
제곱 탐색 (Quadratic Probing)
이중 해시 (Double Hashing)

 

또한 개방 주소법 이외에도 다른 내용들도 있는 것 같다. 

 

 

아무튼 중요한 점 

>>> 중복검사 할 때 가장 효율이 좋다.

 

 

여러 과정을 거치는데도 불구하고 Set의 시간복잡도가 O(1)인 이유

값이 있는지 전체 슬롯에서 인덱스를 파악하기 때문에 값이 있는지는 끝까지 추적하는 것이고, 다만 이러한 일련의 정교한 과정을 거치는데 왜 시간복잡도가 O(1)인 것인가?

 

 

공부하는데 이거 아래에 적기엔 양이 너무 방대하다. 그런데 배울 수록 신기하고 재밌따...!   다음 포스팅에서 계속...ㅎㅎㅎ