- 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net - 문제 분석 1) N(건물 개수) : 2 ~ 1000 2) K(규칙 개수) : 1 ~ 100,000 3) 1 ≤ X, Y, W ≤ N 4) Di (i번째 건물의 건설 시간) : 0 ~ 100,000 각 건물을 지으려면 해당 건물을 짓기 위한 모든 선행 건물을 지어야 한다. (수강신청 커리큘럼과 비슷함) 이러한 구조의 순서를 찾기 위해서는 위상정렬(Topological Sorting..
- 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net - 문제 분석 조건 1) K(기존 랜선의 개수) : 1 ~ 10000 2) N(필요 랜선의 개수) : 1 ~ 1,000,000 3) K ≤ N 4) 랜선의 길이 : 1 ~ 231-1 (여러 랜선을 더하고 빼는 경우 int 범위 초과 => long long 사용) 문제의 요구사항대로 최대 길이의 랜선을 N개로 나누기 위해서는 기존 K개의 랜선을 나누고 난 나머지..
- 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net - 문제 분석 및 풀이 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하기 위해서 일단 풀이 과정을 2가지로 나누었다. 소수 배열을 구하기 연속된 소수의 합이 N인 경우의 수를 구하기 1) 일단 소수 배열을 구하는 것은 흔히들 사용하는 에라토스테네스의 체를 사용하였다. https://blog.naver.com/ndb796/221233595886 22. 에라토스테네스의 체 에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘입니다. 소수란 '양의 약수를 두... blog.nav..
- 문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net - 문제분석 쿼리형 문제로 매 쿼리마다 배열의 중간값을 찾고, 새로운 수를 삽입하는 문제이다. 문제의 조건 총쿼리의 수는 1 ≤ N ≤ 100,000이다. O(N2) = 1010 (100억 => 시간 초과) 따라서 O(NlogN) 이하의 시간복잡도를 가져야 한다. 다시 말해 각 쿼리를 수행하는 알고리즘은 반드시 O(logN)을 만족해야 시간 초과를 피할 수 있다. 쿼리 내..
