전체 글

머지소트트리 (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는 그래프 분석, 순환 검출, 도미노 문제, 인터넷 네트워크 분석, 강한 결합성을 가진 시..

코드 (코사라주 알고리즘)#include #include #include #include #include #include #include #include #include using namespace std;const int MAX_N = 10003;int v, e, a, b, cnt = 1, visited[MAX_N];bool finished[MAX_N];vector adj[MAX_N], radj[MAX_N];vector> res;stack stk;void dfs(int x) { visited[x] = 1; for(int i : adj[x]) { if(!visited[i]) { dfs(i); } } stk.push(x);}void dfs2..

MH-SR602로 간이 보안시스템 만들기오늘은 간이 보안시스템 만들기로 돌아왔습니다. 누구나 집에 모르는 사람이 들어오면 어쩌지 싶은 걱정이 있을텐데 그거 방지하려고 직접 제작할 생각을 했습니다. 인식하면 경고등 울리고 누가 왔는지 사진 찍고 휴대폰에 알림오는 게 기본 구상입니다. 근데 이제 저인 걸 인식을 시켜야할텐데 그건 어떻게 할지 고민 좀 해봐야할 거 같습니다. 아두이노만으로는 어려울 거 같고 라즈베리파이를 추가해야하나... 상상도는 무인 단속기처럼 생각해봤는데, 생각보다 만들기 쉬울 거 같기도 합니다. 근데 이제 Wi-Fi 모듈이 없어서 쿠팡에 급하게 시켜놨습니다. 일단 기본 연결만 하고 2일 정도 뒤에 와이파이 모듈 오면 완성해보려고요. 포스팅은 나눠서 진행할 겁니다.준비물아두이노 UnoMH-..

2004 I2C LCD로 장식만들기연말이 가까워지면서 불빛 장식들이 하나 둘 보이는데, 집에는 하나도 없어서 아두이노랑 2004 I2C LCD로 장식을 한 번 만들어보기로 했습니다. 준비물2004 I2C LCD 디스플레이 모듈아두이노 Uno점퍼 케이블 (M-F로 준비하면 편합니다.)https://github.com/johnrickman/LiquidCrystal_I2C 사이트 들어가서 라이브러리 다운 받기 (I2C LCD 모듈을 제어하기 위해 필요한 LiquidCrystal_I2C 라이브러리)연결 방법GND: 아두이노의 GND에 연결VCC: 아두이노의 5V에 연결SDA: 아두이노의 A4 핀에 연결 (I2C 데이터)SCL: 아두이노의 A5핀에 연결 (I2C 클럭)자세한 설명은 https://kocoafab...

코드#include #include #include #include using namespace std;typedef long long ll;ll n, q, num[100003], x, y, a, b;vector tree;void init(int s, int e, int node) { if (s == e) { tree[node] = num[s]; } else { int mid = (s + e) / 2; init(s, mid, node * 2); init(mid + 1, e, node * 2 + 1); tree[node] = tree[node * 2] + tree[node * 2 + 1]; }}ll query(int s, int e, int l, int r, int node) { if (s > r..

코드#include #include #include #include #include using namespace std;int tc, n, a, b, res, r = 200003, t = 200003;vector> v;int main() { cin >>tc; while (tc--) { cin >> n; v.resize(n); res = 0; r = 200003; t = 200003; for (int i = 0; i > v[i].first >> v[i].second; } sort(v.begin(), v.end()); // 1차 면접 순으로 정렬한 후, 1등과 그보다 2차 면접 성적이 나은 사람들을 뽑음 for (pair pa : v) { if (pa.first 풀이사실 테케보..

코드#include #include #include #include #include #include using namespace std;typedef long long ll;const int MAX_N = 2000003;ll n, a[MAX_N];vector tree;void update(vector &tree, int idx, ll diff) { while(idx &tree, int idx) { ll ans = 0; while(idx > 0) { ans += tree[idx]; idx -= (idx & -idx); } return ans;}int find_kth(int x) { int s = 1; int e = MAX_N; while..

코드#include #include #include #include #include #include using namespace std;typedef long long ll;ll MAX_N = 1000003;ll n, a;vector tree;void update(vector &tree, ll idx, ll diff) { while(idx &tree, ll idx) { ll ans = 0; while(idx > 0) { ans += tree[idx]; idx -= (idx & -idx); } return ans;}// k번째를 찾는 과정// 사탕은 인덱스별로 저장되어있고, 개수가 저장되어 있기 때문에 정렬된 상태// 이분탐색을 통해서 개수가 많으면 ..