알고리즘/자료구조

[자료구조] 우선순위 큐와 힙

우선순위 큐(Priority Queue) 큐 형태로 우선순위가 높은 데이터가 먼저 나가는 자료구조 cf ) 큐(Queue) 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 ADT(Abstract Data Type) - 객체 우선순위를 가진 요소들의 모음 - 연산 insert(x) 우선순위 큐에 요소 x 추가 remove() 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환 find() 우선순위 큐에서 가장 우선순위가 높은 요소를 반환 구현 방법 배열 또는 연결리스트를 이용 > 삽입 또는 삭제 연산을 위한 시간복잡도는 O(n) ( ∵ 선형 구조의 자료구조 ) 힙 트리 이용 > 힙트리의 높이는 log₂(n+1)이며 힙의 시간복잡도는 O(log₂n) (..

Collection 함수 정리

정렬 관련 Arrays.copyOfRange() 전달받은 배열의 지정된 범위에 해당하는 요소만을 새로운 배열로 복사하여 반환 public static int [] copyOfRange (int [] 복사할 원본 배열, int 원본 배열에서 복사할 범위의 시작 인덱스, int 원본 배열에서 복사할 범위의 끝 인덱스) 반환값 원래 배열에서 지정된 범위를 포함하는 새 배열. (필요한 길이를 얻기 위해 잘리거나 0으로 채워짐) 예외 ArrayIndexOutOfBoundsException - 초기 인덱스, 즉 (from_index)가 원래 배열의 범위를 벗어난 경우 발생 IllegalArgumentException - form_index > to_index 인 경우 NullPointerException - 원래 ..