1. 온라인 쿼리특징쿼리가 주어지면 즉시 처리하고 결과를 반환해야 한다.입력받은 순서대로 쿼리를 처리한다.실시간 데이터 업데이트나 연속된 요청 처리가 필요한 문제에서 사용사용해야 하는 상황1. 실시간 응답이 필요한 경우사용자가 요청할 때마다 즉시 결과를 반환해야 하는 문제ex) 게임 서버에서 사용자의 실시간 요청 처리2. 데이터가 점진적으로 업데이트 되는 경우데이터가 동적으로 변화하며, 각 쿼리마다 최신 상태를 반영해야 하는 문제ex) 배열 값이 자주 변경되고, 변경된 값을 기반으로 쿼리를 처리하는 경우3. 데이터 크기가 작거나 중간 규모인 경우매 쿼리마다 즉시 처리하더라도 성능 문제가 없는 경우알고리즘 예시세그먼트 트리펜윅 트리2. 오프라인 쿼리특징쿼리를 미리 모아서 일괄적으로 처리한다.쿼리의 순서를 ..
자료구조 및 알고리즘
오프라인 쿼리와 Mo's Algorithm오프라인 쿼리는 쿼리를 즉시 처맇지 않고, 미리 저장해 두었다가 특정 ㅈ건에 따라 일괄적으로 처리하는 알고리즘 설계기법을 말한다. 이 방법은 데이터가 많고 쿼리가 많은 상황에서 효율적인 처리를 가능하게 한다. 1. 오프라인 쿼리의 특징즉시 응답하지 않음 - 쿼리를 입력받을 때 바로 처리하지 않고, 나중에 한 번에 처리한다.정렬 기반 최적화 가능 - 쿼리를 정렬하거나 특정 조건에 따라 순서를 조정하여 효율성을 높일수 있다.시간 복잡도 최적화 - 적절한 데이터 구조와 알고리즘을 사용하면 쿼리의 총 실행시간을 줄일 수 있다.2 . 오프라인 쿼리의 장점배치 처리 - 쿼리를 정렬하거나 재구성한 뒤 효율적으로 처리하므로 전체 실행 시간이 줄어든다.특정 패턴 최적화 - 예를 ..
머지소트트리 (merge sort tree)머지 소트 트리는 세그먼트 트리의 변형으로, 특정 구간에서 정렬된 데이터를 효율적으로 처리할 수 있는 자료구조이다. 주로 구간 내 특정 값의 개수를 세거나 k번째 작은 수를 찾는 문제 등에 활용된다. 1. 머지 소트 트리의 개념머지 소트 트리는 세그먼트 트리와 비슷하지만, 각 노드에 구간에 해당하는 데이터를 정렬된 상태로 저장한다. 세그먼트 트리에서 각 노드가 단일 값을 저장하는 반면, 머지 소트 트리에서는 리스트 또는 배열 형태로 정렬된 값을 저장한다.2. 머지 소트 트리의 구성리프 노드: 각 배열의 원소를 저장내부 노드: 해당 구간의 두 하위 노드 데이터를 합친 후 정렬한 리스트를 저장3. 구현 방법1) 트리 구축void build(int s, int e, ..
오일러 경로 테크닉오일러 경로 테크닉에서는 DFS(깊이 우선 탐색)을 사용하여 그래프를 순회하면서 특정 정보(노드 방문 순서, 간선 순회 순서 등)를 기록한다. 일반적으로 오일러 투어라고도 불리며, 트리나 그래프의 정보를 flat한 배열 형태로 변환한다. 세그먼트 트리 같은 자료구조에서 효율적으로 처리할 수 있도록 한다. 트리의 dfs 순회를 기반으로 각 노드의 방문 순서 또는 진입/퇴장 시간을 기록한 배열을 생성한다. 세그먼트 트리는 일반적으로 배열을 대상으로 작동하는데, 오일러 경로 테크닉을 사용하면 트리 문제를 배열 문제로 변환하여 세그먼트 트리에서 구간 합, 구간 최대/최소값 쿼리 또는 특정 노드와 서브트리에 대한 작업을 효율적으로 수행할 수 있다. 예시위와 같은 트리구조가 있다. ETT를 사용..
