'백준 11003번' 태그의 글 목록

백준 11003번 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net ● N과 L이 5,000,000이하 이므로 일반적으로 O(nlogn)의 시간복잡도를 가지는 정렬 알고리즘을 사용할 수 없음 ● O(n)의 시간 복잡도로 해결해야 하므로 슬라이싱 윈도우를 덱으로 구현하기 ● 덱의 마지막 위치에서부터 now보다 큰 값은 덱에서 제거 ● 덱의 마지막 위치에 now값 저장 ● 덱의 첫 번째 위치에서부터 L의 ..

Algorithm/BOJ 2024. 2. 28. 20:58

이전 1 다음