본문 바로가기

분류 전체보기

 (191)
정렬 시간 비교 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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 #include #include #include #include #define SWAP(a,b,t)(t=a,a=b,b=t) using namespace std; vector i..
레이스( BOJ 1508 ) 문제 : https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어 www.acmicpc.net 문제 파악하기 M명의 심판을 배치하는 여러 가지 경우 중, 가장 가까운 심판 사이의 거리가 최대인 경우를 구하는 문제입니다. 만약 모든 경우의 수를 조사한다면, 최악의 경우 1,000,000개 자리 중 50명의 심판을 배치하는 모든 가짓수를 조사해야 합니다. 터무니없이 많기 때문에 문제를 조금 바꿀 필요가 있습니다. 문제를 최적화 문제에서 결정문제로 바꿔봅시다. ..
그래프 균형 맞추기( BOJ 22344 ) 문제 : https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 문제 파악하기 그래프 내 간선의 가중치가 주어질 때, 그래프의 균형을 맞출 수 있는 여러 가지 방법 중 모든 정점 가중치 값의 절댓값 합이 가장 작은 경우를 구하는 문제입니다. 그래프의 균형은 두 정점을 연결하는 간선의 가중치와 두 정점의 가중치의 합이 같은 경우를 의미합니다. 문제 예시 그림과 같이 모든 간선의 가중치 값이 연결된 정점의 합과 일치하는 경우를 의미하며, 균..
개구리 점프( BOJ 17619 ) 문제 : https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 문제 파악하기 개구리가 점프를 해서 원하는 통나무까지 이동할 수 있는지 확인하는 문제입니다. 통나무들은 항상 가로방향으로 연못에 떠 있으며, 개구리는 항상 수직적인 방향으로 점프할 수 있습니다. 그렇기에 개구리는 항상 통나무의 값이 조금이라도 겹친다면 무조건 점프할 수 있습니다. 따라서, 우리는 모든 통나무에 대해서 서로 겹쳐있는지 확인하고, 겹..
헬기 착륙장( BOJ 22348 ) 문제 : https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악하기 2개의 페인트통을 사용해서 헬기 착륙장을 그릴 수 있는 경우의 수를 구하는 문제입니다. 헬기 착륙장은 반지름이 서로 다른 원으로 구성되어 있으며, 반지름이 1부터 R까지 1씩 차이나게 그릴 수 있습니다. 하나의 헬기 착륙장은 항상 하나의 색으로만 만들 수 있으며, 각각의 페인트통이 최대 50,000개 있기 때문에 그릴 수 있는 헬기착륙장의 최대 크기는 대략 450입니다. 따라서, 우리..
등산 마니아( BOJ 20188 ) 문제 : https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 문제 파악하기 N개의 오두막과 (N-1)개의 오솔길로 이루어진 등산로가 주어질 때, 경로의 다양성을 구하는 문제입니다. 여기서 말하는 경로의 다양성이란 i번째 오두막에서 j번째 오두막으로 정산을 거쳐 이동할 때, 지나는 서로 다른 오솔길의 개수를 의미합니다. N개의 오두막 사이에 나올 수 있는 모든 경로의 다양성을 구해야하는데, 단순히 모든 경우의 수를 구하기에는 오두막의 개수가 3..
등수 찾기( BOJ 17616 ) 문제 : https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 문제 파악하기 N명의 사람 중 주어진 X가 될 수 있는 등수의 범위를 찾는 문제입니다. 등수의 범위라고 하니 뭔가 확률적으로 생각해야 될 것처럼 보이지만 등수의 의미를 생각한다면 그리 어렵지 않게 풀 수 있는 문제입니다. 문제 해결하기 그렇다면 등수의 의미는 무엇일까요? 등수란 자신보다 앞에 몇 명이 있으며, 뒤에 몇 명이 ..
Cereal( BOJ 18878 ) 문제 : https://www.acmicpc.net/problem/18878 18878번: Cereal Farmer John's cows like nothing more than cereal for breakfast! In fact, the cows have such large appetites that they will each eat an entire box of cereal for a single meal. The farm has recently received a shipment with $M$ different types of cereal $(1\ www.acmicpc.net 문제 파악하기 소들이 자신의 선호도 순위대로 시리얼을 먹거나 시리얼을 포기할 때, 0마리 ~ (i-1)마리 소가 앞에서부..

티스토리툴바