정화 코딩

https://www.acmicpc.net/problem/27966 #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n; cin >> n; long long ans = (n - 1) + (n - 1) * (n - 2); cout 모든 정점 쌍에 대해서 두 정점 사이 거리의 합이 최소가 되도록 하기 위해서는 하나의 정점을 중심에 두고 나머지 모든 정점을 그 중심 정점에 연결하도록 트리를 구성하면 된다. 이 사실만 알면 쉽게 풀 수 있었던 문제. 아 long long으로 해야 함! (AC)

7회차 - graph, tree, map and set  집합https://www.acmicpc.net/problem/11723다양한 방법으로 풀 수 있는 문제입니다.  1. set을 사용한 풀이단순히 문제에서 설명하는 대로 코드를 작성하면 됩니다.#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m, n; string op; cin >> m; set s; for (int i = 0; i > op; if (op == "add") { cin >> n; s.insert(..

https://www.acmicpc.net/problem/5639 #include #include using namespace std;vector a;void post(int s, int e) { if (s >= e) return; int idx = e; for (int i = s + 1; i a[s]) { idx = i; break; } } post(s + 1, idx); post(idx, e); cout > x) { a.push_back(x); } int n = a.size(); post(0, n);} 이 문제는 트리 구조를 만들어서 뭔갈 한다기 보다는 어떻게 하면 전위 순회..

https://www.acmicpc.net/problem/1967 #include #include using namespace std;vector>> g;vector vst;int maxc = 0;void dfs(int cur, int cnt) { vst[cur] = true; if (cnt > maxc) maxc = cnt; for (auto nxt: g[cur]) { if (!vst[nxt.first]) dfs(nxt.first, cnt + nxt.second); }}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; g = vector..

09-5. 최소 공통 조상 074. LCA (백준 11437번) https://www.acmicpc.net/problem/11437 import sys from collections import deque input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] depth = [0] * (n+1) parent = [0] * (n+1) visited = [False] * (n+1) def bfs(node): que = deque() que.append(node) visited[node] = True level = 1 size = 1 cnt = 0 while que: now = que.popleft() for nxt in tree..

A. 완전 이진 트리 (백준 9934번) https://www.acmicpc.net/problem/9934 #python import sys input = sys.stdin.readline k = int(input()) visit = list(map(int, input().split())) tree = {} for i in range(1, pow(2, k-1)): tree[i] = [i*2, i*2 + 1, 0] for i in range(pow(2, k-1), pow(2, k)): tree[i] = ['.', '.', 0] def inOrder(now): global i if now != '.': inOrder(tree[now][0]) tree[now][2] = visit[i] i += 1 inOrde..

09-3. 이진 트리 070. 트리 순회 (백준 1991번) https://www.acmicpc.net/problem/1991 from sys import stdin n = int(stdin.readline()) tree = {} for _ in range(n): self, left, right = stdin.readline().split() tree[self] = [left, right] def preOrder(now): if now != '.': print(now, end='') preOrder(tree[now][0]) preOrder(tree[now][1]) def inOrder(now): if now != '.': inOrder(tree[now][0]) print(now, end='') inOrd..

09-1. 트리 알아보기 067. 트리의 부모 찾기 (백준 11725번) https://www.acmicpc.net/problem/11725 from sys import stdin import sys sys.setrecursionlimit(10 ** 6) n = int(stdin.readline()) g = [[] for _ in range(n+1)] parent = [0] * (n+1) def dfs(pre, cur): for nxt in g[cur]: if nxt != pre: parent[nxt] = cur dfs(cur, nxt) for _ in range(n-1): a, b = map(int, stdin.readline().split()) g[a].append(b) g[b].append(a) d..