레야몬

1. 문제 각 테스트케이스 첫째 줄 장소의 수 $N(2\le N\le 500)$과 도로의 수 $M(1\le M\le {10}^4)$가 주어짐. 0~N-1까지 장소의 번호가 매겨지는데 -2- 시작점 S, 도착점 D \((S \neq D, 0 \leq S, D V 도로는 최대 한 개이며 U->V는 V->U와 다르다. 입력의 마지막 줄에는 0이 두 개가 있다. 각 테스트케이스에 대해 거의 최단 경로 길이를 출력하며 없는 경우에는 -1을 출력하라 2. 재정의 최단 경로에 포함되는 도로 제외 최단 경로 3. 해결방법 - ..

나는 스위핑으로 풀었다. 분할 정복 풀이를 원하는 사람은 다른 블로그로 -> -> 1. 문제 2차원 평면 상에 n개의 점이 주어져 있을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. $n(2\le n\le 100,000)$ $\left|x\right|,\left|y\right|\le 10000,x,y\in \mathbb{Z}$ 각 점의 x, y 좌표가 주어짐 가장 가까운 두 점의 거리의 제곱을 출력 2. 재정의 n개의 점들 중 가장 가까운 두 점 사이 거리 구하기 3. 해결 방법 Vertex.push_back({x, y}) 좌표들을 x축을 기준으로 오름차순 정렬하기 제일 왼쪽 부터 차례대로 점들을 확인하며 스위핑을 수행 set container에는 고..

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다. 1. 문제 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 ) $N(1\le N\le 10,000)$, $M(1\le M\le ,100,000)$ N과 M 절 $(1\le ,\left|i\right|,\left|i\right|\le N)$ i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다. 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자 ex) Vertex[2*a].push_back(2*b-1) 그..

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다. 1. 문제 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 ) $N(1\le N\le 10,000)$, $M(1\le M\le ,100,000)$ N과 M 절 $(1\le ,\left|i\right|,\left|i\right|\le N)$ i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다. 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자 ex) Vertex[2*a].push_back(2*b-1) 그..

LCA 2 하위 호환이라서 똑같은 코드로 바로 풀었다. 정답은 아래 링크에 있다. https://leyamon.tistory.com/entry/C-11438%EB%B2%88-LCA-2-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%ED%9D%AC%EC%86%8C-%EB%B0%B0%EC%97%B4 [C++] 11438번 LCA 2 - 자료 구조, 트리, 최소 공통 조상, 희소 배열 문제 N($2\le N\le 100,000$)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1부터 N가지 번호가 매겨져 있으며 루트는 1이다. 각 ..

문제 N($2\le N\le 100,000$)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1부터 N가지 번호가 매겨져 있으며 루트는 1이다. 각 노드의 쌍 M($1\le M\le 100,000$)개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하라. 노드의 개수 N 트리 상에 연결된 두 정점 (2~N) 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 M 정점 쌍 (N+1+M) M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 문제 재정의 스패닝 트리가 주어질 때 최소 공통 조상을 출력하라. 해결 방법 희소 배열로 부모 저장, LCA로 빠르게 탐색 실수한 점, 개선한 점 MAX_LOG의 크기를 가진 배열에 MAX_LOG번째 값..

문제 문자열간 간선 정보를 알려줄 때 트리를 구성하고 사전 순서가 앞서도록 DFS를 한 결과를 출력하라. 정점의 개수 n(1 n; for(int i=0; i> k; vector v; for(int j=0; j> str; v.push_back(str); } root->insert(v, 0); } } int main() { cin.sync_with_stdio(0); input(); root->print(0); return 0; } 트라이를 종만북에 있는데로 구성하고 이를 이용해 문제를 풀려고 하니 잘 되지 않았다. 노드 하나에 문자를 넣으면 단어와 단어 사이를 구별하는 것이 어려웠다. 이렇게 딱 틀을 닫고 보니 문제를 전혀 풀 수 없었던 것이다. 다른 사람이 짠 코드를 보고 나서야 map으로 문자열이 들어간..

#include #define FOR(i, k, N) for(int i=k; i> w >> n; FOR(i, 1, n) cin >> num[i]; } int main() { cin.sync_with_stdio(0); input(); FOR(i, 1, n-1) { FOR(j, i+1, n) { int s = w - num[i] - num[j]; if(s < 0) continue; if(weight[s]) { cout