1. 온라인 쿼리특징쿼리가 주어지면 즉시 처리하고 결과를 반환해야 한다.입력받은 순서대로 쿼리를 처리한다.실시간 데이터 업데이트나 연속된 요청 처리가 필요한 문제에서 사용사용해야 하는 상황1. 실시간 응답이 필요한 경우사용자가 요청할 때마다 즉시 결과를 반환해야 하는 문제ex) 게임 서버에서 사용자의 실시간 요청 처리2. 데이터가 점진적으로 업데이트 되는 경우데이터가 동적으로 변화하며, 각 쿼리마다 최신 상태를 반영해야 하는 문제ex) 배열 값이 자주 변경되고, 변경된 값을 기반으로 쿼리를 처리하는 경우3. 데이터 크기가 작거나 중간 규모인 경우매 쿼리마다 즉시 처리하더라도 성능 문제가 없는 경우알고리즘 예시세그먼트 트리펜윅 트리2. 오프라인 쿼리특징쿼리를 미리 모아서 일괄적으로 처리한다.쿼리의 순서를 ..
자료구조 및 알고리즘
오프라인 쿼리와 Mo's Algorithm오프라인 쿼리는 쿼리를 즉시 처맇지 않고, 미리 저장해 두었다가 특정 ㅈ건에 따라 일괄적으로 처리하는 알고리즘 설계기법을 말한다. 이 방법은 데이터가 많고 쿼리가 많은 상황에서 효율적인 처리를 가능하게 한다. 1. 오프라인 쿼리의 특징즉시 응답하지 않음 - 쿼리를 입력받을 때 바로 처리하지 않고, 나중에 한 번에 처리한다.정렬 기반 최적화 가능 - 쿼리를 정렬하거나 특정 조건에 따라 순서를 조정하여 효율성을 높일수 있다.시간 복잡도 최적화 - 적절한 데이터 구조와 알고리즘을 사용하면 쿼리의 총 실행시간을 줄일 수 있다.2 . 오프라인 쿼리의 장점배치 처리 - 쿼리를 정렬하거나 재구성한 뒤 효율적으로 처리하므로 전체 실행 시간이 줄어든다.특정 패턴 최적화 - 예를 ..
map과 unordered_map의 차이 mapunordered_map순서오름차순 정렬정렬 없음구현트리 구조해시 테이블탐색 시간log(N)O(1)삽입 시간log(N)O(1) 요약map은 정렬 순서를 보장하고 unordered_map은 보장하지 않는다.unordered_map은 hash 기반으로 map보다 속도가 빠르다.map은 BST(Binary Search Tree) 기반으로 해시 충돌에서 안전하다.set과 unordered_set도 동일하게 각각 트리, 해시 기반이다.multimap과 multiset은 BST 기반이다.참조https://zshchun.github.io/posts/map%EA%B3%BC-unordered-map%EC%9D%98-%EC%B0%A8%EC%9D%B4/
unordered_map과 배열의 성능 차이오프라인 쿼리 문제를 풀다가 unordered_map을 이용하면 시간초과가 나고 배열을 사용하면 시간이 단축되는 경험을 했다. 둘 다 접근할 때 O(1)으로 알고 있었는데, 어디서 차이가 날까 생각해보았다. 해시충돌 때문이라고 넘어갈까 했지만 자세히 알아보고 기록해두는 게 좋을 거 같아서 포스팅하기로 결정했다. 1. unordered_map vs 배열a) unordered_map의 특성시간 복잡도평균적으로 O(1) 시간에 접근 가능핮만 최악의 경우 O(N)으로 느려질 수 있음 (해시 충돌 발생 시)캐시 활용도unordered_map은 내부적으로 해시 테이블을 사용하며 데이터가 메모리 상에 분산되어 저장된다.따라서 캐시 적중률(cache hit rate)가 낮아질..
머지소트트리 (merge sort tree)머지 소트 트리는 세그먼트 트리의 변형으로, 특정 구간에서 정렬된 데이터를 효율적으로 처리할 수 있는 자료구조이다. 주로 구간 내 특정 값의 개수를 세거나 k번째 작은 수를 찾는 문제 등에 활용된다. 1. 머지 소트 트리의 개념머지 소트 트리는 세그먼트 트리와 비슷하지만, 각 노드에 구간에 해당하는 데이터를 정렬된 상태로 저장한다. 세그먼트 트리에서 각 노드가 단일 값을 저장하는 반면, 머지 소트 트리에서는 리스트 또는 배열 형태로 정렬된 값을 저장한다.2. 머지 소트 트리의 구성리프 노드: 각 배열의 원소를 저장내부 노드: 해당 구간의 두 하위 노드 데이터를 합친 후 정렬한 리스트를 저장3. 구현 방법1) 트리 구축void build(int s, int e, ..
오일러 경로 테크닉오일러 경로 테크닉에서는 DFS(깊이 우선 탐색)을 사용하여 그래프를 순회하면서 특정 정보(노드 방문 순서, 간선 순회 순서 등)를 기록한다. 일반적으로 오일러 투어라고도 불리며, 트리나 그래프의 정보를 flat한 배열 형태로 변환한다. 세그먼트 트리 같은 자료구조에서 효율적으로 처리할 수 있도록 한다. 트리의 dfs 순회를 기반으로 각 노드의 방문 순서 또는 진입/퇴장 시간을 기록한 배열을 생성한다. 세그먼트 트리는 일반적으로 배열을 대상으로 작동하는데, 오일러 경로 테크닉을 사용하면 트리 문제를 배열 문제로 변환하여 세그먼트 트리에서 구간 합, 구간 최대/최소값 쿼리 또는 특정 노드와 서브트리에 대한 작업을 효율적으로 수행할 수 있다. 예시위와 같은 트리구조가 있다. ETT를 사용..
강한 연결 요소 (Strongly Connected Component, SCC)강한 연결 요소(SCC)란 방향 그래프에서 어떤 두 점 u와 v가 있을 때 u -> v와 v -> u 두 방향으로 모두 경로가 존재하는 정점들의 최대 집합을 의미한다.특징SCC는 방향 그래프의 구성 요소무방향 그래프에서의 연결 요소와 비슷하지만, 방향성이 존재하는 그래프에서 정의된다.SCC 내의 모든 정점은 서로 도달 가능해야 한다.DAG로 변환 가능모든 SCC를 하나의 정점으로 압축하면 방향성이 없는 비순환 그래프 (DAG, Directed Acyclic Graph)가 만들어진다.이 DAG는 SCC의 상호 연결 관계를 보여준다.응용SCC는 그래프 분석, 순환 검출, 도미노 문제, 인터넷 네트워크 분석, 강한 결합성을 가진 시..
펜윅트리 (Fenwick Tree, Binary Indexed Tree, BIT)펜윅트리는 트리 구조를 1차원 배열로 구현한 자료구조로, 각 위치에서 특정 구간을 대표하는 값을 저장하여 빠르게 구간 합 등을 계산할 수 있다. 업데이트와 쿼리 연산의 시간 복잡도는 O(logN)이다. 1기반 인덱싱을 사용하기 때문에 배열의 크기를 N + 1 (N은 데이터의 크기)로 설정하는 경우가 많다. 세그먼트 트리보다 상대적으로 구현이 간단하고 메모리 사용량이 적다. 주요 연산 비교연산펜윅 트리세그먼트 트리구간 쿼리O(logN)O(logN)단일 업데이트O(logN)O(logN)구간 업데이트O(NlogN)O(logN) (Lazy Propagation 사용 시)메모리 사용량O(N)O(4 * N) 펜윅 트리 코드#inclu..
그래프에서 음의 사이클 구하기벨만 포드 알고리즘을 이용하는 것과 플로이드 워셜 알고리즘을 이용하면 그래프에서 음의 사이클을 찾아낼 수 있다. 플로이드 워셜 알고리즘을 이용한 방법mp를 그래프라고 할 때, 플로이드 워셜 알고리즘에서 사이클의 존재 여부는 mp[i][i] 값을 통해서 확인할 수 있다. 플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하기 위해 각 정점 i에서 j로 가는 최단 경로를 mp[i][j]에 저장하게 된다.사이클이 없는 경우라면, 어떤 정점에서든 자신으로 돌아오는 경로가 존재하지 않으므로 mp[i][i]는 초기화된 값인 INF를 유지하게 된다.반면, 사이클이 존재하는 경우 해당 경로의 길이를 갱신하게 되어 mp[i][i] (자기 자신에게로 돌아오는 경로)가 INF가 아닌 값..
느리게 갱신되는 세그먼트 트리 (Lazy Propagation)느리게 갱신되는 세그먼트 트리(Lazy Propagation)는 세그먼트 트리에서 구간 업데이트를 더 효율적으로 처리하기 위해 사용하는 기법이다. 구간의 여러 값을 한 번에 갱신하고, 그 후에 구간에 대한 정보를 빠르게 얻어야 할 때 사용된다. 1. 느리게 갱신되는 세그먼트 트리란?기본 세그먼트 트리는 특정 구간의 값(합, 최대값 등)을 빠르게 쿼리할 수 있게 해준다. 그런데 만약 구간 내 모든 값에 동일한 연산(ex. 더하기)을 여러 번 적용해야 하는 경우, 기본 세그먼트 트리로는 비효율적일 수 있다. 최악의 경우 nlogn의 시간이 걸릴 수 있기 때문이다. 이때 느리게 갱신되는 세그먼트 트리를 사용하면 구간 전체에 대한 업데이트를 지연시..
