joseph0528 코딩 블로그

그래프(Graph) 그래프란 정점과 간선으로 이루어진 집합을 말한다. 이런 이미지가 있다고 할 때 숫자가 쓰여있는 원을 정점 정점 사이를 잇는 선을 간선 이라고 한다. 이때 간선은 두 정점 사이 여러 개 있을 수 있으며, 방향이 존재하거나 가중치가 존재하는 등 여러 형태가 있으며, 이를 이용한 다양한 그래프가 존재한다. 트리(Tree) 트리란 그래프의 종류 중 하나로 나무처럼 생겼다고 해서 붙여진 그래프의 하위분류이다. 트리는 그래프와 비슷하게 생겼지만 방향을 제외했을 때, 사이클이 존재하면 안 된다. 그림 1은 그래프는 될 수 있지만 2-3-4-5의 사이클이 존재하기 때문에 트리일 수 없다. 그림 2는 사이클이 존재하지 않기 때문에 그래프와 트리 모두 해당된다. 또 그래프는 다른 정점들과 떨어진 정점들..

문제에 쓰여있는 그대로 R를 루트노드라고 하고 LCA(U, V)를 구해주면 끝인 문제이다. 이 문제를 처음 봤을 때 LCA의 sparse table를 입력마다 갱신하는 방법이 바로 떠오르겠지만 그럴 경우 코드를 작성하지 않아도 안된다는 것을 알 수 있다. 그럼 어떻게 해야 할까 이 그림은 위 문제의 테스트케이스를 그래프로 나타낸 것이다. 이때 (U, V)에 대해 R의 위치는 1. R 이 LCA(U, V) 보다 위에 있을 때, 2. R 이 V -> LCA(U, V) 사이에 있는 노드와 연결되어 있을 때, 3. R 이 U -> LCA(U,V) 사이에 있는 노드와 연결되어있을 때, 4. R이 루트 노드를 거쳐 U, V를 가야 할 때 이렇게 총 4개가 나오게 된다. 그럼 처음부터 따져보자. 위 그림은 1번 경우..

이 문제는 여러 가지 풀이 방법이 있지만 이 글에선 유니온 파인드(줄여서 유파)를 이용한 풀이를 사용하겠다. 이 문제를 간단히 요약하면 사용할 수 있는 정점이 주어지면 한 정점에서 다른 정점으로 갈 수 있는 모든 경우의 수를 구하라는 문제이다. 이때 n개의 정점들이 이어져있다고 해보자. n개의 정점들은 자신을 제외한 모든 정점에게 갈수 있다고 할 때 이 그룹에서 나올 수 있는 경우의 수는 n*(n-1)/2 개가 된다. 이 글에선 이걸 이용할 것이다. 일단 처음에 한 정점을 기준으로 번호를 다시 부여해준다.(이 글에선 1번 정점을 기준으로 했다.) 번호를 부여할때 자신의 부모 노드의 번호를 같이 저장한 뒤 입력을 받을 때 새로 부여된 자신의 번호와 부모의 번호를 함께 저장한다. 그 뒤 자신에게 부여된 번호..

문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다. 즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사..

https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 이 문제는 전에 올렸던 사무실 이전과 같은 방식의 문제이다. https://joseph0528.tistory.com/77 BOJ 16121(사무실 이전)풀이 https://www.acmicpc.net/problem/16121 16121번: 사무실 이전 첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나..

https://www.acmicpc.net/problem/16121 16121번: 사무실 이전 첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나머지를 출력한다. www.acmicpc.net 티어에 비해? 간단했지만 구현 때문에 말아먹은 문제이다. 인접한 두 점의 거리는 모두 1이기 때문에 제곱수의 규칙을 알면 쉽게 할 수 있다. 1부터 5까지만 표시해보자면 1^2=1,2^2=4,3^2=9,4^2=16,5^2=25 나열하면 1 4 9 16 25 이렇게 나오는 걸 알 수 있다. 여기서 규칙을 찾아보면 3,5,7,9 씩 커진다. 즉 전에 커진 수+2만큼을 전수에 더하면 (n+1)^2를 구할 수 있는 것이다. 그렇기 때문에 전 노드에서..

solved.ac 티어 : 골드 3 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제의 풀이는 생각보다 간단하다. 1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다. 문제에 있는 예시로 설명을 해보겠다 괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다. 1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다. 일단 3부터 시작하..

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이문제는 의외로 간단한데 어떤 노드에서 와 연결된 노드들 중에 재일 마지막 노드까지의 거리가 첫 번째로 큰 값과 두 번째로 큰 값의 합이 그 노드를 포함했을 때 가장 긴 길이이다. 이걸 dfs으로 탐색하면서 노드별로 가장 긴 길이 중에서도 가장 긴 길이를 출력하면 된다 . 예시로 봤을 때 4번 노드를 포함하는 최대 길이는 8이다. 4의 자식 노드를 포함하는..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18437 18437번: 회사 문화 5 총 N명의 직원이 재직 중인 회사가 있고, 각 직원은 1번부터 N번까지 번호가 매겨져 있다. 이 회사는 수직적인 구조를 가지고 있고, 대표를 제외한 모든 직원은 한 명의 직속 상사를 갖고 있다. www.acmicpc.net 컴퓨터가 켜져 있는 상태를 1, 컴퓨터가 꺼져있는 상태를 0으로 두고 구간을 1 또는 0으로 변경한 뒤 구간 합을 출력하면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu[N]; ll cnf=0..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/14288 14288번: 회사 문화 4 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다. BOJ 14268(회사 문화 2)풀이 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번..