Algorithm ๐ง๐ป๐ป457 [๋ฐฑ์ค,c++] 1967๋ฒ - ํธ๋ฆฌ์ ์ง๋ฆ ๋ฌธ์ 1967๋ฒ: ํธ๋ฆฌ์ ์ง๋ฆ ํ์ผ์ ์ฒซ ๋ฒ์งธ ์ค์ ๋ ธ๋์ ๊ฐ์ n(1 ≤ n ≤ 10,000)์ด๋ค. ๋์งธ ์ค๋ถํฐ n-1๊ฐ์ ์ค์ ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด๊ฐ ๋ค์ด์จ๋ค. ๊ฐ์ ์ ๋ํ ์ ๋ณด๋ ์ธ ๊ฐ์ ์ ์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ฒซ ๋ฒ์งธ ์ ์๋ ๊ฐ์ ์ด ์ฐ www.acmicpc.net ์ฝ๋ #include #include #include using namespace std; int max_len = 0; int max_node; bool visited[10001]; int ans; vectorgraph[10002]; void dfs(int node, int len){ visited[node] = 1; if(max_len>N; for(int i=0; i>a>>b>>c; graph[a].push_back({b,c}); g.. 2022. 7. 11. [๋ฐฑ์ค,c++] 3584๋ฒ - ๊ฐ์ฅ ๊ฐ๊น์ด ๊ณตํต ์กฐ์ ๋ฌธ์ 3584๋ฒ: ๊ฐ์ฅ ๊ฐ๊น์ด ๊ณตํต ์กฐ์ ๋ฃจํธ๊ฐ ์๋ ํธ๋ฆฌ(rooted tree)๊ฐ ์ฃผ์ด์ง๊ณ , ๊ทธ ํธ๋ฆฌ ์์ ๋ ์ ์ ์ด ์ฃผ์ด์ง ๋ ๊ทธ๋ค์ ๊ฐ์ฅ ๊ฐ๊น์ด ๊ณตํต ์กฐ์(Nearest Common Anscestor)์ ๋ค์๊ณผ ๊ฐ์ด ์ ์๋ฉ๋๋ค. ๋ ๋ ธ๋์ ๊ฐ์ฅ ๊ฐ๊น์ด ๊ณตํต ์กฐ์์, ๋ www.acmicpc.net ์ฝ๋ #include #include #include using namespace std; bool visited[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int N; cin >> N; vectorgraph(N + 1); for (int i = 1; i > a >> b; g.. 2022. 7. 11. [๋ฐฑ์ค,c++] 14675๋ฒ - ๋จ์ ์ ๊ณผ ๋จ์ ์ ๋ฌธ์ 14675๋ฒ: ๋จ์ ์ ๊ณผ ๋จ์ ์ ํ๋ก๊ทธ๋จ์ ์ ๋ ฅ์ ํ์ค ์ ๋ ฅ์ผ๋ก ๋ฐ๋๋ค. ์ ๋ ฅ์ ์ฒซ ์ค์๋ ํธ๋ฆฌ์ ์ ์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 100,000) ํธ๋ฆฌ์ ์ ์ ์ 1๋ฒ๋ถํฐ n๋ฒ๊น์ง ์กด์ฌํ๋ค. ๋ค์ ์ค๋ถํฐ N-1๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ์ ์ ์ www.acmicpc.net ์ฝ๋ #include #include using namespace std; vectorgraph; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N; cin>>N; graph.resize(N+1); for(int i=0; i>a>>b; graph[a].push_back(b); graph[b].push_back(a); } int q; cin>>q; for(int i=0;.. 2022. 6. 30. [๋ฐฑ์ค,c++] 6416๋ฒ - ํธ๋ฆฌ์ธ๊ฐ? ๋ฌธ์ 6416๋ฒ: ํธ๋ฆฌ์ธ๊ฐ? ํธ๋ฆฌ๋ ๊ต์ฅํ ์ ์๋ ค์ง ์๋ฃ ๊ตฌ์กฐ์ด๋ค. ํธ๋ฆฌ๋ฅผ ๋ง์กฑํ๋ ์๋ฃ ๊ตฌ์กฐ๋ ๋น์ด ์๊ฑฐ๋(๋ ธ๋์ ๊ฐ์๊ฐ 0๊ฐ), ๋ ธ๋์ ๊ฐ์๊ฐ 1๊ฐ ์ด์์ด๊ณ ๋ฐฉํฅ ๊ฐ์ ์ด ์กด์ฌํ๋ฉฐ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค. www.acmicpc.net ์ฝ๋ #include #include #include #include #include #define MAX 101 using namespace std; vectorindegree[MAX + 1]; unordered_map outdegree; // node, cnt unordered_set node; int edge_cnt = 0; int remove_leaf() { queue q; int remove_cnt = 0; for (auto cur : node) { .. 2022. 6. 30. [๋ฐฑ์ค,c++] 1068๋ฒ - ํธ๋ฆฌ ๋ฌธ์ 1068๋ฒ: ํธ๋ฆฌ ์ฒซ์งธ ์ค์ ํธ๋ฆฌ์ ๋ ธ๋์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. N์ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค์๋ 0๋ฒ ๋ ธ๋๋ถํฐ N-1๋ฒ ๋ ธ๋๊น์ง, ๊ฐ ๋ ธ๋์ ๋ถ๋ชจ๊ฐ ์ฃผ์ด์ง๋ค. ๋ง์ฝ ๋ถ๋ชจ๊ฐ ์๋ค๋ฉด (๋ฃจํธ) -1์ด ์ฃผ์ด์ง๋ค www.acmicpc.net ์ฝ๋ #include #include #include using namespace std; vectorv[51]; bool visited[51]; int N, root; int cnt; void dfs(int start){ if(v[start].empty()){ cnt++; return; } else if(v[start].size()==1){ if(visited[v[start].front()] == true) cnt++; } for(auto it: v.. 2022. 6. 21. [๋ฐฑ์ค,c++] 5539๋ฒ - ์ด์ง ๊ฒ์ ํธ๋ฆฌ ๋ฌธ์ 5639๋ฒ: ์ด์ง ๊ฒ์ ํธ๋ฆฌ ํธ๋ฆฌ๋ฅผ ์ ์ ์ํํ ๊ฒฐ๊ณผ๊ฐ ์ฃผ์ด์ง๋ค. ๋ ธ๋์ ๋ค์ด์๋ ํค์ ๊ฐ์ 106๋ณด๋ค ์์ ์์ ์ ์์ด๋ค. ๋ชจ๋ ๊ฐ์ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ฉฐ, ๋ ธ๋์ ์๋ 10,000๊ฐ ์ดํ์ด๋ค. ๊ฐ์ ํค๋ฅผ ๊ฐ์ง๋ ๋ ธ๋๋ ์๋ค www.acmicpc.net ์ฝ๋ #include #include using namespace std; vectorv; void postorder(int start, int end){ if(start>end) return; if(start==end){ cout 2022. 6. 21. [๋ฐฑ์ค,c++] 9934๋ฒ - ์์ ์ด์ง ํธ๋ฆฌ ๋ฌธ์ 9934๋ฒ: ์์ ์ด์ง ํธ๋ฆฌ ์๊ทผ์ด๋ ์ฌ๋ก๋ฒ ๋์์ ๋์ Donji Andrijevci๋ฅผ ์ฌํํ๊ณ ์๋ค. ์ด ๋์์ ๋๋ก๋ ๊น์ด๊ฐ K์ธ ์์ ์ด์ง ํธ๋ฆฌ๋ฅผ ์ด๋ฃจ๊ณ ์๋ค. ๊น์ด๊ฐ K์ธ ์์ ์ด์ง ํธ๋ฆฌ๋ ์ด 2K-1๊ฐ์ ๋ ธ๋๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. (์๋ www.acmicpc.net ์ฝ๋ #include #include #include using namespace std; vectorheight[1025]; vectorv(1025); void inorder(int start, int end, int level){ if(start > end) return; int mid = (start+end)/2; height[level].push_back(v[mid]); inorder(start, mid-1, level+1).. 2022. 6. 21. [๋ฐฑ์ค,c++] 1655๋ฒ - ๊ฐ์ด๋ฐ๋ฅผ ๋งํด์ ๋ฌธ์ 1655๋ฒ: ๊ฐ์ด๋ฐ๋ฅผ ๋งํด์ ์ฒซ์งธ ์ค์๋ ๋ฐฑ์ค์ด๊ฐ ์ธ์น๋ ์ ์์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. N์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๊ทธ ๋ค์ N์ค์ ๊ฑธ์ณ์ ๋ฐฑ์ค์ด๊ฐ ์ธ์น๋ ์ ์๊ฐ ์ฐจ๋ก๋๋ก ์ฃผ์ด์ง๋ค. ์ ์๋ -1 www.acmicpc.net ์ฝ๋ #include #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); priority_queue left; priority_queue right; int N; cin>>N; for(int i=1; i>inp; if(i==1) left.push(inp); else if(right.empty()){ if(left.top(.. 2022. 6. 21. [๋ฐฑ์ค,c++] 12764๋ฒ - ์ธ์ง๋ฐฉ์ ๊ฐ ์คํ ๋ฌธ์ 12764๋ฒ: ์ธ์ง๋ฐฉ์ ๊ฐ ์คํ ์ฒซ์งธ ์ค์ ์ฌ๋์ ์๋ฅผ ๋ํ๋ด๋ \(N\)์ด ์ฃผ์ด์ง๋ค. \((1 \le N \le 100,000)\) ๋์งธ ์ค๋ถํฐ \(N\)๊ฐ์ ์ค์ ๊ฑธ์ณ์ ๊ฐ ์ฌ๋์ ์ปดํจํฐ ์ด์ฉ ์์ ์๊ฐ \(P\)์ ์ข ๋ฃ ์๊ฐ \(Q\)๊ฐ ์ฃผ์ด์ง๋ค. \((0 \le P \lt Q \le 1,000 www.acmicpc.net ์ฝ๋ #include #include #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N; cin>>N; priority_queue min_heap; // {๋๋๋ ์๊ฐ, ์ข์๋ฒํธ} priority_queue seats; // {์ข์๋ฒํธ, ๋๋.. 2022. 6. 20. ์ด์ 1 ยทยทยท 7 8 9 10 11 12 13 ยทยทยท 51 ๋ค์