득이공간

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 7장. 트리 7-1. 트리 7-2. 이진 트리 7-3. 세그먼트 트리 7-4. LCA 📌 7-1. 이진 트리 * 트리의 특징 - 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다. - 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. - 트리의 부분 트리 역시 트리의 모든 특징을 따른다. - 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. * 트리의 구성 요소 - 노드: 데이터의 index와 value를 표현하는 요소 - 에지: 노드와 노드의 연결 관계를 나타내는 선 - 루트 노드: 트리에서 가장 상위에 존재하는 노드 - index..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 6장. 그래프 6-1. 유니온 파인드 6-2. 위상정렬 6-3. 다익스트라 6-4. 벨만-포드 6-5. 플로이드-워셜 6-6. 최소 신장 트리 📌 6-1. 유니온 파인드 * 유니온 파인드 - 그래프 내의 임의 두 노드가 서로 연결되어있는지 판별하기위해 사용되는 부분 알고리즘 * 유니온 파인드 용어 - union 연산: 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음 - find 연산: 두 노드가 같은 집합에 속해 있는지를 확인, 자신의 대표 노드를 찾아준다. * 유니온 파인드 동작 원리 1. 대표 노드 저장 배열에 각 노드를 초기화 2..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 5장. 정수론 5-1. 소수 구하기 5-2. 오일러 피 5-3. 유클리드 호제법 📌 5-1. 소수 구하기 * 소수 - 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수 - 1과 자기 자신 외에 약수가 존재하지 않는 수 * 에라토스테네스의 체 - 시간 복잡도: O(Nlog(logN)) * 에라토스테네스의 체 동작 원리 1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성 2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. - 이때 처음으로 선택된 숫자는 지우지 않..

1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int A, B; cin >> A >> B; int C, D; cin >> C >> D; int Child, Parent; if (B == D) { Child = A + C; Parent = B; } else { Child = A * D + C * B; Parent = B * D; } int X = max(Child, Parent);..

11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long N; cin >> N; long long P = N; for (int i = 2; i 1) { P = P - P / N; } cout

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net #include using namespace std; bool PrimeNumber[1000001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int M, N; cin >> M >> N; for (int i = 2; i

11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include #include #include #include using namespace std; const int& MaxSize = 100001; const int& MaxK = 20; int K; int MaxDepth; list Neighbors[MaxSize]; int Depth[MaxSize]; int Parent[MaxK][MaxSize]; queue SearchQueue; bool Visited[MaxSize]; void SearchLC..

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include #include #include using namespace std; const int& MaxSize = 10001; list Children[MaxSize]; pair Tree[MaxSize]; queue SearchQueue; void SearchLCA(int NodeA, int NodeB) { int A = NodeA; int B = NodeB; while (Tree[A].second !..

11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include #include #include using namespace std; const int& MaxSize = 50001; list Neighbors[MaxSize]; pair Tree[MaxSize]; queue SearchQueue; bool Visited[MaxSize]; void SearchLCA(int NodeA, int NodeB) { int A = NodeA; int B = NodeB; while (Tree[A].second != T..

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include #include using namespace std; const int& DivNum = 1000000007; int Count, StartIndex; long long MulTree[1048576 * 2]; void UpdateValue(int Index, int Value) { int CurIndex = StartIndex + Index; MulTree[CurIndex] = Valu..