BOJ C++ 알고리즘 공부
-
[플로이드-와샬] 케빈 베이컨의 6단계 법칙(1389) (C++)BOJ C++ 알고리즘 공부 2022. 2. 27. 17:22
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 1. 문제 개요 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 예를 들어, 1이 2와 아는 사이이고 2가 3과 아는 사이, 3과 4는 아는 사이이면 1과 4는 3단계만 거치면 된다. 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이..
-
[기하학] 선분 교차 3 (20149) (C++)BOJ C++ 알고리즘 공부 2022. 2. 17. 19:21
https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제. 선분 교차 2 문제와 같지만 선분이 한 점에서 만나는 경우 점의 좌표를 출력하는 문제. 2. 입출력 3. 문제 풀이 선분 교차 1 문제와 같이 점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다. CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다. 세 개의 점이 시..
-
[기하학] 선분 교차 2(17387) (C++)BOJ C++ 알고리즘 공부 2022. 2. 16. 22:31
https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제. 선분 교차 1 문제와 같지만 세 점 이상의 점이 나란히 있는 경우를 고려해야하는 문제. 2. 입출력 3. 문제 풀이 선분 교차 1 문제와 같이 점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다. CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다. 세 개의 점이 시..
-
[기하학] 선분 교차1 (17386) (C++)BOJ C++ 알고리즘 공부 2022. 2. 15. 18:07
https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제. 2. 입출력 3. 문제 풀이 점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다. CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다. 세 개의 점이 시계 방향, 반시계 방향 또는 평행하게 놓여있는지 여부를 알 수 있다. ty..
-
[기하학] CCW(11758) (C/C++)BOJ C++ 알고리즘 공부 2022. 2. 12. 16:23
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어질때 이를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 문제. 2. 입출력 3. 문제 풀이 첫번째, 두번째 점을 이용하여 직선의 방정식을 구하고, 세번째 점을 방정식에 대입했을 때 양수가 나오면 반시계 방향, 음수가 나오면 시계 방향, 0이 ..
-
[기하학] 두 원(7869) (C++)BOJ C++ 알고리즘 공부 2022. 2. 11. 19:19
https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 1. 문제 개요 2차원 평면상에 두 원이 주어질 때, 교차하는 영역의 넓이를 소수점 셋째자리 구하는 문제. 2. 입출력 3. 문제 풀이 두 원이 만나는 경우는 네가지로 나눌 수 있다. 첫번째는 두 원이 만나지 않는 경우이다. 이 경우에는 두 원의 중심의 거리가 두 원의 반지름을 합한 값보다 크다. 두 원이 교차하는 영역이 존재하지 않게 된다. 두번째는 한 원이 다른 원에 포함되지 않으면서 한 점에서 만나는 경우이다. 이 경우에는 두 원의 중심의 거리가 두 원의 반..
-
[기하학] 다각형의 넓이(2166) C++BOJ C++ 알고리즘 공부 2022. 2. 10. 00:38
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 1. 문제 개요 2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 주어질 때, 이 다각형의 면적을 구하는 문제. 2. 입출력 3. 문제 풀이 다각형을 이루는 순서대로 점이 주어지므로 신발끈 공식을 사용해서 해결할 수 있다. 4. 전체 코드 #include #include #include #include using namespace std; //다각형의 넓이 int main(){ vector v; ..
-
[플로이드-와샬] 운동(1956)BOJ C++ 알고리즘 공부 2022. 2. 7. 23:38
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 문제 개요 1번부터 V번 마을이 있을 때, 시작점으로 돌아오는 사이클 중 가중치 합의 최솟값을 찾는 문제. 예를 들어 입력 값이 다음과 같이 주어질때, 3 4 //정점수, 간선수1 2 1 3 2 11 3 5 // 1에서 3로 가는 노드의 가중치가 52 3 2 2 -> 3 -> 2 3 -> 2 -> 3 위와 같이 두 개의 사이클이 만들어질 수 있고 가중치 합의..