임의 구간의 최대 평균 및 구간의 합 문제

  • mujugi
    mujugi

    안녕하세요
    혼자 고민해보다가 도저히 모르겠어서

    질문드립니다.

    1. 임의 구간의 최대 평균 문제

    어떤 배열 a 가 있고 배열 안에는 임의의 정수 n개가 들어있습니다

    이 배열의 합의 최대 평균 구간인 L1 ~ L2를 찾는 문제입니다

    O(n)에 가능하다고 하는데 도저히 방법을 모르겠습니다.

    (사실 배열의 모양이 어떤 모양인지도 모르겠습니다)

    원문입니다

    Given a sequence of N 64-bit integers, find a sequence of at least L consecutive integers that has the highest average. O(N^2) not too hard; O(N) possible but much harder. O(NL) follows since there must exist an optimal interval between L and 2L. Hint: can compute average from i to j in O(1) time with O(N) preprocessing by precomputing prefix[i] = a[0] + ... + a[i] for each i. Then the average of the interval from i to j is (prefix[j] - prefix[i]) / (j - i + 1).

    1. 임의의 구간의 합 문제

    (1,3),(2, 4),(6,8),(5.5,9)

    이런 구간 배열이 있을때 union된 최대 거라는
    (1,4), (5.5,9) 즉 3 + 3.5 = 6.5 가 될텐데요

    소수점이 없다고 가정하면 O(n)안에 계산을 할 수 있는데
    소수점이 있을때도 worst O(n)으로 계산 할 수 있을까요?
    일반적으론 정렬해서 O(n log n) 으로 풀린다고 합니다

    감사합니다


    11년 전
6개의 댓글이 있습니다.
  • Being
    Being

    첫 번째 문제를 완전한 선형 시간에 푸는 것은 (발견하기) 매우 어렵습니다. 대신 이분 검색을 활용하는 경우가 종종 있습니다.

    두 번째 문제의 경우 짧게 생각한 결과 불가능하다에 500원 걸겠습니다. :p


    11년 전 link
  • hyunhwan
    hyunhwan

    Being // 하지만 radix sort를 쓴다면 어떨까?!


    11년 전 link
  • mujugi
    mujugi

    LIBe // 부동소수점에 스트링변환이라던가 연산을 취하지 않고 기수정렬 할수 있나요?


    11년 전 link
  • haje01
    haje01

    Cumulative Sum을 사용하시면 가능합니다.


    9년 전 link
  • 장홍준
    장홍준

    첫 번째 문제는 각 원소를 (i, i번째 원소까지의 누적합)으로 n개의 점을 만들어 컨벡스헐을 활용하면, 컨벡스헐을 구하는데 O(N log N)이 걸리는 걸 제외하면 O(N)에 풀 수 있습니다.
    (올해 코더스하이 예비소집 문제와 거의 유사한 것 같아 링크 남겨드립니다. https://www.acmicpc.net/problem/10213)

    두 번째 문제는 정렬하는 시간을 제외하면 O(N)에 풀리는데, 결국 정렬의 시간복잡도가 O(N)일 수 있냐는 것인데 이는 불가능합니다.


    9년 전 link
  • Fate
    Fate

    S[i] = sum(A[1]...A[i]) 라 할 때 (S[i]-S[j])/(i-j) 가 최대인 값을 구하는 문제인건가요? monotonous queue를 이용하는 방법은 없을까요?


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.