코딩
-
[구현] 로봇 청소기(14503)(C++)BOJ C++ 알고리즘 공부 2022. 5. 10. 15:45
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 1. 문제 개요 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r,..
-
[구현] 봄버맨(1691)BOJ C++ 알고리즘 공부 2022. 5. 8. 16:22
https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 1. 문제 개요 봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발..
-
[플로이드-와샬] 케빈 베이컨의 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이 ..
-
[플로이드-와샬] 운동(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 위와 같이 두 개의 사이클이 만들어질 수 있고 가중치 합의..