알고리즘/백준

문제 풀이 크루스칼 알고리즘을 이용하였다. 가중치가 작은 순서대로 검사할 수 있도록 간선을 가중치의 오름차순으로 정렬한다. 검사하는 간선이 사이클을 만들지 않다면 간선을 선택한다. 간선이 선택되면 선택된 간선의 노드를 같은 부모로 설정한다. 모든 간선을 검사하거나, 간선이 (총 노드의 수 - 1)만큼 선택되었다면 종료된다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2; int dist; }edge; int parent[10001]; bool compare(const edge edge1, const edge edge2) { return edge1.dist < edge2.dist; } // v의 최상위 부..

문제 풀이 들어온 수를 하나하나 모두 나누면서 접근하면 시간초과이다. 1000000길이의 bool 배열에 입력으로 들어온 인덱스에 해당하는 배열의 값을 true로 세팅한다. 검사할 값의 배수가 입력으로 들어왔는지 확인한다. 배수가 들어왔다면 answer에 현재 검사하는 값에 해당하는 배열의 값을 1증가시키고, 배수의 값은 1 감소시킨다. 코드 #include #include using namespace std; const int MAX = 1000001; bool num[MAX]; int answer[MAX]; vector num_v; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; int maxi = 0; cin >> N; for (int ..

문제 풀이 2중 for문을 돌려서 정답을 찾으면 시간 초과가 발생한다. 두 포인터 알고리즘을 이용한다. 용액의 입력값이 오름차순으로 입력된다. 용액 vector의 양쪽에서 부터 start와 end로 시작하여 검사한다. start가 end의 값을 넘을 때까지 검사하며, start와 end의 합의 절댓값이 현재 answer보다 작다면 갱신한다. start와 end의 합의 부호에 따라 start와 end의 값을 증가하거나 감소시킨다. 코드 #include #include #include using namespace std; int main() { int N; vector v; vector answer; cin >> N; v.resize(N); answer.resize(2); for (int i = 0; i <..

문제 풀이 다각형의 넓이를 구하는 공식으로 대각성분끼리 곱하고 더하면 구할 수 있다. 코드 #include #include #include using namespace std; int main() { int N; long double answer = 0; cin >> N; vector coordinate; coordinate.resize(N); for (int i = 0; i > x >> y; coordinate[i] = make_pair(x, y); } for (int i = 1; i

문제 풀이 위의 식을 구하는 것이 문제의 답이다. 페르마의 소정리에 의해 밑의 식이 성립한다. 즉 b^(-1) (mod X)는 b^(X - 2)이므로, 이 b^(X - 2)만 구하면 답을 구할 수 있다. 문제에서 X가 1,000,000,007의 큰 수 이므로 일반적인 제곱을 하면 범위 초과가 발생하므로 mod연산과 분할 정복을 이용하여 제곱값을 구한다. 코드 #include const int MOD = 1'000'000'007; using namespace std; // a를 b번 곱하고 c로 나눈 값 long long power(long long a, long long b, long long c) { if (b == 0) { return 1; } if (b == 1) { return a % c; } l..

문제 풀이 전체 별이 그려질 공간을 보면 [3100][6200] 정도가 된다. 받은 N값에 따라 별이 그려질 공간을 분할한다. 이 구조의 별을 해당 위치에 그리는 방법으로 해결한다. 코드 #include using namespace std; int N; char ground[3100][6200]; char star[3][6] = { " * ", " * * ", "*****" }; void insertStar(int n, int x, int y) { // 계속 쪼개서 n이 1이라면 별을 입력 if (n == 1) { for (int i = 0; i < 3; ++i) { for (int j = 0; j < 5; ++j) { ground[x + i][y + j] = star[i][j]; } } return; ..

문제 풀이 다익스트라 알고리즘에 경로 추적을 추가한 문제이다. 다익스트라 알고리즘 도중 최단 경로가 갱신되면 노드의 부모 노드를 교체한 방식으로 진행한다. next_node에 최단 경로로 도달하기 위해서는 current_node에서 와야 한다. 코드 #include #include #include #include using namespace std; int n, m; int start_node, end_node; vector graph; int dist[1001][1001]; int parent[1001]; vector path; void dijkstra(int n) { dist[n][n] = 0; parent[n] = n; priority_queue pq; pq.push(make_pair(0, n));..

문제 풀이 종이의 가장자리는 모두 비어있으므로 (0, 0)에서부터 BFS를 시작하여 외부 공기를 모두 방문한다. 방문과 동시에 해당 공기의 상하좌우로 치즈가 있는지 검사하여 치즈마다 공기와 접촉한 횟수를 구한다. 각 치즈를 검사하여 공기와 2번 이상 접촉했다면 해당 치즈를 삭제하고 다시 BFS를 실시한다. 모든 치즈가 녹았다면 BFS를 중지한다. 코드 #include #include #include using namespace std; typedef struct { int x; int y; }type; queue q; int ground[101][101]; int visited[101][101]; int cheese_ground[101][101]; int move_x[4] = { 0, 0, 1, -1 }..

문제 풀이 미세먼지는 동시에 확산 하므로 확산했을 때의 변화값을 의미하는 배열을 하나 더 선언한다. 확산 시, 소스가 되는 미세먼지는 상하좌우로 확산된 수에 비례한다. 공기 청정기에 의한 순환은 for문으로 아래와 위 공기 청정기 각각의 방향에 따라 설정하였다. 코드 #include using namespace std; int room[51][51]; int room_dif[51][51]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int airConUp = -1; int airConDown = -1; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int R, C, T; int ..

문제 풀이 모든 정점에서 모든 정점으로의 최단 거리가 필요하고 정점의 수가 적으므로 플로이드-워셜 알고리즘을 사용한다. 코드 #include #include #include using namespace std; int n, m, r; int graph[101][101]; void floydWarshall() { for (int i = 1; i > m >> r; // 노드 당 아이템 수 입력 for (int i = 0; i > temp; itemNum_node.push_back(temp); } // 그래프 입력 fill(&graph[0][0], &graph[100][100], INT_MAX); while (r--) { int n1, n2; cin >> n1 ..