어쨌든 공부하는 블로그

[C++][백준 11724] 연결 요소의 개수 (DFS, BFS)

https://www.acmicpc.net/problem/11724제출 코드(DFS)#include #include using namespace std;vector vec[1001]; // 연결된 정점들을 vector에 저장bool visit[1001]; // 방문 여부 체크용void dfs(int node){ visit[node] = true; // 연결된 노드들을 체크 for (int i = 0; i > n >> m; while(m--) { int u, v; cin >> u >> v; // 방향 없는 그래프이기 때문에 u와 v 양쪽에 push vec[u].push_back(v); vec[v].push_back(..

[C++][백준 11660] 구간 합 구하기 5

https://www.acmicpc.net/problem/11660 풀이1우선 누적합을 이용해 2차원 배열에 값을 채워넣는다(배열의 (i, j)에는 (0, 0)부터 (i, j)번째까지의 모든 값이 담긴다. 즉, (i + 1, 0) 위치에는 (i, n)까지의 합에 (i + 1, 0) 번째 수가 더해진 값이 들어가게 된다)답은 각 행의 x2의 누적합 - x1의 누적합을 행의 갯수만큼 반복하여 더해주면 된다위 배열이 주어졌다고 가정했을 때, 누적합을 이용해 배열을 채우면 아래와 같다제출 코드#include using namespace std;int ps[1025][1025];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ..

https://www.acmicpc.net/problem/14929 풀이출력값은 x1 * x2 + x1 * x3 + ... x1 * xn + x2 * x3 + x2 * x4 + ...x2 * xn ... x(n-1) * xn 이므로정리해서 x1(x2 + x3 + ... xn) + x2(x3 + x4 + ... xn) 와 같이 표현할 수 있다이때 xi부터 xn까지 하나하나 더하는 과정을 n번 반복하면 시간초과가 되기 때문에 누적합을 이용한다 제출 코드#include using namespace std;int arr[100001];int ps[100001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; ..

https://www.acmicpc.net/problem/3474 풀이오른쪽 끝에 나오는 0의 개수는 10이 얼마나 곱해졌는가를 구하면 된다그렇다면 10이 얼마나 곱해졌는가는 2와 5가 몇 개 곱해졌는가를 구하면 된다이때 2가 곱해진 횟수와 5가 곱해진 횟수 중 더 작은 횟수가 10이 곱해진 횟수라고 보면 되는데, 2는 모든 짝수가 해당되므로 팩토리얼 연산에서는 무조건 5가 곱해진 횟수보다 많다 따라서 5가 곱해진 횟수를 세면 되는데, N!을 계산하기 위해 1부터 N까지 루프문을 돌며 5가 등장하는 횟수를 세면 시간초과가 된다(N의 최댓값이 10억이기 때문) N이 125라면, 1부터 125까지를 곱해주어야 한다. 1부터 125까지의 수 중에 5의 배수가 등장하는 횟수는 125를 5로 나누어 쉽게 구할 수..

우선 두 수의 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눠주면 구할 수 있다따라서 최대공약수(GCD)를 구하는 것이 중요하다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다... 1. 재귀함수로 구현int gcd(int a, int b){ if (a % b == 0) return b; return gcd(b, a % b);} 2. 반복문으로 구현int gcd(int a, int b){ int r = a % b; while(r) ..

https://www.acmicpc.net/problem/21920풀이1x의 소인수를 저장해두고, 입력된 수들을 x의 소인수들로 나눠서 서로소인지 여부를 확인한다 제출 코드#include #include using namespace std;int arr[500001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, x; cin >> n; for (int i = 0; i > arr[i]; cin >> x; vector v; // x의 소인수 구하기 for (int i = 2; i  풀이2서로소라는 것은 두 수의 최대공약수가 1인 수라는 의미이다이를 그대로 해석하여 gcd ..

https://www.acmicpc.net/problem/5347풀이최소공배수(LCM)와 최대공약수(GCD)를 유클리드 호제법을 이용해 푸는 문제다 두 수의 최소 공배수는 두 수의 곱을 최대 공약수로 나누면 구할 수 있다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다...  제출 코드#include using namespace std;long long gcd(long long a, long long b){ if (a % b == 0) return b; ..

힙으로 구현된 큐로, 기본적으로 내림차순으로 정렬된다(top이 가장 큰 값) #include #include using namespace std;int main(){ // 내림차순 정렬 priority_queue q; // or priority_queue, less> q2; // 오름차순 정렬 priority_queue, greater> q; q.top() // 가장 위에 위치한 값을 리턴 q.pop() // 가장 위에 위치한 값을 삭제 q.empty() // 큐가 비있는지를 리턴(bool) q.push(a) // 큐에 원소를 푸시} #include #include using namespace std;struct comp{ bool..

https://www.acmicpc.net/problem/1991풀이일반적인 방법으로 포인터를 이용한 구조체로 이진 트리를 구현할 수도 있지만C++에서 map을 이용해 트리를 구현하는 더 간단한 방법도 있다 제출 코드#include #include using namespace std;map> tree;void preorder(char node){ cout > n; char node; while(n--) { cin >> node; cin >> tree[node].first >> tree[node].second; } preorder('A'); cout

https://www.acmicpc.net/problem/2304 풀이각 높이별로 가장 왼쪽에 있는 기둥과 가장 오른쪽에 있는 기둥을 구해서 그 사이 면적을 계속 더해주는 식으로 코드를 작성하였다   제출 코드#include #include using namespace std;pair arr[1001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i > arr[i].first >> arr[i].second; sort(arr, arr + n); int sum = 0; for (int i = 1; i = i) ..