책너두 (코딩 인터뷰 완전분석) 48일차 (17.21, 17.26)

17. 어려운 연습문제

17.21 막대 그래프의 부피

• 히스토그램(막대 그래프)을 상상해 보자. 누군가가 히스토그램 위에서 물을 부었을 때, 이 그래프가 저장할 수 있는 물의 양을 계산하는 알고리즘을 설계하라. 단, 막대의 폭은 1이라고 가정하자.

17.26 드문드문 유사도

• 서로 다른 단어로 구성된 두 문서의 유사도는 단어들의 교집합의 크기 나누기 합집합의 크기로 정의할 수 있다. 즉, 정수로 이루어진 두 문서 {1, 5, 3}과 {1, 7, 2, 3}의 유사도는 0.4가 된다. 왜냐하면 두 문서의 교집합의 크기는 2이고 합집합의 크기는 5이기 때문이다. 유사도의 밀도가 굉장히 ‘희박’할 것 같은 문서가 굉장히 많이 주어져 있다(각 문서는 ID로 표현된다). 여기서 희박하다는 뜻은 임의의 두 문서의 유사도가 0이 될 확률이 높다는 뜻이다. 이때, 유사도가 0보다 큰 모든 문서 ID 쌍과 그들의 유사도를 반환하는 알고리즘은 설계하라. 비어 있는 문서를 출력해서는 안 된다. 각 문서는 서로 다른 정수로 이루어진 배열로 표현되었다고 가정해도 좋다.