🔗 문제https://www.acmicpc.net/problem/1655📝 풀이자료 구조 + 우선순위 큐접근법입력으로 들어오는 정수들에 대해 기록하고, 중간값을 N번 찾는 문제입력값 N은 최대 100,000으로 대략적인 시간복잡도는 O(NlogN)으로 잡고 풀어야 한다. 단순하게 생각했을 때, 입력을 받으면서 정렬을 계속 수행한 후 현재 개수/2의 인덱스를 구하면 되지만정렬의 시간복잡도는 O(NlonN)으로 입력값 N에 대해 최대 100,000번 수행한다고 하면 O(N^2)을 넘어서게 된다.그렇다면 어떻게 풀이를 해야할까? 매번 정렬을 수행할 수 없으니 정렬을 유지한 채 값을 기록하고, O(1)로 중간 값을 찾을 수 있어야 한다.자료구조 중 이러한 특성을 가지고 있는 자료구조가 있다.기본적인 정렬을 ..

문제https://www.acmicpc.net/problem/3584 풀이해시 + 그래프 탐색접근법“공통 조상” 이라는 키워드만 보고서는 유니온 파인드를 생각했습니다.그러나 “가장 가까운 공통 조상(Nearest Common Ancestor)”을 구하는 문제로써 Union-Find로 구할 시 루트노드가 나오기에 다른 방식으로 접근했습니다. 두 정점의 부모 노드만 탐색하면 되었기에 일반적인 그래프 탐색을 통해서 접근했습니다. (시간복잡도↓)트리 자료구조로는 인접리스트를 활용했고, 자식 노드가 아닌 부모 노드를 탐색해야 했기에 부모를 기준으로 자식노드를 담는게 아닌 자식 노드를 기준으로 부모 노드를 담았습니다.list.get(부모).add(자식) → list.get(자식).add(부모)a와 b 노드의 공통되..

Union-Find?분리 집합이라고도 불리는 유니온 파인드는 그래프 형태의 자료구조에서 정점들의 연결 정보를 알고 싶을 때 사용하는 알고리즘입니다.분리 집합이라고 불리는 이유는 서로 연결된 정점들을 각각의 집합으로 만들기 때문입니다. DFS(BFS) VS Union Find그래프 형태의 자료에서 연결 정보를 알고 싶을 때 DFS, BFS 탐색을 통해서도 알 수 있습니다.그러나 서로 다른 모든 정점의 연결정보를 구하려면 시간이 오래 걸릴 수 밖에 없습니다.10만개의 정점이 있고, 모든 정점이 서로 연결되있을수도 있다면 두 정점의 연결관계를 탐색하는데 최대 10만번의 탐색이 이루어질 수 있기 때문입니다.또한 이러한 연결관계 탐색이 N번 필요하다면 O(N^2)의 시간이 필요합니다. Union Find를 사용하..

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