세그먼트 트리구간 쿼리(Query)와 업데이트를 효율적으로 처리하기 위한 트리특정 구간의 합, 최소값, 최대값 등을 빠르게 계산. O(logN)범위 합 구하기, 구간 최소값/최대값 구하기누적합의 경우 합계를 구할 때만 사용할 수 있고, 특정 값이 업데이트될 경우 나머지 값들도 모두 업데이트가 되어야 함.세그먼트 트리의 경우 구간내의 다양한 값들을 구할 수 있고, 업데이트될 경우 몇개의 수만 업데이트하면 됨. 즉, 구간내의 다양한 값(최대값, 최소값)과 업데이트가 빈번하게 일어날 경우, 누적합이 아닌 세그먼트 트리 사용세그먼트 트리 초기화배열에 대해 세그먼트 트리를 형성하기 위해서는 이분탐색과 비슷한 느낌으로 2개씩의 합을 구하고, 구한 합에 대해 또 2개씩 합을 구하며 최종 한 개의 합까지 구합니다.만약..

그래프그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조여러 요소(정점) 간의 관계를 나타내기 위해 사용구성요소로는 정점, 간선, 가중치가 있음.분류방향 그래프(Directed Graph): 간선에 방향이 있습니다. (A,B)는 A→B를 의미하며, B→A는 별개의 간선으로 취급됩니다.무방향 그래프(Undirected Graph): 간선에 방향이 없으며 (A,B)와 (B,A)가 동일합니다.가중치 그래프(Weighted Graph): 간선에 가중치가 포함된 그래프입니다.비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프입니다.트리계층적 구조를 표현하는 특수한 형태의 그래프무방향이면서 사이클이 없는 연결 그래프임의의 두 정점을 연결하는 Simple Path가 유일한 ..

참고 문제https://www.acmicpc.net/problem/17182 포스팅 목적플로이드 워셜과 다익스트라의 개념을 알고 있다면 두 개를 혼용해서 사용할 수 있는걸 알 수 있습니다.그래서 위 문제 풀이를 위해 플로이드 워셜이 아닌 다익스트라를 N번 수행했습니다.다익스트라 코드는 평소와 같이 작성을 했지만 제출했을 때 메모리 초과가 발생하여 이유를 찾는 과정에서 다음번에도 실수할 수 있을 것 같은 반례를 찾아서 기록하기 위해 작성합니다.최초 다익스트라 코드static void Dijkstra(int start) { PriorityQueue pq = new PriorityQueue(((o1, o2) -> o1[1] - o2[1])); pq.offer(new int[]{start, 0}); ..

글을 작성하는 이유최근 문제를 풀면서 키워드 유추 -> 접근법 생각 -> 검증 -> 코드로 구현 순으로 풀이를 진행하는 연습을 하고 있습니다.이 과정에서 접근법에 대해 코드로 구현하는게 잘 되지 않는다고 느껴져서 이유를 생각해보고, 어떻게 개선해나갈지 정리하고자 글을 작성하게 되었습니다. 참고 문제https://school.programmers.co.kr/learn/courses/30/lessons/77886  키워드 유추0과 1로 이루어진 어떤 문자열 xx를 최대한 사전 순으로 앞에 오도록x에 있는 "110"을 뽑아서임의의 위치에 삽입접근법 생각문자열 x에서 "110"을 추출추출 후 남은 문자열에 대해서도 계속해서 추출최종적으로 남은 문자열에서 마지막 0의 위치를 탐색추출한 "110"을 순차적으로 마지..