정화 코딩

https://www.acmicpc.net/problem/12850 어떤 인접 행렬이 "1분만에 이동할 수 있는 경로"라고 하면, 인접 행렬의 d 거듭제곱은 "d분만에 이동할 수 있는 경로"이다.이 사실만 알면 문제를 쉽게 풀 수 있다. (선형대수학에서 배운다고들 하는데 나는 왜 기억이 안 나지)단순 d 제곱을 하면 시간초과가 나므로 분할 정복을 이용한 거듭제곱을 사용해주어야 한다. #include #include using namespace std;int MOD = 1000000007;vector> e;vector> mul(vector> a, vector> b) { vector> c(8, vector(8, 0)); for (int i = 0; i > pow(vector> a, int x) {..

https://www.acmicpc.net/problem/2568 딱 전깃줄 문제와 가장 긴 증가하는 부분 수열 5 문제를 합친 문제이다. 전깃줄 문제 풀이: https://jungh150c.tistory.com/110가장 긴 증가하는 부분 수열 5 문제 풀이: https://jungh150c.tistory.com/109 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> a(n + 1); a[0].first = a[1].first = 0; for (int i = 1..

https://www.acmicpc.net/problem/2887 #include #include #include using namespace std;int n;vector> a;vector> e;vector parent;int find(int a) { if (parent[a] == a) return a; else return parent[a] = find(parent[a]);}bool unite(int a, int b) { a = find(a); b = find(b); if (a != b) { parent[a] = b; return true; } else { return false; }}int main() { ios_bas..

https://www.acmicpc.net/problem/1509 dp 배열 2개를 사용해서 풀었다.1. 모든 구간에 대해서 팰린드롬인지 아닌지를 저장하는 배열p[i][j] : i부터 j까지의 문자열이 팰린드롬이면 true, 아니면 false이 배열을 채울 때는 구간의 길이가 1일 때, 2일 때, ... 순서로 채워준다. 어떤 구간이 팰린드롬이고 직전 문자와 직후 문자가 같으면 그 구간도 팰린드롬임을 활용해서 채우면 된다.2. 팰린드롬 분할 개수의 최솟값을 저장하는 배열 (정답을 구하는 배열)dp[i] : i까지의 문자열의 팰린드롬 분할 개수의 최솟값이 배열은 0부터 j까지의 팰린드롬 분할 개수의 최솟값, 즉 dp[j]가 x이고 j+1부터 i까지의 문자열이 팰린드롬이면 dp[i]를 x + 1로 갱신할 수..

https://www.acmicpc.net/problem/16566 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, k; cin >> n >> m >> k; set blue; for (int i = 0; i > x; blue.insert(x); } for (int i = 0; i > x; auto it = blue.upper_bound(x); cout (TLE)단순히 수들을 set에 넣어두고 upper_bound로 수를 찾고 지워주고...를 반복하면 시간 초과를 ..

https://www.acmicpc.net/problem/1106 Knapsack 문제 중에서도 Unbounded Knapsack 문제이다.Unbounded Knapsack 문제는 Knapsack 문제 중 아이템을 무한히 선택 가능한 상황이다. 사실 Unbounded Knapsack 문제는 처음이라서, 나는 처음에 아이템을 복사해주고 일반적인 Knapsack처럼 하면 되는 줄 알았다. (찾아보니 이건 아이템을 정해진 횟수만큼만 선택할 수 있는 Bounded Knapsack 문제에서 사용할 수 있는 방법인 것 같다.)첫 번째 풀이: 홍보 도시를 중복으로 사용할 수 있도록 복제 + 2차원 dp 배열을 사용해서 냅색#include #include using namespace std;int MAX_COST = ..

https://www.acmicpc.net/problem/17370 각 이동은 위와 같이 벡터로 표현할 수 있다. 실수 좌표계에서 방문 처리를 하는 법은 여러 방법이 있을 수 있겠지만 나는 두가지 방법으로 구현해보았다. 1. 실수 좌표를 그대로 사용, 대신 오차 범위를 두고 비교벡터는 동일하게 (1, 0) (0.5, sqrt(3)/2), (-0.5, sqrt(3)/2), ... 이런 식으로 계산한다. 다만 소수점 둘째자리 정도까지 반올림해주었다. 그래야 계산 상의 차이로 아주 작은 오차가 생겼을 때 같은 점으로 인식할 수 있다. 나는 실수를 scale 후에 반올림을 해서 정수로 만들고, pair을 원소로 하는 set으로 방문 처리를 해주었다. #include #include #include #inclu..

https://www.acmicpc.net/problem/28297 모든 기어 쌍에 대해서 벨트의 길이의 구하고 (총 n*n번) 그 길이들을 가지고 최소 스패닝 트리를 만들면 된다. 하나의 기어 쌍에 대한 벨트의 길이를 구하는 과정은 다음과 같다. 두 중심 사이의 거리를 빗변(h)으로 하고 두 반지름의 차이를 높이(a)로 하는 삼각형을 생각해보자. 피타고라스 정리에 의해 밑변(b)도 구할 수 있고 arcsin을 통해 α도 구할 수 있다. α를 활용하여 두 호의 길이도 구할 수 있다.벨트의 길이는 밑변 * 2 + 왼쪽 원의 호 + 오른쪽 원의 호 이다. 주의할 점은!!! (PI + 2α)는 항상 더 큰 반지름과 곱해져야 하고 (PI - 2α)는 항상 더 작은 반지름과 곱해져야 한다는 것이다. 이것 때문에 ..