본문 바로가기

분류 전체보기414

백준 16404 주식회사 승범이네 문제 URL : https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net 문제 접근법 : 오일러 경로 테크 + lazy propagation segtree 문제입니다. dfs를 이용해서 해당노드들의 인덱스를 다시설정해주고 해당노드의 자손들이 몇개나있는지 나올때 확인할수 있으므로 오일러를 이용해서 범위를 셋팅해줄수있습니다. 그후 segtree를 이용해서 update와 query를 이용해서 답을 구하시면 됩니다. .. 2023. 1. 18.
백준 2610 회의준비 문제 URL : https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 문제 접근법 : union find + 플로이드를 이용한 알고리즘 문제입니다. 해당 트리의 개수가 몇개인지 확인한후 트리를 집합대로 분리한후 그집합대로 가장 먼노드중 최소가 될수있을만한 노드를 구하시면 됩니다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3.. 2023. 1. 18.
백준 2617 구슬 찾기 문제 URL : https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제 접근법 : 플로이드를 와샬 알고리즘을 이용하여 쉽게 풀수있습니다. 해당 구슬이 다른구슬보다 큰것이 n/2보다 많은지 해당 구슬이 다른구슬보다 작은것이 n/2보다 많은지 확인해서 값을 구하면됩니다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 .. 2023. 1. 18.
백준 8012 한동이는 영업사원! 문제 URL : https://www.acmicpc.net/problem/8012 8012번: 한동이는 영업사원! 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 www.acmicpc.net 문제 접근법 : 두노드간의 거리문제입니다. 빠르게 구하기위해 LCA의 depth를 이용하면되는데 두정점을 a,b라 할때 depth[a]+depth[b]-2*depth[lca(a,b)] 를 통해 쉽게 구할수있습니다. 소스코드 : //By 콩순이냉장고 #include using namespace std; vector v[30001],depth,iv; int n, m; int parent[.. 2023. 1. 18.

티스토리툴바