본문 바로가기

BOJ67

[BOJ] 백준 1007번: 벡터 매칭 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net N개의 좌표점이 주어지고 (N은 짝수) N/2개의 벡터를 만들 때, 모든 벡터의 합이 최소가 되는 크기를 구하는 문제입니다. 20개의 벡터 쌍을 구하는 경우의 수는 20C2 + 18C2 +...+ 4C2 + 2C2 이므로 20! / 2^10 으로 다른 방법을 찾아봐야겠습니다. 2,432,902,008,176,640,000 / 1024 = 2,375,880,867,360,000 위의 벡터의.. 2020. 8. 11.
[BOJ] 백준 1004번: 어린 왕자 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주�� www.acmicpc.net 점과 원사이 관계로 푸는 문제. 출발 지점과 도착 지점이 주어진 원에 대하여 두 점이 모두 원 안쪽에 속하는지, 둘다 속하지 않은 경우 해당 원을 진입하거나 이탈 할 필요가 없습니다. 어느 한 지점만 속한 경우 반드시 진입 또는 이탈을 해야하므로 이 경우에만 1 증가 시켜주면 됩니다. #include #include using namespace std; typedef long l.. 2020. 8. 11.
[BOJ] 백준 1002번: 터렛 https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 중심과 반지름이 주어질 때, 두 원의 교점의 개수를 구하는 문제입니다. 소수점 연산의 오차를 줄이기 위하여 두 점사이 거리의 제곱을 활용합니다. 두 원의 중심 간의 거리 dist = (x1-x2)^2 + (y1-y2)^2 두 반지름의 합 sumr = (r1 + r2) * (r1 + r2) 두 원의 반지름 중 큰 것 r1, 작은것 r2 (같으면 순서 상관 없음) 1. 동심원의 경우 if (!dist) { // 동심원 cout > y1 >> r.. 2020. 8. 11.
유니온 파인드 (Union Find) 혹은 분리 집합 (Disjoint Set) 유니온 파인드 알고리즘은 같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 다양한 문제들에서 많이 사용됩니다. 특정 노드는 자신의 부모를 의미하는 P[node] 배열값을 갖습니다. 즉 P[node] = node 인 경우 자기 자신을 부모로 한다는 의미이며, P[node] != node 인경우 다른 노드 번호를 부모로 한다는 뜻입니다. 그럼 대체 이걸 어디에 사용할 수 있을까요? 예를 들어 1번 노드와 3번 노드가 연결되어 있고, 2번 노드와 3번 노드가 연결되어 있다면 1번과 3번이 연결되어있는 것을 알 수 있습니다. 여기서 연결된 노드간 같은 부모를 갖는다고 정의한다면 P[1] = P[2] = P[3] 이며 1 또는 2 또는 3의 값을 가집니다. 편의상 부모 노드의 번호가 작은쪽으로.. 2020. 8. 9.

티스토리툴바