문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 설명 최소 스패닝 트리는 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 이번 문제에서는 프림 알고리즘을 통해 최소 신장 트리를 구할 것이다. 먼저 간선의 정보를 저장할 Edge 클래스를 만든다. 우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다. c..
문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 설명 (n + 1) 개의 집합 { 0 }, { 1 }, { 2 }, ... , { n } 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 각 (n + 1) 개의 집합은 서로소 집합이다. 합집합 연산이 필요할 때에는 union()를 사용하고 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산이..
문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 설명 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 여러 개의 건물을 동시에 지을 수 있다. 건물을 짓는데 우선순위가 있으므로 이는 DAG로 나타낼 수 있다. 먼저 건물을 짓는데 걸리는 시간과 후행자로 가지는 건물 번호 리스트를 저장할 Build 클래스를 만든다. class Build { int time; ArrayList successor; public Bui..
문제 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 설명 1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N × (N-1) × … × 2 ×1 가지가 있다. 둘째 줄의 첫 번째 수가 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 구해야 한다. 먼저 순열을 ..
문제 https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 설명 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있고 알파벳 순서대로 수록되어 있다. 사전에서 K번째 문자열이 무엇인지 구해야 한다. 사전에 수록되어 있는 문자열의 갯수는 \({}_{N + M}\mathrm{C}_{M}\) 이다. 그 값이 K보다 작다면 -1을 출력하고 그렇지 않다면 query를 진행해 K번째 문자열을 찾는다. if (combination(N + M, ..
문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 설명 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. 한 사이트에는 최대 한 개의 다리만 연결될 수 있고 다리끼리는 서로 겹쳐질 수 없다. 실행결과는 M개의 사이트 중 N개를 순서 구분 없이 고르는 경우의 수를 의미한다. 따라서, 조합을 사용해야 하는데 파스칼의 삼각형을 이용하면 쉽게 구할 수 있다. 파스칼의 삼각형은 \({}_{n}\mathrm{C}_{r} = {}_{n ..
문제 https://www.acmicpc.net/problem/3955 3955번: 캔디 분배 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100) 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어져서 주어진다. (1 ≤ K, C ≤ 109) 선영이는 부자가 아니기 때문에 www.acmicpc.net 설명 선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 (K × X + 1) 개를 구매하려고 한다. 사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 C개 들어있다 문제 조건을 식으로 나타내면 K x X + 1 = C x Y (X, Y는 자연수) 이다. 이 식을 베주 항등식으로 바꾸고 변수를 보기 편하게 바..
문제 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 설명 N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지게 해야 한다. 모든 경우의 수를 하나하나 따지면 수행시간이 O(\(N^{2}\)) 이지만 누적합을 사용하면 O(N) 으로 해결할 수 있다. LtoR 배열에는 배열 좌측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다. RtoL 배열에는 배열 우측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다. 최대공약수를..
