자바스크립트로 배우는 SICP - 12. 집합과 리스트 자료구조
집합과 리스트를 추상화 해보자! 언제나 쌍과 리스트 자료구조는 함께!
2023-11-04 | 독서 | 3min
오늘은 집합에 대한 연산들을 구현하는 방법에 대한 내용이다! 우선 책에서는 다음과 같은 순서대로 집합을 구현하고 있다!
- 순서 없는 목록(리스트 자료구조)으로 집합 구현하기
- 합집합 구하는 함수
- 교집합 구하는 함수
- 주어진 요소가 집합에 속하는지 확인하는 함수
- 집합에 객체를 추가하는 함수
- 순서 있는 목록(크기 순으로 나열된 리스트 자료구조)로 집합 구현하기
우선 주어진 요소가 집합에 속하는지를 확인할 수 있게 된다면, 해당 함수를 나머지 세 연산을 위한 함수를 구현하는데 이용할 수 있을 것이다.
문제는, 순서 없는 목록으로 구현했을 경우 집합 간 연산을 진행할 때 피연산 대상 집합의 모든 원소들을 순회해야한다는 단점이 생긴다. 이는 곧 연산에 필요한 단계 수를 만큼 만들기에 타 연산에도 부정적인 영향을 끼치게 된다.
그러면 더 좋은 방법은 없을까? 책에서는 이 방법으로 리스트를 이용하되 크기 순서가 있는 리스트 자료구조를 이용하고 있다. 순서가 있을 경우, 합집합이나 교집합 연산에서 중복 제거 대상이 되는 요소를 확인하기 위해 모든 집합 내의 값을 순회할 필요가 없어진다.
예를 들어, 만약 두 집합 a, b의 합집합을 본다면 a의 집합의 원소들을 순회하며 집합 b의 리스트 객체의 원소들과 크기 비교가 가능해진다. 이때, 크기 관계가 설정되었다는 의미는 a의 원소를 b와 비교할 때 들어갈 확률이 50%라는 것이며 이는 단계수를 으로 줄여준다!
여기에 리스트 자료구조의 원소 배치 방식을 이진 트리 방식을 이용한다면 더욱 단계 수를 줄여줄 수 있다! 이진 트리의 장점은 부모 노드의 원소 즉, head 를 비교한 뒤 그 이후로 비교할 부분이 자식 노드가 헤드가 되는 브랜치만 비교하면 되기에 비교가 진행될수록 앞으로 비교해야할 대상이 로 줄기에 단계수가 logarthic하게 감소한다!
이번 내용은 알고리즘 관련 내용이 많이 도움이 많이 되었다! 생각보다 알고리즘에 대한 소개이지만 이렇게 추상화와 관련해서 함수 구현을 해보니 확실히 이해에 배가 되는 느낌을 받았다. 이렇게 알고리즘을 배워도 정말 좋을 것 같다…! 쨋든 오늘도 알찼다!