728x90 🥇Baekjoon Solutions73 [C++] 백준 1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리(크루스칼 알고리즘)의 가장 기본적인 문제입니다. 유니온-파인 개념을 사용하여 사이클이 발생하지 않는 방향으로 모든 연결 간선들을 분석해 줍니다. #include #include #include using namespace std; class edge { public: int node[2]; int distance; edge(in.. 2021. 8. 19. [C++] 백준 1181번: 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 알고리즘 라이브러리에 있는 sort함수를 사용하여 해결합니다. sort함수의 특이 형태인 비교 인자 구분 함수를 사용하여 특별 케이스 정렬을 진행합니다. #include #include #include using namespace std; bool compare(string a, string b) { if (a.size() == b.size()) return a < b;// 문자열.. 2021. 8. 19. [C++] 최소 스패닝 트리(크루스칼 알고리즘) 최소 스패닝 트리란? 트리는 N개의 정점이 N-1개의 간선으로 연결되어 있으면서 어느 두 노드를 잡아도 가지 못하는 경로가 존재하지 않습니다. 일반적으로 트리를 만들 때, 가중치를 고려하지 않고 트리를 구성합니다. 간선에 가중치가 존재하기 때문에 최소 스패닝 트리가 있는 것입니다. 최소 스패닝 트리는 간선을 N-1개의 간선을 뽑아내서 트리를 구성하면서, 뽑아낸 간선의 총 합이 제일 작아야합니다. 최소 스패닝 트리의 주요 포인트 1) 우선 N개의 정점이 트리가 되어야한다. 2) 뽑은 간선의 총합이 제일 작아야한다. 구현 1) 트리를 구성하기 위해서는 union-find 알고리즘의 union을 써서 쉽게 구현이 가능합니다. 2) 다음 뽑은 간선의 총합을 제일 작게 해기 위해서는 우선 간선을 오름차순 .. 2021. 8. 8. [C++] 백준 11659번: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 최초풀이 DP알고리즘을 활용하여 풀이를 진행하였고 빠른 출력 처리를 해주어야 합니다. #include using namespace std; int dp[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M, k; cin >> N >> M; for (int i.. 2021. 8. 1. [C++] 백준 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 최초풀이 시간초과 에러가 많이 발생하는 문제입니다. DP 알고리즘을 잘활용하고 빠른 입출력 처리도 해주어야 합니다. #include using namespace std; int dp[1025][1025]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N,.. 2021. 8. 1. [C++] 백준 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 최초풀이 위에서부터 아래로 규칙에 따라 최대 값을 갱신해가는 배열을 만듭니다. 가장 아래 단계까지 구했다면 그 단계의 최대 값을 출력해 줍니다. #include using namespace std; int dp[501][501]; int main() { int n, temp; cin >> n; for (int i = 1; i > temp; if (j == 0) dp[i][j] = temp + dp[i - 1][j]; else if (j == i - 1) dp[i][j].. 2021. 8. 1. [C++] 백준 11050번: 이항 계수 1 https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 최초풀이 #include using namespace std; int main() { int N, K, ans = 1; cin >> N >> K; for (int i = N; i > N - K; i--) ans *= i; for (int i = 1; i 2021. 7. 31. [C++] 백준 1644번: 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 최초풀이 1-4,000,000까지 소수 확보 연속된 소수들의 합을 배열 인덱스로 확인하며 누적 #include #include using namespace std; int check[4000001]; bool Not_prime[4000001]; int main() { int N; vectorprime; //소수가 아닌수 체크(에라토스테네스의 체) for (int i = 2; i N; cout 2021. 7. 31. [C++] 백준 2725번: 보이는 점의 개수 https://www.acmicpc.net/problem/2725 최초풀이 시간초과 에러가 처음 발생하였습니다. 그래서 미리 모든 수를 구해 놓고 결과 값을 구하는 방식을 사용하였습니다. #include #include using namespace std; int gcd(int a, int b) {// 최대공약수 구하기(재귀, 유클리드 호제법) if (b == 0) return a; else return gcd(b, a % b); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int C; vectorv; cin >> C; v.push_back(0); int ans = 0; for (int i = 1; i > N; cout 2021. 7. 31. 이전 1 ··· 3 4 5 6 7 8 9 다음 728x90
