정화 코딩

https://www.acmicpc.net/problem/28707 나는 두가지 방법으로 풀었는데, 공통적으로 필요한 아이디어는 각 배열의 상태를 정점으로 생각하고 하나의 swap 연산을 가중치가 있는 간선으로 생각하는 것이다. 그리고 방문했는지 여부와 걸린 시간은 vector 배열을 key로 하고 걸린 시간 int를 value로 하는 map으로 처리한다. 첫번째는 BFS를 사용한 풀이이다.단순히 방문할 때마다 비내림차순 상태가 맞는지 확인 후 ans를 갱신하고, 다음 상태들을 쭉 보면서 방문한 적 없거나 시간이 덜 걸린 경우에만 큐에 넣어주면서 탐색했다. #include #include #include #include using namespace std;int n, m;vector a;vector c..

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α)는 항상 더 작은 반지름과 곱해져야 한다는 것이다. 이것 때문에 ..

https://www.acmicpc.net/problem/28296 다음과 같은 순서로 생각하면 이해가 그나마 좀 쉬운 것 같다. 일단 두 창고를 연결하는 경로상의 도로 중 가장 작은 가중치가 그 경로의 상한선이 되고, 두 창고를 연결하는 여러 경로가 있을 때 상한선이 가장 큰 경로를 택한다.즉, 두 창고를 연결하는 경로가 여러 개 있을 때, 가중치가 작은 도로가 포함되지 않도록 하는 것이 최적이다. 이를 통해 가중치가 작은 간선들은 필요없고 최대 스패닝 트리를 그렸을 때 거기에 포함된 도로들만 사용하면 된다는 것을 알 수 있다. 최대 스패닝 트리를 그려야 하므로 가중치가 큰 도로부터 보면 된다. 가중치가 큰 도로부터 보면 현재 보고 있는 도로가 지금까지 봐온 도로 중 가중치가 가장 작은 도로라는 것이..

https://www.acmicpc.net/problem/1005 게임 개발과 완전 비슷한 문제이다.이 문제에 대한 설명과 풀이는 이 글에 있다. #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n, k, w; cin >> n >> k; vector> g(n + 1); vector time(n + 1); vector totaltime(n + 1); vector indegree(n +..

https://www.acmicpc.net/problem/9466 이 문제는 사이클을 판단하는 문제이다. 사이클이 있는지 없는지를 판단하기 위해서 chk 배열과 v 변수를 두었다.v 변수는 현재가 몇번째 연결 그래프인지를 저장하는 변수이고, chk 배열은 해당 노드를 방문 했는지 여부와 몇번째 연결 그래프에서 방문했는지를 저장하는 배열이다. 해당 연결 그래프에서 사이클이 존재하는지를 판단했다면 이제 어느 노드부터 어느 노드까지가 사이클인지 알아야 한다.이를 위해서 지나온 경로를 기록한 후 사이클의 기준점까지 역주척하면서 체크하면 되는데, 두 가지 방법이 있다. 하나는 재귀 함수의 콜 스택을 사용하는 방법이고, 다른 하나는 명시적 스택(stack 자료구조)을 사용하는 방법이다. 1. 재귀 함수 콜 스..

https://www.acmicpc.net/problem/17070 그냥 bfs 해주되, 파이프가 놓여 있는 방향까지 큐에 넣도록 했다. 그래서 현 상태를 기준으로 어떻게 움직일 수 있는지를 체크해서 (n, n)에 도달하면 한번 카운트 해주는 식으로 구혔했다.어차피 움직이는 방향이 무조건 오른쪽 또는 아래이기 때문에 시간 안에 해결 가능하다고 생각했는데, 제출해보니 좀 간당간당하고 dp로 풀어야 했던 문제인 듯하다. #include #include #include using namespace std;// 파이프가 놓여 있는 방향 {가로, 세로, 대각선}int px[] = {0, -1, -1};int py[] = {-1, 0, -1};vector>> d = { {{0, 1, 0}, {1, 1, 2}..

https://www.acmicpc.net/problem/14938 우선 모든 노드와 노드 사이의 최단 경로를 구해 놓는다.그 후 각 지역에 떨어졌다고 가정했을 때, 얻을 수 있는 아이템의 수를 구해서 최댓값을 찾는다. 모든 노드 간의 최단 경로가 필요하기 때문에 플로이드-워셜을 사용하였다. #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, r; cin >> n >> m >> r; vector item(n + 1); for (int i = 1; i > item[i];..