푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 트리를 구현하고 서브트리의 개수를 구하는 문제입니다. 각 노드의 부모를 저장할 parent배열을 만든 후 parent[루트]의 값을 -1로 설정해줍니다. 루트번호에서 dfs함수를 돌려서 트리를 구성해주는데 저는 여기서 조건을 두 가지를 걸었습니다. 간선이 무방향으로 주어지다 보니 부모 노..

✏️문제 링크 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 일단 문제를 보기에 앞서 두 수를 a, b 라 하면 a와 b의 최대공약수는 m=gcd(a,b)이고, 최소공배수는 a*b/m입니다. 즉 문제에서 최대공약수와 최소공배수가 주어지는데 정답으로 출력하고자 하는 두 개의 자연수의 곱은 최대공약수 * 최소공배수가 되어야 합니다. 이는 최소공배수와 최대공약수를 구하는 식을 보시면 당연한 결과입니다 int형으로 하면 ..

✏️문제 링크 https://www.acmicpc.net/problem/14433 14433번: 한조 대기 중 첫째 줄에 한 팀에 속한 플레이어의 수 N(1 ≤ N ≤ 300)과 트롤픽의 수 M(1 ≤ M ≤ 300), 각 팀의 팀원들이 원하는 트롤픽의 수 K1, K2(1 ≤ K1, K2 ≤ 500)가 주어진다. 다음 K1개의 줄에 걸쳐 두 수 i, j(1 ≤ www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 두 팀이므로 각 팀마다 이분 매칭을 구현해주면 됩니다. https://pooreumjung.tistory.com/338 Algorithm 공부 #26 - 이분 매칭(Binary Matching) Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알..

✏️문제 링크 https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 기본적인 이분 매칭 알고리즘을 구현하는 문제입니다. https://pooreumjung.tistory.com/338 Algorithm 공부 #26 - 이분 매칭(Binary Matching) Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의..