DSU(Disjoint Set Union) / Union Find

Disjoint Set Union Disjoint Set(서로소 집합)이란 서로 공통된 원소가 없는 집합을 말합니다. 보통 Union Find 라고 불립니다. Union 2개의 집합을 1개의 집합으로 합치는 방식입니다. 기본적으로 높이 가 작은 쪽을 큰 쪽으로 합칩니다. 유니온 바이 랭크(Union by rank) 두개의 disjoint set 을 합칠 때 항상 작은 쪽을 큰 쪽에 합칩니다. Find 어떤 element가 주어질때, 이 element 가 속해져 있는 루트 를 반환합니다. 아래 예시에서는 3 이라는 원소를 Find 하게 되면 루트인 6이 나오게 됩니다. 경로 압축 경로 압축은 Find 의 시간 복잡도를 개선하기 위해 원소를 Find 할 경우 바로 루트원소가 나올 수 있도록 하는 방법입니다...

자바스크립트의 해시테이블

해시테이블에 대해 공부하게 된 사연.. 백준에서 알고리즘 문제를 풀다 똑같은 로직인데, 배열로 value에 접근할 때와 object를 사용해 구현한 Map 을 통해 value에 접근했을때 속도차이가 유의미하게 나는 것을 경험했다. 자바스크립트에서 배열은 객체 보다 더 나은 성능을 가진다. 자바스크립트의 배열은 배열을 흉내낸 객체이다. 따라서 배열 요소에 접근할 때 일반적인 배열보다 느릴 수밖에 없는 구조적인 단점을 보완하기 위해 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하여 좀 더 배열처럼 동작하도록 최적화하여 구현했다. 위 자료를 근거로 배열과 객체를 모두 사용할 수 있는 경우가 있다면 배열을 통해 value에 접근하는 편이 더 성능상 유리하다는 것을 알았다. (나는 객체를 Map 처럼 만들어서..