synodic의 삭망월

그리디 알고리즘 종료시간 기준 정렬 코드 #include #include #include using namespace std; int n, m, a, b, cnt; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; vector v; for(int i = 0; i > a >> b; v.push_back({ b, a }); // 종료시간 기준 정렬 } sort(v.begin(), v.end()); a = 0, cnt = 0; for(int i = 0; i < v.size(); i++) { if(v[i].second < a) continue; a = v[i].first; cnt++; // 최..

string 이나 char 사용법을 경험해봤으면 해서 이 문제를 알고리즘 학습 동아리 문제 셋에 추가해봤다. string은 헤더파일에 존재하므로 추가가 필수이다. 코드 #include #include #include using namespace std; using ll = long long; const int MAX = 1000; int N; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; // string을 쓴다면 사실상 의미 없음 string s; cin >> s; int ans = 0; for (int i = 0; i < s.size(); i++) { ans += s[i] -'0'; } cout

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 이해 이 문제를 이해하기 위해서 종이에 그림을 그려 보라. 단번에 어떤 자료구조가 필요할지 떠오르지 않아도 괜찮다. 앞에서 K번째 원소까지 탐색하고, 원소를 지우고, 탐색하고, 지우고... 를 반복하면 되겠구나! 하고 떠오르면 문제 이해가 끝났다. Queue 이제 큐를 사용해보자 K번째 원소까지 어떻게 셀까? 1. 큐의 맨 앞 원소를 뒤에 붙이고(push), 그 원소를 지운다(pop) 이 과정을 K번동안 반복한다. 그럼 초기에 앞에서 K번째에 있던 원소가 맨 앞으로 왔을 것이다. 2..

dp 사용 코드 #include #include #include #include using namespace std; using ll = long long; int n, sum, arr[100001], dp[100001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; dp[0] = -1000; sum=-1000; for (int i = 0; i > arr[i]; dp[i] = max(arr[i], dp[i - 1] + arr[i]); sum = max(sum, dp[i]); } cout

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 크루스칼 알고리즘 문제 조건 도시가 연결되어 있는 단위를 (도시 한 개만 존재하는 단위도 포함) 도시 묶음이라 하자. 이 도시 묶음 하나 당 발전소는 단 한 개가 존재해야 한다. (MST에서) 두 노드가 같은 트리 안에 존재할 수 없다는 건 두 노드의 부모노드가 같다는 뜻이다. 따라서 발전소의 부모노드를 통일시킨다 (union한다) 발전소 중 하나의 노드..

https://www.acmicpc.net/problem/2180 2180번: 소방서의 고민 첫째 줄에 화재 발생 건수 n이 주어진다. n은 200,000 이하의 양의 정수이다. 둘째 줄부터 n개의 줄에 각각 한 줄에 한 쌍씩 a와 b가 입력된다. a와 b는 40,000 이하의 음이 아닌 정수이다. www.acmicpc.net 문제 이해 문제의 입출력을 보자. 입력 3 2 0 1 2 0 3 출력 5 운이 좋게도 주어진 입력 예시 순서를 따라가면 출력이 나온다. 화재를 진압하는데 걸리는 시간은 at + b이므로 1번째 소방서에서 0초 소비, (2 * 0 + 0) 2번째 소방서에선 2초 소비, (1 * 0 + 2) 3번째 소방서에선 3초 소비 (0 * 2 + 3) 하므로 총 5초(정확히는 단위 시간) 이 소..

https://www.acmicpc.net/problem/2581 다양한 풀이가 있는 것 같아 내 것도 올려본다. 제곱근 소수가 아닌 N의 약수는 무조건 [1,N] 사이에 존재한다. 어떤 자연수 n이 소수인지 알기 위해서 제곱근 n까지만 진행하면 된다. 수가 수를 나누기 위해서 몫이 항상 필요하며 나누는 수와 몫 중 하나는 반드시 제곱근n 이하이기 때문이다. 나누는 수와 몫이 제곱근n을 좌우로 대칭이므로 제곱근값보다 같거나 작은 숫자로 나누어지면 그 이후는 계산을 할 필요가 없다. 때문에 계산이 간략해진다. 코드 #include #include using namespace std; using ll = long long; const int INF = 10001; int ans = 0; bool isPrim..

크루스칼 알고리즘은 모르는 이에게 설명하기도 쉽고 이해하기도 쉽다. unionParent함수에서 일반적으로 부모노드가 더 큰 쪽에 합치지만 일방적으로 첫번째 파라미터인 변수에 union 했다. 코드 // Kruskal Algorithm Using Union & Find #include #include using namespace std; using ll = long long; const int MAX = 1e7; int n,m; int Parent[MAX]; // Parent[node] == parent of node int getParent(int n) { if (Parent[n] == n) return n; else return Parent[n] = getParent(Parent[n]); } void..

#include #include #include #include using namespace std; using ll = long long; const int MAX = 101; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n, c, tot_c = 0; double g, tot_g = 0.0, GPA = 0.0; cin >> n; while (n--) { cin >> c >> g; tot_c += c; tot_g += g * c; } cout

조건 총 n개의 노드의 좌표 정보가 주어진다(double 형) 나는 n개 노드가 서로 전부 이어져있는 간선 정보를 만들어 mst를 탐색해야 할 것이다. 그 개수는 nC2이다. 그만큼 새로운 vector에 push해주면 된다. for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // 다음 노드 double dist = sqrt((v[i].x - v[j].x) * (v[i].x - v[j].x) + (v[i].y - v[j].y) * (v[i].y - v[j].y)); star.push_back(GPS(i, j, dist)); } } 이 구현만 해주면 평범한 mst문제다. 코드 // Kruskal Algorithm Using Union &..