11003번 - 최솟값 찾기
전 문제를 풀지 않았습니다 하지만 전 문제를 풀지않았음에도 불구하고 어떻게 푸는지 보였는데 거의 실버3 수준의 슬라이딩 윈도우 인거 같습니다 덱을 사용할 필요도 없는거 같고 배열만 써도 쉬울거 같습니다 슬라이딩 윈도우가 안되는 이유를 설명좀 해주세요
최솟값 연산에는 역원이 없기 때문에 맨 앞의 수가 최솟값이면 이 수가 빠졌을 때 새 최솟값을 알 수 없습니다.
덱트릭없이 부분 최솟값을 모두 찾는 일반적인 슬라이딩 윈도우는 시간복잡도가 O(NL)이기 때문에 시간초과가 발생하기 때문입니다.
만약 덱트릭없이 풀 수 있었다면 문제의 티어와 태그가 다르겠죠?
문제가 쉽다고 느껴진다면 글을 쓰는 대신 그 문제를 쉬운 풀이로 풀고 제보를 하는 것이 현명한 방법입니다.
만약 숫자 5,000,000, 길이 5,000,000 면 연산량이 조단위가 나올 것 같은데요??
댓글을 작성하려면 로그인해야 합니다.
cproblem0429 1년 전
전 문제를 풀지 않았습니다 하지만 전 문제를 풀지않았음에도 불구하고 어떻게 푸는지 보였는데 거의 실버3 수준의 슬라이딩 윈도우 인거 같습니다 덱을 사용할 필요도 없는거 같고 배열만 써도 쉬울거 같습니다 슬라이딩 윈도우가 안되는 이유를 설명좀 해주세요