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 &..

문제 이해 틈과 불일치의 페널티를 문제 조건으로 주고 최적 정렬의 총 손해를 알아내는 DNA 서열 정렬 알고리즘을 본 적 있는가? 이 문제는 그 페널티가 각 케이스마다 다르게 2차원 배열로 주어졌다. 최적 정렬을 구하는 계산은 다음 중 하나로 시작한다. 두 배열 X, Y에서 X[0]은 Y[0]과 정렬한다. X[0]은 틈과 정렬한다. Y[0]은 틈과 정렬한다. 이 표는 주어진 조건이라 나는 const 2차원 배열로 저장했다. 다이나믹 프로그래밍- 점화식 최적 정렬의 손해를 저장하는 2차원 배열 opt를 채우는 점화식을 세우자. opt[i-1][j-1] + score[ Xseq[i-1]][ Yseq[j-1] ]; opt[i-1][j] + score[ Xseq[i-1] ][4]; opt[i][j-1] + sc..

구글링 해서 풀었다면? 그래프 이론을 공부한 뒤에도 이 문제의 해답이 떠오르지 않는다면, 이 문제의 풀이를 암기하고, 비슷한 응용 문제를 풀어보는 게 효율적인 학습법일 것 같다. https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 코드 #include #include #include #include using namespace std; using ll = long long; const int MAX = 52; int map[MAX][MAX];..

이전 블로그는 https://velog.io/@synodical synodical (Yeeun Lee) - velog Invalid operands to binary expression('const' and 'const') 에러 const keyword 붙이기백준에서 크루스칼 알고리즘을 풀던 중,노드의 정보 중 간선의 가중치를 클래스 내 연산자 오버로딩으로 정렬하기 위해를 작 velog.io 누가 내 코드 복붙으로 백준에 제출한 거 보고 벨로그에 회의감이 들어 수익도 안나는데 티스토리에 옮겨야지 미루다가 이제 옮겼다 일상 적는 사람은 벨로그보다 티스토리에 많은 것 같아 그 점도 가산점으로 쳤다.

https://www.acmicpc.net/problem/21316 문제 이해 조건에 따르면 7번 별이 스피카이다. 12줄에 걸쳐 그래프(별자리) 정점(별)과 간선 정보가 주어진다. 문제의 입력에서 반드시 그림과 같은 모습임이 보장된다. 고 했으므로 주어지는 그래프는 모두 동형이다. 따라서 매 테스트케이스 마다 12줄에 걸쳐 동일한 그래프의 정점과 간선 정보가 주어지지만, 서로 다른 두 개의 정수 x, y 또한 바뀔 것이다. 그러므로 우리는 매번 바뀌는 테스트 케이스에서, (조건의) 저 7번 자리에 위치하는 별의 번호를 출력해야한다. 그렇다면 어떤 별이 (조건의) 7번 자리인 것을 어떻게 알아낼까? 인접한 정점의 차수 7번과 인접한 정점들을 보자. 7번의 차수는 3이고, 인접한 정점은 3, 6, 8번 별..