나쿠리 개발 메모장

매일 상상만 하던 random access + O(logN) 삽입 삭제가 이미 있다니 . . (only g++) #include #include #include using namespace __gnu_pbds; using namespace std; #define ordered_set tree int main(){ ordered_set oSet; // idx 번째 iterator 반환 oSet.find_by_order(idx); // value의 idx를 반환 (value보다 작은 원소 개수를 반환) oSet.order_of_key(value); oSet.insert(v); oSet.erase(v); } 활용 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는..

개요 유니온 파인드(Union-Find)는 서로소 집합(Disjoint Set) 자료구조를 표현하는 알고리즘이다. Disjoint Set은 상호 배타적인(공통 원소가 없는) 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 본문 유니온 파인드 구현 유니온 파인드는 크게 세가지 연산으로 구성된다. 초기화 : N 개의 원소를 각각의 집합으로 초기화 Union : 두 개의 원소가 속한 각각의 집합을 하나로 합침 Find : 원소가 속한 집합을 반환 유니온 파인드는 배열 구현과 트리 구현으로 나뉘는데, 주로 트리 구현을 이용한다.(트리가 더 빠르다) 배열 구현 배열 기반 구현은 매우 간단하다. 초기화 : Arr[i] = i 와 같이 원소를 각자의 집합에 초기화시킨다. Union : 모든..

개요 두 포인터(Two Pointers) 혹은 슬라이딩 윈도우(Sliding Window)라고 부른다. 1차원 배열에서 2개의 포인터를 조작하며 값을 얻는 기법이다. 본문 예를 들어 1차원 배열에서 구간 합의 경우의 수를 찾는 문제가 있다고 하자. 위와 같이 브루트포스로 경우의 수를 찾게 된다면 O(N^2)가 될 것이다. N의 범위가 10만을 넘기기만 해도 시간 초과가 나버리게 된다. 이럴 때 필요한게 두 포인터다. 두 포인터(Two Pointers) front와 back 처럼 두 개의 포인트를 잡고 시작한다. 현재 합이 20보다 작으므로 b를 뒤로 움직여 부분합을 증가시킨다. 합이 20보다 커질 때 까지 b 포인터를 뒤로 움직인다. 20이 된 경우의 수가 있다면 count를 증가시킨다. 위처럼 합이 2..

DFS(Depth First Search) DFS(깊이 우선 탐색)는 그래프의 탐색 방법 중 한 가지이다. DFS는 크게 세 가지 과정으로 나뉜다. 한쪽으로만 계속 방문 더 이상 방문할 정점이 없으면, 이전 정점으로 이동 처음 정점으로 돌아가면 탐색 종료 DFS의 구현 정점 방문 정보 기록을 목적으로 스택을 활용하면 된다. 방문 여부는 배열에 저장한다. 정점을 방문할 때 출발 정점을 스택에 PUSH 하면 된다. 이때 방문 여부는 출발 정점, 도착 정점 둘 다 처리한다. 더 이상 방문할 정점이 없을 경우 스택에서 POP 하면서 이전 정점으로 돌아가며 다시 확인하면 된다. 모든 정점을 방문했을 경우를 배열로 확인하여 탐색을 종료하면 끝이다. 다음 정점 방문 (스택에 이전 정점 추가, 둘 다 방문 배열 체크)..

개요 그래프는 정점과 정점을 잇는 간선의 모임이며 데이터의 표현 방식이다. 그래프 자체가 알고리즘이라기 보단, 그래프를 근거로한 여러 알고리즘들이 존재한다. 본문 그래프의 종류 그래프의 집합 표현 V = Vertex E = Edge V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)} V(G3) = {A, B, C, D} E(G3) = {, , } 그래프의 구현 인접 행렬 기반 V*V 크기의 2차원 배열을 사용하여 구현한다. 인접 리스트 기반 연결리스트를 기반으로 그래프를 구현한다. 무방향 그래프의 경우 정점 노드를 둘다 연결해야함에 주의 그래프 탐색 알고리즘 대표적으로 DFS와 BFS가 있다. DFS(Depth First Searc..

트리(Tree) 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 비선형 자료구조이다. 트리를 만드는 도구를 만들어 놓으면 다양한 목적으로 활용이 가능하다. 트리의 관련 용어 노드(node) - 트리의 구성요소(A, B, C, D, E) 간선(edge) - 노드와 노드를 연결하는 선 루트 노드(root node) - 트리 구조에서 최상위 노드(A) 단말 노드(terminal node) - 아래로 노드가 연결 되어 있지 않은 노드(C, D, E) 내부 노드(internal node) - 단말 노드를 제외한 모든 노드(A, B) 부모 노드(parent node) 계층적 구조에서 위에 연결되어 있는 노드(A는 B,C의 부모 노드) 자식 노드(child node) 계층적 구조에서 아..

테이블(Table) 맵(Map) 혹은 사전 구조(Dictionary)라고도 불리운다. 테이블은 데이터가 key와 Value가 쌍을 이루는 자료구조이다. key : 중복되지 않는 값 value : 실질적인 데이터 key를 기반으로 value를 탐색해야 하기 때문에 value를 근거로 key를 만드는 공식이 필요하다. 그렇지만 key와 value가 완전히 구분되지 않고 value의 일부를 key로 활용하는 경우도 있다. Ex) 학번이라는 value를 key로 활용 (학번은 중복되지 않기 때문) O(1)라는 빠른 속도를 가지지만 많은 공간이 낭비되는 문제가 발생한다. struct StudentInfo { int id; string name; }; StudentInfo arr[30000000]; arr[2020..