Algorithm Problems (212) 썸네일형 리스트형 [백준/C++] 16234번: 인구 이동 문제https://www.acmicpc.net/problem/16234문제 요약N × N 크기의 땅이 있고, 땅은 1 × 1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, 그곳에는 사람들이 살고 있다. 오늘부터 인구 이동이 시작된다. 1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두나라가 공유하는 국경선을 하루 동안 연다.2. 위 조건에 맞는 국경선이 모두 열리고, 인구 이동이 시작된다.3. 국경선이 열려 있어 인접한 칸을 이용해 이동할 수 있으면, 그 나라들은 하루 동안 연합을 이룬다.4. 연합을 이루고 있는 각 칸의 인구 수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다.5. 연합을 해체하고, 모든 국경선을 닫는다. 각 나라의 인구 수.. [백준/C++] 1043번: 거짓말 문제https://www.acmicpc.net/problem/1043문제 요약지민이는 각 파티에서 거짓말을 하고 싶어한다. 하지만, 몇몇 사람들은 이미 이야기의 진실을 알고 있다. 따라서, 이런 사람들이 파티에 왔을 경우, 지민이는 진실을 이야기할 수 밖에 없다. 당연히 어떤 사람이 다른 파티에서 진실을 듣고, 또다른 파티에서는 거짓말을 들었을 경우가 없도록 피해야 한다. 거짓말을 할 수 있는 파티 수의 최대를 출력한다.코드#include #include #include using namespace std;// uf[i]: i번 사람의 그룹 번호int uf[55];// t_uf[i]: i번 그룹이 진실을 아는지 여부bool t_uf[55];// 파티 정보 저장vector party[55];// 진실을 알.. [백준/C++] 15686번: 치킨 배달 문제https://www.acmicpc.net/problem/15686문제 요약1 × 1 크기의 칸으로 이루어진 N × N 크기의 도시가 있다. 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 집과 가장 가까운 치킨집 사이의 거리를 "집의 치킨 거리"라고 한다. 모든 집의 치킨거리를 "도시의 치킨 거리"라고 한다. 도시 내 치킨집 중 최대 M개를 고르고 나머지 치킨집은 폐업시켜야할 때,도시의 치킨 거리가 가장 작게 만들어야 한다. 도시의 치킨 거리의 최솟값을 출력한다.코드#include #include #include #include using namespace std;int n, m;int board[55][55];vector> home;vector> chicken;bool open_chicken[20];.. [백준/C++] 1707번: 이분 그래프 문제https://www.acmicpc.net/problem/1707문제 요약이분 그래프란,그래프의 정점의 집합을 둘로 분할하여 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프이다. 그래프가 입력으로 주어질 때, 이분 그래프인지 아닌지 출력한다.코드#include #include #include using namespace std;int k;int main() { // 입출력 시간 단축 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> k; // 테스트 케이스 반복 while (k--) { // 그래프 정보 입력 vector edges[20020]; int v, e; cin >> v >> e; for .. [백준/C++] 11779번: 최소비용 구하기 2 문제https://www.acmicpc.net/problem/11779문제 요약n개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. A번 도시에서 B번 도시까지 드는 최소 버스 비용과 경로를 출력한다.코드#include #include #include #include using namespace std;int n, m;int start_node, end_node;vector> edges[1010];vector res;priority_queue> pq;// dist[i] : 출발 도시에서 i번 도시까지 최소 비용int dist[1010];// route[i]: 최소 경로 상에서 i번 도시의 직전 도시int route[1010];int main() { ios_base::.. [백준/C++] 13325번: 이진 트리 문제https://www.acmicpc.net/problem/13325문제 요약각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 에지들의 가중치를 증가시켜 루트에서 모든 리프까지의 거리가 같도록 하고,에지 가중치들의 총합을 최소화해야 한다.코드???코드 설명그래프의 높이는 0부터 k까지 존재한다.그래프의 노드는 1번부터 2^(k+1) - 1번까지 존재하고, 간선은 총 2^(k+1) - 2개가 존재한다. i / 2번 노드에서 i번으로 이어진 간선의 가중치를 edges[i]에 저장한다. dfs 함수는 재귀적으로 트리를 후위 순회하며 i번 노드에서 리프까지 거리의 최대값을 반환한.. 이전 1 2 3 4 ··· 36 다음