개발하는 사막여우

세그먼트 트리란 ? 배열 또는 리스트와 같은 데이터 구조를 이용하여 구간에 대한 질의를 효율적으로 처리하는 자료구조 주어진 구간에 대한 쿼리 연산을 빠르게 수행할 수 있도록 도와줌. 주로 구간 합, 최솟값 최댓값 등. 트리 구조를 사용하여 데이터를 분할하고 각 분할된 영역에 대한 요약정보를 저장. 이를 통해 트정 구간에 대한 연산을 빠르게 수행할 수 있음 트리를 구축하는 초기 비용이 크지만, 이 후 구간 질의에 대해 빠르게 답을 제공할 수 있음으로 효율적 세그먼트 트리 구조 시간복잡도 트리를 구축: O(N) 합, 곱 계산(쿼리 연산): O(logN) 값의 갱신(업데이트 연산): O(logN) => N은 배열의 크기이며, 구간에 대한 연산을 처리하는 경우 logN만큼의 시간이 들기 때문에 세그먼트 트리의 ..

BFS란 루트 노드 (혹은 시작 노드)에서 시작하여 인접한 노드를 먼저 방문하는 알고리즘입니다. 즉 DFS와 같이 깊이를 먼저 탐색하는 것이 아니라 자신 주변을 넓게 탐색하여 너비 우선 탐색이라고 불립니다. BFS로 최단경로를 찾을 수 있는 이유는 한 정점에서 연결되는 모든 길을 "한번씩" 탐색하기 때문입니다. 특정 노드와 연결된 노드 사이의 길이는 1이기 때문에 같은 방식으로 모든 노드 사이의 거리를 구할 수 있기 때문입니다. 하지만 가중치가 있는 그래프의 경우 BFS를 사용할 수 없습니다 ! BFS의 특징 그래프 탐색 시, 어떤 노드를 방문했는지 여부를 반드시 검사해야 합니다. 검사하지 않았을 경우, 무한루프에 빠질 수 있습니다. BFS 알고리즘은 일반적으로 선입선출(FIFO)의 특징을 가지는 큐 자..

우선순위 큐란 ? - 일반적인 큐의 구조 FIFO(First In First Out)의 구조를 가지지만, 데이터가 들어온 순서대로 빠져나가는 것이 아니라, 우선순위를 결정하고, 우선순위에 따라 데이터가 출력되는 구조입니다 . - 내부가 힙의 구조로 되어있기 때문에 O(nlogn)의 시간복잡도를 가지게 됩니다. - 배열에 값을 추가하면서 따로 정렬하지 않더라도 자동으로 정렬되는 것이 장점입니다. 우선순위 큐 선언 import java.util.PriorityQueue; PriorityQueue hq = new PriorityQueue(); 우선순위에 따른 최대, 최소 힙 - 최소힙: 최솟값이 우선순위인 큐 import java.util.PriorityQueue; PriorityQueue hq = new P..