ArrayDeque
-
Array DequeCS 지식/자료구조 2021. 1. 29. 17:37
Array Deque AbstractCollection 클래스와 Deque, Cloneable, Serializable 인터페이스를 상속받는 클래스 특징 사이즈 제한이 없다. ( -> 입력받는 크기에 따라 resize 된다.) 외부 동기화가 없는 상태에서, 멀티 쓰레드에서 동시 엑세스가 안된다. == Thread Safe를 보장하지 않는다.) 요소로 null을 저장할 수 없다. Stack과 LinkedList보다 빠른 속도 Thread-safe 멀티 스레드 프로그래밍에서 일반적으로 어떤 메소드나 변수, 또는 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램 실행에 문제 없음 하나의 메소드가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 해당 메소드를 호출해서 동시에 함께 실행해도 각 스..
-
BOJ) 최솟값 찾기 (11003 번)알고리즘/백준 2021. 1. 29. 16:36
최솟값 찾기 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우를 이용하는 문제로, N개의 수와 윈도의 크기 L이 주어진다. D(i) = A(i-L+1) ~A(i) 중의 최솟값이라고 할 때, D에 저장되는 값을 출력하는 문제다. 즉, 자신의 위치에서 L칸 앞선 칸들 중 최솟값을 찾는 문제다. 처음에는 우선순위 큐로 시도하다가, 시간초과가 떴다. 아무래도 최악의 경우에는 O(N)이 추가돼서 그런 것 같다. (while을 통해 인덱스 범위를 검증하는 과정) 그래서 Deq..