oVeron

https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 두 점 (x1, y1), (x2, y2)가 있다고 할 때, 벡터는 (x1, y1) - (x2, y2)이다. 점이 N개 있을 때 벡터의 합은, 벡터를 N/2개 더하면 되므로 ((xa, ya) - (xb, yb)) + ((xc, yc) - (xd, yd)) + ... 이다. 이는 {(xa, ya) + (xc, yc) + ... } - {(xb, yb) + (xd, yd) ...} 이다. 즉 ..

알고리즘/baekjoon 2023. 2. 1. 22:57

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 비어있는 칸을 어떻게 하나로 연결할 것인지가 중요했던 문제이다. 이때 본인은 유니온 파인드를 썼지만 그냥 구현해서 풀어도 큰 상관은 없다. 구현력을 시험했던 문제. #include #include #include #include #include #include #include #include #include using namespace std; typedef long long..

알고리즘/baekjoon 2023. 1. 30. 23:10

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net gi가 입력될 때, gi보다 작되 가장 큰 공항을 골라야 최대한 많은 비행기를 도킹시킬 수 있다. 하지만 평범하게 이를 구현하면 시간초과가 나므로, 유니온 파인드를 이용해 gi보다 작되 가장 큰 공항을 부모로써 가지게 설계하면 된다. #include #include #include #include #include #include #include #include #..

알고리즘/baekjoon 2023. 1. 30. 19:48

https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; ll A, B; ll ans{ 0 }; int main() { ios::sync_with_stdio(fa..

알고리즘/baekjoon 2023. 1. 30. 18:55

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net dp[k][i][j] : k번째 지시사항에서 왼발은 i, 오른발은 j에 위치해 있다. 점화식을 구해보자. k+1번째 지시로 이동할 곳이 x라 할 때 dp[k][i][j] = min( dp[k+1][x][j], dp[k+1][i][x] )이다. 즉 왼발이 x로 이동할 때, 오른발이 x로 이동할 때로 나누어서, 이동할 때의 비용을 반영해 그 최솟값을 구하면 된다. #..

알고리즘/baekjoon 2023. 1. 30. 10:48

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net dp[i][j] : 1번 경찰차가 i번 사건, 2번 경찰차가 j번 사건에 출동했을 때 최단 거리 점화식을 구해보자. dp[5][8]일 때를 생각해보자. 즉 1번 경찰차가 5번 사건, 2번 경찰차가 8번 사건에 출동했을 때이다. 그렇다면 이전 사건인 7번 사건에 출동한 경찰차는 2번 경찰차가 된다. 7번 사건에 1번 경찰차가 출동했다면 1번 경찰차는 현재 5번 사건이 일어난 ..

알고리즘/baekjoon 2023. 1. 26. 12:27

https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net #include #include #include #include #include #include #include #include #include #define inf 1e9 using namespace std; int N; int D[20][20]; int dp[20][1048576]; typedef long long ll; typedef pair pii; int solve(int ..

알고리즘/baekjoon 2023. 1. 25. 19:38

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #define inf 1e9 using namespace std; typedef long long ll; typedef pair pii; int N; int W[16][16]; int dp[65536]..

알고리즘/baekjoon 2023. 1. 25. 18:39