전체 글 (35) 썸네일형 리스트형 BOJ - 행성 터널(2887) 처음에 이 문제를 접했을 때, 사실 왜 gold 1이나 부여되어 있는지 몰랐는데 그대로 제출하니 메모리 초과가 발생하였다. N이 10만개가 들어왔을 경우 내 알고리즘은 현재 N * (N-1)개 만큼의 간선정보를 저장하고 있다. 하지만, 이 문제는 모든 간선에 대한 정보를 알 필요 없이 x축, y축, z축에 대해 인접한 행성만 보면 된다. 그 이유는 백준 질문게시판에 나와있는 아래 내용과 같다. 주어진 그래프의 MST를 T라고 합시다. 인접하지 않은 정점 A, B가 T에서 간선으로 연결되어있다고 가정하죠. 일반성을 잃지 않고 A, B 사이에 연결된 간선 무게가 |A_x - B_x| 라고 하죠. x 축으로 A, B 사이에 있는 정점 C가 존재합니다 (A_x c.z; c.idx = i + 1; v.push_b.. BOJ - 다리 만들기 2(17472) 삼성 SWEA A형 기출문제고, MST에 관련한 문제여서 풀어보았다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 .. BOJ - 네트워크 연결(1922) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include #include #include using namespace std; int N, M, answer; typedef struct graph { int v1; int v2; int cost; } graph; vector v; bool comp(graph a, graph b) { return a.cost N; cin .. 프로그래머스 - 합승 택시 요금(2021 KAKAO BLIND RECRUITMENT) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include #include using namespace std; int cost[201][201]; int INF = 10000000; int solution(int n, int s, int a, int b, vector fares) { int answer = 0; for(int i=1; i 프로그래머스 - 순위 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include using namespace std; bool graph[101][101]; int solution(int n, vector results) { int answer = 0; memset(graph, false, sizeof(graph)); //cstring 헤더 추가 for(int i=0; i BOJ - 거짓말(1043) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 #include #include using namespace std; int N, M; vector party[51]; int getRoot(vector parent, int idx) { if (parent[idx] == idx) return idx; else return.. BOJ - 최소 스패닝 트리(1197) MST를 찾는 알고리즘 중 union-find를 이용하여 O(E*logE)에 찾을 수 있는 Kruskal algorithm을 이용하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 #include #include #include using namespace std; int V, E; typedef struct graph { int v1; int v2; int cost; }gra.. 프로그래머스 - 섬 연결하기 두 Vertex를 잇는 Edge의 cost가 주어졌고, 해당 cost가 최소인 MST를 만드는 것이 문제의 목표이다. MST를 구하는 방법은 여러 개가 있는데, 이 중 Kruskal-algorithm을 사용하여 풀어보도록 하겠다. 크루스칼 알고리즘은 union-find 알고리즘을 이용하여 MST를 구하는 알고리즘으로 잘 알려져 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using namespace std; int getRoot(int idx, .. 이전 1 2 3 4 5 다음
