728x90 Algorithm16 최소 스패닝 트리 / 최소 신장 트리 (MST) 최소 스패닝 트리 / 최소 신장 트리 (MST : Minimum Spanning Tree) by Kruskal Algorithm & Prim Algorithm 정의 최소 스패닝 트리(최소 신장 트리, MST : Minimum Spanning Tree)란, 모든 노드들이 가중치가 있는 무방향 간선에 연결이 되어있을 때, 모든 노드들을 연결하는 방법 중 사이클이 없으면서 가중치의 합이 최소가 되는 트리를 의미한다. 좌측과 같은 그래프가 있다고 할 때, 최소 스패닝 트리은 우측의 빨간 간선들로 이루어진 그래프가 된다. 완성된 최소 스패닝 트리는 모든 노드들이 전부 연결이 되어있으며, 사이클이 존재하지 않는다. 또한 V개의 정점을 가진 그래프라고 할 때, 최소 스패닝 트리는 V - 1 개의 간선을 가진 트리가 .. 2021. 8. 9. 투 포인터 알고리즘 (Two pointer Algorithm) 투 포인터 알고리즘 (Two pointer Algorithm) 개요 위와 같은 Array 에 대해서 array[0] + array[1] + ... + array[k] 의 값이 20이 넘을 때 k의 최소값을 구하라고 한다면, 위 주황색 포인터를 계속해서 1씩 증가시켜 가면서 20이 처음으로 넘는 index를 찾게 될 것 이다. 위의 경우 이 때의 정답은 5이다. 이 경우는 사실 많이 기초적이며 array에 대해서 이해를 하려고 공부를 할 때나 다루는 부분일 것이며 대부분의 사람들이 생각할 수 있을 것 이다. 그렇다면, 위와 같은 Array 에 대해서 부분합인 array[k] + array[k + 1] + ... + array[n] 의 값이 6에 해당이 되는 index가 연속되는 부분집합의 개수를 구하라면 .. 2021. 7. 20. 백준 No.7579 [앱] BOJ No.7579 [앱] Problem 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net Code 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 #include #include #define memory first #define cost second using namespace std; typedef pair PII; int cost_max =.. 2021. 2. 22. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) What is Floyd-Warshall Algorithm? Dijkstra (다익스트라) 알고리즘이 시작하고자 하는 한 vertex에서 나머지 vertex들로 가는 최소 비용을 구하는 알고리즘 이라면, 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로 가는 최소 비용을 2차원 array 혹은 vector 에 저장을 해 둔다. 아래 코드에선 floyd[ i ][ j ]로 표기했고, 이 의미는 vertex i 에서 vertex j 로 가는 최소 비용을 의미한다. floyd[ i ][ j ]의 값을 vertex i, vertex j 를 제외한 모든 vertex 를 경유해보면서 더 작은값을.. 2021. 2. 20. 백준 No.11404 [플로이드] BOJ No.11404 [플로이드] Floyd-Warshall Algorithm Problem 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Code 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 #include #include using namespace std; typedef unsigned long long ull; int V, E; const ul.. 2021. 2. 20. 백준 No.11779 [최소비용 구하기2] BOJ No.11779 [최소비용 구하기2] Problem 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net Code 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 #inc.. 2021. 2. 19. Codeforces Round #703 (div.2) Codeforces Round #703 (div.2) A. Shifting Stacks (solved) Problem Problem - A - Codeforces codeforces.com Code 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 #include #include #include using namespace std; typedef unsigned long long ull; int tc; vector dp(101, 0); vector ans; int main() { ios_base::sync_with_std.. 2021. 2. 19. 백준 No.13913 [숨바꼭질4] Baekjoon Online Judge No.13913 [숨바꼭질4] Problem 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Code 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 #include #.. 2021. 2. 16. 백준 No.13549 [숨바꼭질3] Baekjoon Online Judge No.13549 [숨바꼭질3] Problem 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Code 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 #include #include #include #define pos first #define ti.. 2021. 2. 16. 백준 No.1504 [특정한 최단 경로] Baekjoon Online Judge No.1504 [특정한 최단 경로] Problem 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Code 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 .. 2021. 2. 9. Dijkstra (다익스트라) Dijkstra What is Dijkstra? 그래프의 한 노드에서 다른 노드로 갈 때 드는 가중치들의 합의 최소값을 구하는 알고리즘이다. 이 '가중치'를 문제가 요구하는 바에 따라 거리, 비용 등의 형태로 문제에 다양하게 적용시킬 수 있을 것 같다. Explanation A정점부터 탐색을 시작해봤다. 실제 코드에서 알고리즘을 사용할 땐 처음에 시작하고자 하는 정점을 정해주면 된다. 좌측의 표에서 빨간색은 확정된 최소 비용을 나타낸다. A에서 A로 갈 때에는 당연히 비용이 0이므로 확정이다. 숫자 앞에 A를 붙인 이유는 직전에 A에서 왔다는 의미이다. B, C, D E 열에 차례대로 비용을 적어준다. F열은 A에서 F로 가는 간선이 없으므로 inf 라고 하자. 저렇게 나열해준 뒤 확정이 된 빨간색 칸을.. 2021. 2. 8. 백준 No.12865 [평범한 배낭] Baekjoon Online Judge No.12865 [평범한 배낭] Problem 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Code 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 #define weight first #define value second using nam.. 2021. 2. 6. Codeforces Round #699 (Div.2) A, B Codeforces Round #699 (Div.2) A. Space Navigation Problem Problem - A - Codeforces codeforces.com Code 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 #include #include #include using namespace std; int tc; vector ans; int main.. 2021. 2. 6. BOJ No.2798 [블랙잭] Baekjoon Online Judge No.2798 [블랙잭] Code 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 #include #include using namespace std; int N, M; vector cards; int main() { cin >> N >> M; cards.resize(N); for (int i = 0; i > cards[i]; int answer = 0; for (int i = 0; i 2021. 2. 5. lower_bound, upper_bound lower_bound & upper_bound std::lower_bound - cppreference.com std::upper_bound - cppreference.com Definition lower_bound : 찾고자 하는 값 이상의 수가 처음으로 나오는 곳의 index를 구할때 사용 upper_bound : 찾고자 하는 값보다 큰 수가 처음으로 나오는 곳의 index를 구할때 사용 How to use Binary search를 기반으로 탐색되므로, 탐색되는 vector 혹은 list 는 sort 되어있어야 한다. lower_bound, upper_bound는 구하고자 하는 곳의 iterator를 return 한다. 따라서 실제로 사용할 경우 구한 lower_bound 혹은 upper_bound.. 2021. 2. 4. 이전 1 2 다음 728x90
