카카오 블라인드 공채에서는 2년간 누적합을 활용하는 문제가 출제되었습니다.
또 한 번 나오기 쉽지 않겠지만, 누적합이 어떤 유형의 문제를 효율적으로 해결할 수 있는지 살펴보도록 하겠습니다.
누적합은 구간의 변화
를 효율적으로 처리할 수 있는 알고리즘입니다.
최적의 광고 위치(구간)
을 구하도록 요구합니다.시청시작시간
& 시청종료시간
으로 구성여기서 시청자의 재생 구간 정보 logs를 가공하는 과정에서 누적합을 적용할 수 있습니다.
누적합을 적용하지 않는 다면, 매 log당 시청시간만큼의 연산
이 필요합니다.
누적합을 적용한다면, 매 log당 2번의 연산
과 마지막에 전체를 순회하며 누적을 구하는 2 * N번의 연산
만이 필요합니다.
파괴되지 않은 건물의 숫자
를 구하도록 요구합니다.