알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10999 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.느리게 갱신되는 세그먼트 트리는 해당 링크를 참조해주세요. https://www.acmicpc.net/blog/view/26 느리게 갱신되는 세그먼트 트리를 사용할 수 있다면 바로 구할 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M, K;long long Index[1000001];vector Tree;vector lazy;long long se..

문제 링크입니다. https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 중위 순회를 이용해 푸는 문제였습니다. 1부터 N까지 열이 존재할 때, 트리의 노드를 적정하게 배치하여 하나씩만 위치하게 합니다. 이때, 최대 길이를 가지는 행을 구해주면 되는 문제입니다. 이 문제를 트리를 탐색하는 3가지 방법 중에, 중위 순회 방법이 가장 적당합니다. 왜냐하면, 중위 순회는 왼쪽 자식 -> 부모 -> 오른쪽 자식의 순서로 탐색을 진행하는데 1..

문제 링크입니다. https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net M개 만큼 BFS를 수행하면 되는 문제였습니다. 먼저 노드와 cost를 백터를 통해 이어줍니다. 그 다음 M개만큼 시작점, 끝점을 받아 BFS를 돌려주면 됩니다. 이때 check의 값은 0이 아닌 -1로 해줘야지 조건이 편해집니다. 0로 거리의 값으로 포함되기 때문에 방문여부를 확인하기 위해서 -1를 저장해줬습니다. 또한, 구조가 트리이기 때문에 어느 곳을 먼저 방문했더라도 최단거리가 나옵니다. -> 다익스트라가 아닌 BFS..

문제 링크입니다. https://www.acmicpc.net/problem/10838 10838번: 트리 N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다. 각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다. 트리에 www.acmicpc.net LCA와 같은 원리로 푸는 문제였습니다. A부터 B까지 같은 색을 연결하는 것이 문제의 핵심입니다. 먼저 A와 A의 부모를 모두 찾아서 True로 저장해줍니다. 다음으로 B와 B의 부모를 찾아보는데 True로 저장된 노드를 살펴봅니다. 만약 True로 저장된 노드가 존재한다면 해당 노드가 A와 B의 공통 부모라는 의미입니다. 문제에서 주어진 조건에 따라 1000개 이하로 무조건 ..

문제 링크입니다. https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 오프라인 쿼리 문제였습니다. 간선을 지운다는 것을 거꾸로 생각하는 것이 핵심이였습니다. 들어오는 입력을 먼저 확인하겠습니다. 2번째 줄부터 N-1개 만큼 트리를 확인할 수 있는 정보가 입력됩니다. 예제 입력 1번의 경우는 1번이 2번의 부모, 1번이 3번의 부모라는 의미입니다. 트리 정보가 주어진 후에는 제거할 선과 연결되어 있는 지를 확인할 노드들의 정보..

문제 링크입니다. https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 문제였습니다. 재귀를 통해서 전위 탐색을 후위 탐색으로 출력하면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #include #include #define INF 987654321 using namespace std; int Tree[10001]; int..

문제 링크입니다. https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 중위 순회, 후위 순회의 특징을 알아야지 풀 수 있는 문제였습니다. 중위 순회의 특징은 부모 노드를 기준으로 왼쪽은 왼쪽 트리를 나타내고, 오른쪽은 오른쪽 트리를 나타냅니다. 후위 순회의 특징은 항상 마지막 수는 트리의 부모를 나타냅니다. 더 자세한 내용은 그림을 확인해주세요. 후위 순회와 중위 순회를 통해서 트리를 찾는 것은 확인했습니다. 이제 구현하는 단계가 남았습니다. 부모 노드가 중위 순회에서 어디..

문제 링크입니다. https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리의 순회 방식에 대해서 물어보는 문제입니다. 어떤 방식으로 트리를 순회하는지 이해한다면 풀 수 있는 문제입니다. 3가지 방법의 공통점은 항상 부모 노드인 'A'에서 시작한다는 것입니다. 'A' 노드에서 시작해서 어떤 방식으로 탐색하는지 한번 알아보겠습니다. 1. 전위 순회 2. 중위 순회 3. 후위 순회 전위, 중위, 후위 순회가 어떤 방식으로 이뤄지는지 확인했습니..

문제 링크입니다. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net DFS를 사용하여 푸는 문제입니다. 임의의 점을 하나 선택한 뒤, 해당 점에서 다시 탐색을 하여 답을 구하는 문제였습니다. 1 ~ N까지의 정점이 있을 때, 가장 긴 노드 사이의 거리를 구하는 문제였습니다. 1번 점부터 N번 점까지 모든 경우를 확인하기에는 경우가 너무 많아 시간 초과가 생길 수 있습니다. 따라서 다른 방법을 통해 지름을 구해야하는데 그중 한 ..

문제 링크입니다. https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net DFS를 이용한 문제였습니다. 1번 정점에서 시작해서 가장 긴 거리에 있는 점을 찾은 뒤, 해당 점에서 되돌아오면서 길이를 재는 방법이였습니다. 해당 문제는 두번의 DFS를 사용해야하는 문제였습니다. 1~N번까지의 점 중에서 임의의 점을 하나 선택합니다. 해당 점에서 가장 거리가 먼 점을 하나 확인합니다. 이 점을 X라 하겠습니다.(저는 1번을 임의로 정했습니다...