본문 바로가기

분류 전체보기105

[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.
[BOJ] 백준 1956번: 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 u를 완전탐색 O(n^3)로 구할 수 있습니다. 초기값을 입력 경로로 넣어주고 나머지는 꽤 큰값 (1e9)로 초기화한 뒤 3중 포문으로 구해 나가는 코드입니다. #include #include #include #include #include #include #include #include using namespace std; int n, m; int buf[401][401]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i a .. 2020. 8. 9.

티스토리툴바