1개의 댓글이 있습니다.
-
-
JongMan -
Sliding window min을 참조해 보세요. ;)
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Sliding window min을 참조해 보세요. ;)
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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) 에 할 수 있는 알고리즘이 있을까요?
11년 전