혹시 이러한 알고리즘이 있나요?

  • ggabu420
    ggabu420

    이상하게 아무리 생각해봐도 퍼뜩 잘 생각이 안나네요..
    원래 존재하지 않는 건지 제 머리가 나쁜 건지..(아마 후자겠지만)

    n개의 정수 배열이 있을 때, 이들 중 연속하는 k개의 정수 중에서
    최소값을 구해서 이들 최소값들 중 최대값을 구하는 알고리즘을
    보려고 하는데요.

    가령, 1 2 4 3 2 3 1 1 2 라는 배열이 있을 경우,

    1 2 4 의 최소값 1
    2 4 3 의 최소값 2
    4 3 2 의 최소값 2
    3 2 3 의 최소값 2
    ...

    이런식으로 구하면 최종적으로 최소값들 중 가장 큰 수가 2이고
    답은 2가 되는 그런 로직입니다.

    가장 간단하게 생각해낼 수 있는 방법은 O(nk) 인 로직인데..
    이걸 혹시 O(n) 에 할 수 있는 알고리즘이 있을까요?


    10년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    Sliding window min을 참조해 보세요. ;)


    10년 전 link

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