본문 바로가기

백준

 (497)
[백준 11437번] LCA (C++) 문제링크 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, u, v; int parent[50001]; int depth[50001]; vectornode[50001]; void dfs(int n, int p) { parent[n] = p; //부모..
[백준 3584번] 가장 가까운 공통 조상 (C++) 문제링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N, A, B, X, Y; int parent[10001]; int visited[10001]; int dfs(int n) { if(visited[n..
[백준 25511번] 값이 k인 트리 노드의 깊이 (C++) 문제링크 : https://www.acmicpc.net/problem/25511 25511번: 값이 k인 트리 노드의 깊이 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 간선에는 가중치가 없다. 트리 T에 있는 각 정점에는 서로 다른 값이 부여된다. 트리 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K; int arr[100001]; int parent[100001]; int dfs(int n, int cnt) { if(n==0) return cnt; //루트 ..
[백준 9372번] 상근이의 여행 (C++) 문제링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N, M; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; while(T--) { cin >> ..
[백준 1240번] 노드사이의 거리 (C++) 문제링크 : https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, s, e; vectort[1001]; int dist[1001]; int bfs(int s, int e) { queueq; q.push(s); dist[s]=0; while(!..
[백준 3067번] Coins (C++) 문제링크 : https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N, M; int arr[21]; int dp[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; w..
[백준 1068번] 트리 (C++) 문제링크 : https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, remove_node, root, result; vectort[51]; //트리 int visited[51]; //방문처리용 void dfs(int node) { visited[node]=1; b..
[백준 5582번] 공통 부분 문자열 (C++) 문제링크 : https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string s1, s2; int dp[4001][4001]; int result; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s1 >..

티스토리툴바