728x90 Baekjoon Online Judge15 백준 No.7420 [맹독 방벽] BOJ No.7420 [맹독 방벽] 문제 7420번: 맹독 방벽 (acmicpc.net) 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 설명 * 볼록 껍질 (컨벡스 헐 : Convex hull) 볼록 껍질을 응용하여 풀 수 있는 문제이다. 아래 예시를 들어 보았다. 건물들의 좌표를 위와 같이 입력을 해 보았다. 또한 해당 좌표들을 좌표평면에 표시 해 보았다. 위 좌표들을 모두 감싸면서 건물들에선 최소 L 만큼 떨어져 있어야 하는 방벽을 세워야 한다. .. 2022. 3. 28. 백준 No.1708 [볼록 껍질] BOJ No.1708 [볼록 껍질] 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 설명 * 볼록 껍질 / 컨벡스 헐 (Convex hull) 볼록 껍질 위와 같이 평면 좌표에 N개의 점이 있을 때 점들을 이어 볼록 다각형을 만들면서, 잇지 않은 나머지 점들은 볼록 다각형 내부에 있도록 하는 것 이다. 볼록 껍질을 구현하기 위한 전처리 과정은 아래와 같이 정리할 수 있다. 1. 점들 중 껍질을 만들기 시작하는 점을 찾는다. - 보통 y값.. 2022. 3. 26. 백준 No.2887 [행성 터널] Baekjoon Online Judge No.2887 [행성 터널] 문제 2887번: 행성 터널 (acmicpc.net) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 설명 최소 스패닝 트리(최소 스패닝 트리 / 최소 신장 트리 (MST)) 를 통해 풀 수 있는 문제이다. 각 정점끼리의 간선의 가중치의 값은 두 정점의 거리에 따른다. 결국 모든 정점 사이에 간선이 존재하게 된다. 정점의 수는 최대 100,000 개 이기 떄문에 이 때 총 간선의 수는 약 (100,000^2) .. 2021. 8. 10. 백준 No.11404 [플로이드] BOJ No.11404 [플로이드] Floyd-Warshall Algorithm Problem 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include using namespace std; typedef unsigned long long ull; int V, E; const ul.. 2021. 2. 20. 백준 No.11779 [최소비용 구하기2] BOJ No.11779 [최소비용 구하기2] Problem 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #inc.. 2021. 2. 19. 백준 No.13913 [숨바꼭질4] Baekjoon Online Judge No.13913 [숨바꼭질4] Problem 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #.. 2021. 2. 16. 백준 No.13549 [숨바꼭질3] Baekjoon Online Judge No.13549 [숨바꼭질3] Problem 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #include #include #define pos first #define ti.. 2021. 2. 16. 백준 No.1504 [특정한 최단 경로] Baekjoon Online Judge No.1504 [특정한 최단 경로] Problem 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 .. 2021. 2. 9. 백준 No.11066 [파일 합치기] Baekjoon Online Judge No.11066 [파일 합치기] Problem 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #incl.. 2021. 2. 7. 백준 No.12865 [평범한 배낭] Baekjoon Online Judge No.12865 [평범한 배낭] Problem 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #define weight first #define value second using nam.. 2021. 2. 6. 백준 No.10942 [팰린드롬?] Baekjoon Online Judge No.10942 [팰린드롬?] Problem 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace.. 2021. 2. 5. BOJ No.2798 [블랙잭] Baekjoon Online Judge No.2798 [블랙잭] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include using namespace std; int N, M; vector cards; int main() { cin >> N >> M; cards.resize(N); for (int i = 0; i > cards[i]; int answer = 0; for (int i = 0; i 2021. 2. 5. lower_bound, upper_bound lower_bound & upper_bound std::lower_bound - cppreference.com std::upper_bound - cppreference.com Definition lower_bound : 찾고자 하는 값 이상의 수가 처음으로 나오는 곳의 index를 구할때 사용 upper_bound : 찾고자 하는 값보다 큰 수가 처음으로 나오는 곳의 index를 구할때 사용 How to use Binary search를 기반으로 탐색되므로, 탐색되는 vector 혹은 list 는 sort 되어있어야 한다. lower_bound, upper_bound는 구하고자 하는 곳의 iterator를 return 한다. 따라서 실제로 사용할 경우 구한 lower_bound 혹은 upper_bound.. 2021. 2. 4. 백준 No.11049 [행렬 곱셈 순서] Baekjoon Online Judge No.11049 [행렬 곱셈 순서] Problem 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 7.. 2021. 2. 4. 백준 No.1912 [연속합] Baekjoon Online Judge No.1912 [연속합] Problem 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int N; vector nums; void input() { cin >> ::N; nums.assign(N, 0); for (int i = .. 2021. 2. 2. 이전 1 다음 728x90
