정리 노트

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 상황 0과 1로만 이루어져 있는 bit들의 stream이 입력으로 들어오는 상황에서 최근 들어온 k개의 bit 중 1의 개수를 구해야 하는 상황이 있다고 합시다. 가장 쉽게 생각할 수 있는 방법은 최근 k개의 bit들을 저장해서 개수를 세는 방법입니다. 새로운 bit가 들어오면 가장 예전의 bit를 버린다면 스트림으로 들어오는 입력에서 1의 개수를 셀 수 있을 것입니다. 자료구조 queue를 사용한다면 어렵지 않은 해결책입니다. 하지만, 저장해야 할 bit 용량이 너무 커서 메모리에 담을 수 없다면 어떻게 해야 할까요..