전체 글 썸네일형 리스트형 Codeforces Round #672 (Div. 2) A~C1번 풀이 얼마 전 Codeforces Round #672 (Div. 2)에 참가했습니다. 처음으로 문제를 3개나 풀어서 행복했습니다. 그래서 대회 중 풀었던 A번, B번, C1번의 풀이를 써 보려 합니다. A번 - Cubes Sorting 문제 Problem - A - Codeforces codeforces.com 문제 설명 $N$개의 정육면체가 한 줄로 놓여 있을 때, 부피가 큰 순으로 정렬한다고 합니다. 단, 두 인접한 정육면체를 교환하는 작업만 할 수 있습니다. 각 정육면체의 부피가 주어질 때, 정렬을 위해 필요한 최소 교환 횟수가 $\frac{N\times (N-1)}{2}$회 미만이라면 YES, 아니면 NO를 출력하는 문제입니다. 풀이 두 인접한 원소만 교환하여 정렬하는 알고리즘으로는 버블 정렬이 있습니.. 더보기 백준 2981번 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간�� www.acmicpc.net 풀이 N개의 수 중 i번째 수를 $a_i$라고, 구하고자 하는 값을 $M$이라고 하겠습니다. N개의 수는 $M$으로 나눈 나머지가 모두 같아야 하므로 이때의 나머지를 $k$라고 하면 $1\leq i\leq N$인 모든 $i$에 대해 $a_i - k$는 $M$의 배수입니다. 따라서 N개의 수 중 어떤 두 수를 잡더라도 두 수의 차는 $M$의 배수가 됩니다. 즉, $1\leq i, j\leq N$인 모든 $i, .. 더보기 백준 10888번 두 섬간의 이동 https://www.acmicpc.net/problem/10888 10888번: 두 섬간의 이동 1에서 N까지 번호가 붙은 N개의 섬이 일렬로 쭉 늘어서 있다. 이 섬들 간에는 아직 다리가 없어서 배로만 이동을 해야 했기에 매우 불편했다. 그렇기에 정부에서는 이 섬들에 다리를 연결하고자 � www.acmicpc.net 무려 열두 번 틀린 문제입니다. 그렇다고 어려운 문제는 아닙니다.. 풀이 방법 임의의 A개의 섬이 A-1개의 다리를 통해 모두 연결되어 있다면, 이 A개의 섬에 대해 연결된 쌍의 개수와 최소 다리 개수의 합을 구할 수 있습니다. 1. 쌍의 개수 A×(A-1) / 2 = 쌍의 개수입니다. 2. 최소 다리 개수의 합 섬 A개가 모두 연결되어 있을 때, 다리 1개를 거쳐 연결되어 있는 쌍의 개.. 더보기 백준 2660번 회장 뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 각 회원을 정점으로, 친구사이를 가중치가 1인 간선으로 생각하면 회원의 점수는 그 회원과 가장 멀리 떨어진 정점과의 거리가 됩니다. 이를 구하려면 모든 회원 간의 관계 (모든 정점 사이의 거리) 를 알아야 하므로 플로이드-와샬 알고리즘을 적용하였습니다. 정점의 수가 N일 때 O(N^3)인 알고리즘이지만 회원의 수 (정점의 수) 가 최대 50이므로 사용할 수 있습니다. 코드 1234567891.. 더보기 백준 1655번 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 N개의 정수를 입력받아 1번째, 2번째, ... N번째 정수까지만 보았을 때 각각의 중앙값들을 출력하는 문제입니다. 풀이 단순히 배열을 사용하여 입력받을 때마다 배열을 정렬한다면 O(N^2)이므로 시간초과일 것입니다. 힙을 이용하여 O(NlogN)으로 해결할 수 있습니다. 지금까지 입력받은 수 중 절반의 작은 수들은 최대 힙에, 나머지 절반의 큰 수들은 최소 힙에 저장합니다... 더보기 이전 1 2 3 4 다음
