알고리즘/알고리즘 유형
[백준] 11003_최솟값 찾기 - JAVA
백준_11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 덱(deque) 위 문제는 슬라이딩 윈도우와 정렬을 사용하면 될 것 같지만 정렬은 nlog(n)의 시간 복잡도를 가지고, N과 L의 범위가 5,000,000인 이 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결해야 한다. 정렬 대신 슬라이딩 윈도우와 덱(deque)이란 자료구조를 사용하면 이 문제를 풀 수 있다. 덱은 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다. 왼쪽에서는 addFi..
