정리 노트

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 크기가 N인 집합에 속한 원소들만 담은 스트림이 있다고 합시다. 이 스트림에서 서로 다른 원소들의 개수를 구하려면 집합을 만들어 스트림의 모든 아이템을 집합에 넣으면 됩니다. 집합은 동일한 아이템을 원소로 가지지 않기 때문에 이를 통해 쉽게 찾을 수 있습니다. 하지만 생성해야 할 집합의 크기가 너무 커져 메모리에 올릴 수 없는 정도라면 어떻게 찾아야 할까요? Flajolet-Martin(ver. 1) Flajolet-Martin 알고리즘을 통해 이를 대략적으로 구할 수 있습니다. 이 알고리즘을 위해 아이템을 \(..