728x90 반응형 최솟값 찾기1 [백준] 11003번 : 최솟값 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 일정 범위 안에서 최솟값을 구하는 문제로 슬라이딩 윈도우와 정렬을 사용하면 된다. 윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i - L + 1부터 i까지이므로 L로 생각하면 된다. 최솟값을 찾기 위한 정렬을 O(nlogn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 해당 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결하기 위해 덱(deque).. 2024. 1. 10. 이전 1 다음 728x90 반응형
