boraBong

💬 문제 https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/ 💬 Idea O(N**2)의 풀이밖에 떠오르지 않아서 혹시나..? 하고 제출해봤지만 역시나 😊😊!!!! O(N)의 풀이여야 효율성 테스트를 통과할 수 있었다. 따라서 O(N)의 풀이를 도출하려 해봤지만 도저히 O(N)의 시간복잡도를 갖는 풀이가 생각나지 않았다. 그래서 다른 블로그를 참고했는데, 평균값의 원리라는 수학 공식을 새로 알게되었다 !! 평균값의 원리 💡 구간의 평균은 부분구간의 평균 중 가장 작은 부분구간의 평균보다 크다. 평균은 어느 두 수가 있을 때 가장 작은 수보다 큰 값을 가진다. 이 원리로 생각해보았을 때, 원소가 4개인 그룹의 평균은 앞..