Algorithm & 자료구조3 우선순위 큐 (PriorityQueue) PriorityQueue란? 스택과 큐에 대해서는 대부분 잘 알고 있을 것이다. 스택은 후입선출로 나중에 들어간 것이 먼저 나오고, 큐는 선입선출 먼저 들어간 것이 먼저 나온다. 큐이긴 하지만 기존의 큐와는 다른 특징을 가진 우선순위 큐라는 자료구조가 있다. 사용자가 지정한 우선순위를 기반으로 원소를 꺼낸다. /** * Creates a {@code PriorityQueue} with the default initial * capacity (11) that orders its elements according to their * {@linkplain Comparable natural ordering}. */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY.. 2023. 4. 24. 배열에서 합이 n인 연속된 구간 찾기 : 투포인터(Two Pointers) * 2022년 10월 19일 velog에 작성했던 게시글을 옮겨온 글입니다. 원소들의 합이 n이 되는 연속된 구간을 찾는 유형의 문제를 종종 볼 수 있는데 투 포인터 알고리즘을 통하여 해결 할 수 있다. 📈 시간 복잡도 선형 탐색 O(N) 시작점과 끝점을 0번째 인덱스로 지정한다. 부분합이 5와 같을 경우 카운트 한다. 부분합이 5보다 작기 때문에 끝점을 1 증가시킨다. 반대일 경우 시작점을 1 증가시킨다. 2~4를 반복한다. 부분합이 1이므로 끝점을 1증가 시킨다. 부분합이 3이므로 마찬가지로 끝점을 1증가 시킨다. 부분합이 6이므로 시작점을 1증가 시킨다. 부분합이 5이므로 카운트를 한다. 이후 끝점을 1증가 시킨다. 반복한다. 문제 [LeetCode] 977. Squares of a Sorted A.. 2022. 12. 31. 사전에서 단어 찾는 방법 : 이진 탐색(Binary Search) * 2022년 10월 18일 velog에 작성했던 게시글을 옮겨온 글입니다. 사전순으로 정렬이라는 말은 A, B, C.. 혹은 ㄱ, ㄴ, ㄷ 순으로 앞에서 뒤로 작은 것부터 큰 것까지 차례대로 늘어놓은 것을 말한다. 만약 이렇게 정렬된 사전에서 특정 단어를 찾으라고 한다면 우리는 자연스럽게 이진 탐색 방법을 이용할 것이다. 우리도 모르게 사용하고 있는 이진 탐색 알고리즘은 정렬이 되었다고 약속되었을 때 효율적이다. 만약 Canada라는 단어를 찾는다면 우리는 사전 한 가운데를 펼치고 그 페이지에 나오는 단어들의 시작이 C보다 앞인지 뒤인지를 판단한다. 만약 뒤라면 그 뒷 페이지는 더이상 볼 필요가 없어진다. 다시 남은 절반의 페이지들의 가운데를 펼쳐 앞의 과정을 반복하다 보면 단 몇번만에 찾을 수 있다... 2022. 12. 31. 이전 1 다음
