C++
-
[BFS/DFS] 이분 그래프(1707)BOJ C++ 알고리즘 공부 2022. 5. 8. 17:54
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 문제 개요 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 2. 입출력 3. 문제 풀이 BFS 또는 DFS를 이용하되 그래프를 색칠해나가면서 이분 그래프..
-
[구현] 봄버맨(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)도 함께 파괴된다. 만약, 폭탄이 폭발..
-
[그리디] 잃어버린 괄호(15410)(C++)BOJ C++ 알고리즘 공부 2022. 4. 17. 12:22
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1. 문제 개요 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 2. 입출력 3. 문제 풀이 식의 값이 최소가 되기 위해서는 빼주는 값이 최대한 많아야 한다. 55-50+40 다음과 같..
-
[그리디] 주유소 (13305)(C++)BOJ C++ 알고리즘 공부 2022. 4. 3. 17:13
https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 1. 문제 개요 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. ..
-
[수학] 카잉 달력(6064) (C++)BOJ C++ 알고리즘 공부 2022. 3. 20. 15:25
https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 1. 문제 개요 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 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 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다. 세 개의 점이 시..