본문 바로가기

백준61

[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.
[BOJ] 백준 9370번: 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지�� www.acmicpc.net 시작점 s와 지나간 두 정점 g와 h의 정보, 전체 경로들에 대한 정보 및 목적지 후보 t가 주어질 때, 시작점에서 목적지까지 최단 경로가 시작점에서 g와 h를 잇는 간선을 지나 목적지까지 가는 최단경로의 비용이 같은 목적지 후보들을 찾는 문제입니다. 먼저 시작점에서 모든 정점까지 가는 최단 경로를 구합니다. 우선순위 큐를 사용한 다익스트라로 빠르게 구할 수 있습니다. (SPFA + SL.. 2020. 8. 9.

티스토리툴바