수학

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[BJ13458] 시험 감독
🚩 문제 설명 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net ⏱️ 시간 복잡도 ▪ 각 시험장의 길이만큼 반복문을 돈다. ▪ 따라서 O(N) ◾ 간단한 사칙연산으로 풀 수 있는 문제입니다. ◾ 각 시험장에 필요한 총 감독관의 최소값을 출력하면 됩니다. ✅ 입출력 1. n : 시험장 개수 2. a : 각 시험장에 있는 응시자의 수 3. b c : 총감독관 감시 가능 응시자 수, 부감독관 감..
→2022.04.28
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ2004] 조합 0의 개수
✅ 조합 0의 개수 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net ◾ 평소 같은 방법으로 풀면 위와 같은 재밌는 결과를 볼 수 있다. import sys N, M = map(int, sys.stdin.readline().split()) def factorial(num, v): ans = 0 i = v while i
→2021.12.01
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ1676] 팩토리얼 0의 개수
✅ 팩토리얼 0의 개수 import sys N = int(sys.stdin.readline()) def factorial(n): if n
→2021.12.01
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ10872] 팩토리얼
✅ 팩토리얼 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net import sys N = int(sys.stdin.readline()) def factorial(n): if n
→2021.12.01
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ6588] 골드바흐의 추측
🚩 문제 설명 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 2부터 N 까지의 수 중에서 소수를 골라 합으로 나타낸다. ▪ 시간복잡도는 O(abs(N) x logN) 으로 해결할 수 있다. ◾ 두 소수의 합으로 해당 테스트 케이스의 수를 나타내는 문제 ◾ 골드바흐의 추측 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. ex) 3 + 5 = 8 ✅ 입출력 1) 각각의 테스트 케이스가 ..
→2021.12.01
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ1929] 소수 구하기
🚩 문제 설명 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ⏱️ 시간 복잡도 ▪ 총 N개의 수가 있다. ▪ 해당 수열에서 어떤 수가 소수인지 알아내는 데에는 O(abs(N)) 이 걸린다. ▪ N개의 수열 중에서 모든 소수를 찾는 데에는 O(N x abs(N)) 이 걸린다. ▪ 해당 문제에서 N의 최대 범위가 100만 이므로 총 시간복잡도는 10^9가 되고 이는 시간초과를 일으킨다. ▪ 따라서 에라토스테네스의 체 라는 방식으로 소수를 구하면 O(NlogN)으로 좀 더 빠르게..
→2021.12.01

• 이전
• 1
• 2
• 다음