본문 바로가기
반응형

전체 글1308

[SWEA] 4006 고속도로 건설 2 출처: [SWEA] SW 문제해결 심화 - 그래프 Input 1 5 8 1 2 4 1 3 9 1 4 21 2 3 8 2 4 17 3 4 16 5 2 20 5 4 30 Output #1 48 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소 신장 트리(MST, Minimum Spanning Tree) ; 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프. ※ 신장 트리(Spanning Tree); 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결. zoosso.tistory.com 최소 신장 트리를 구현하는 알고리즘은 크루스칼과 프림 알고리즘이 존재하는데 해당 문제는 크루스칼 알고리즘 이용. i.. 2021. 2. 27.
[BOJ] 백준 10775 공항 출처: https://www.acmicpc.net/problem/10775 Input 4 6 2 2 3 3 4 4 Output 3 비행기가 연결(docking)하기 위해 주먹구구 방식으로 비어있는지 게이트를 찾고자한다면, 비행기와 게이트의 개수가 각각 1 ≤ N, M ≤ 105이므로 TLE(Time Limit Exceeded) 발생 ※ Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com 구현 Un.. 2021. 2. 27.
[BOJ] 백준 1976 여행 가자 출처: https://www.acmicpc.net/problem/1976 Input 3 3 0 1 0 1 0 1 0 1 0 1 2 3 Output YES ※ Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com 무방향 그래프로 Aij = Aji이므로 i > j 인 경우만 union 연산 Union-Find 구현 후, 주어진 정점들이 가리키는 부모노드가 모두 같은지 확인 import java.io.B.. 2021. 2. 27.
[BOJ] 백준 1717 집합의 표현 출처: https://www.acmicpc.net/problem/1717 Input 7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1 Output NO NO YES ▶ 0 a b → union ▶ 1 a b → find ※ Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com 시뮬레이션 ▶union(1, 3) → find(1, 7) ▶ union(7, 6).. 2021. 2. 27.
최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소 신장 트리(MST, Minimum Spanning Tree) 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프. ※ 신장 트리(Spanning Tree) 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결되어 있는 그래프. ▶ 간선의 개수 = 정점의 개수 - 1 ex) 정점의 개수 |V| = 6 / 간선의 개수 |E| = 5 5 = 6 -1 ▶ 크루스칼 알고리즘Kruskal's Algorithm 혹은 프림 알고리즘Prim's Algorithm을 통해 구현가능 시간복잡도: 둘다 동일하게 O(ElogV)로 구현 가능 Kruskal's Algorithm ; 가중치가 낮은 간선으로 정점을 이어가면 모든 정점을 방문하는 방식 ① 비용이 낮은 간선 선택 ← 우선순위 큐 ② 선택된.. 2021. 2. 27.
Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 노드가 서로 같은 그래프에 속하는지 판단하는 그래프 알고리즘. 이름 그대로 union 연산과 find 연산이 존재 ▶ union(a, b) : a와 b가 포함되어 있는 집합을 합치는 연산 ▶ find(x) : x가 어떤 집합에 포함되어 있는지 찾는 연산 시뮬레이션 ▶ 모든 노드(정점)은 자기 자신을 가리키는 상태. ▶ 정점 [1] - [2] 연결 / 정점 [3] - [4] 연결 → union(1, 2) / union(3, 4) 일반적으로 두 노드 중 낮은 번호 정점으로 .. 2021. 2. 27.
[Jungol] 정올 1336 소수와 함께 하는 여행 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=615&sca=30 Input 1033 8179 Output 6 출발점으로 부터 숫자 자릿수 차이가 한 개가 발생하는 숫자들을 탐색해 갑니다. 이때, 자릿수 차이와 함께 소수여야 하므로 1000 ~ 9999까지의 수 중 에라토스테네스의 체를 이용해서 미리 소수를 구합니다. ※ 코드에서는 prime[i] = 1인 경우, 숫자 i는 소수가 아닙니다. 두 수의 자릿수 일치 정도 확인 #define _CRT_SECURE_NO_WARNINGS #include const int LM = 10000; struct Bus { int num, time; } que[LM]; int start, end; int .. 2021. 2. 26.
[Jungol] 정올 1078 저글링 방사능 오염 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=3040 Input 7 8 0010000 0011000 0001100 1011111 1111011 0011100 0011100 0001000 3 5 Output 9 0 입력받을 때, 저글링 표시를 『-1』로 해서 저장합니다. scanf("%1d", &map[i][j]);로 공백없는 숫자를 한 자리씩 받을 수 있습니다. 또한, BFS 탐색할 때, 저글링이 방사능이 걸려 죽는시간이 3초를 시작시간으로 합니다. ※ Input Data는 열의 크기, 행의 크기 순이므로 주의 #define _CRT_SECURE_NO_WARNINGS #include struct zergling { int x, y.. 2021. 2. 26.
[Jungol] 정올 1661 미로 탈출 로봇 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=50 Input 8 7 1 2 7 5 11111111 00000111 10110011 10111001 10111101 10000001 11111111 Output 9 ※ 주어지는 Input Data가 열의 크기, 행의 크기 순으로 주어지므로 2차원 배열을 구성할 때 주의. ※ map[][] 크기는 100 × 100이므로 Queue에 최대 담기는 개수는 10000개 입니다. ※ scanf("%1d", &map[i][j]);를 통해 공백없이 연속해서 받는 숫자를 한 자리씩 처리할 수 있습니다. #define _CRT_SECURE_NO_WARNINGS #include #define I.. 2021. 2. 26.
[Jungol] 정올 1006 로봇 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=285 Input 5 6 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 4 2 3 2 4 1 Output 9 ※ 방문 확인: visited[101][101][5] → visited[x][y][1~4]: (x, y) 지점을 1~4번 방향으로 방문표시 ① 로봇은 현재 바라보고 있는 방향에서 1~3칸 전진할 수 있습니다. 1~3칸으로 이동가능한지 확인할 때, 범위를 벗어나거나 중간에 장애물이 벗어나는 경우 break 합니다. ex) 1칸 전진했을 때, 장애물을 만난다면 로봇은 2, 3칸 이상 전진도 불가능합니다. 하지만 1칸 전진한 곳이 .. 2021. 2. 26.
반응형

티스토리툴바