본문 바로가기

알고리즘13

2110번 - 공유기 설치 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 요약: -> N개의 좌표에서 C개의 공유기를 설치하는데, 인접한 두 공유기 사이의 최대 거리를 계산 해결 방법: 1) C - 2번의 이분 탐색을 계속 진행하는 방법 => 이렇게 하면 계산량과 저장공간이 너무 많이 들어서 비효율적이다. => 아래 그림처럼 x1 > x2인 경우에 x1을 분할하면서 C개의 공유기를 찾는 방식이다. .. 2021. 3. 29.
11401번 - 이항 계수 3 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/11401 문제요약: -> 이항계수 (N, K)을 1,000,000,007으로 나눈 나머지에 대해 출력 해결방법: 1) 이항계수 (N, K)을 구해서 1,000,000,007으로 나눈다. => 제일 간단한 방법이지만, N값이 크면 이항계수 (N, K)의 값을 저장할 방법이 없다. 2) "페르마의 소정리"을 이용해서 값을 구한다. => ap-1 ≡ 1 (mod p) {단, p: 소수, a: 정수} 소스코드: 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 .. 2021. 3. 1.
1676번 - 팩토리얼 0의 개수 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제요약: -> N!을 계산하고 그 계산된 값에서 뒤에서부터 0이 몇 개 나타나는 지 계산하는 문제 해결방법: 1) N!을 직접 계산하고 0의 개수를 센다. -> 이렇게 계산하는 것이 제일 간단하지만, 시간이 너무 오래 걸리고 숫자의 크기가 너무 커진다는 문제가 있다. 2) 0의 개수는 N!을 소인수분해해서 2의 개수와 5의 개수 중 작은 수이다. -> 2와 5를 곱하면 10이 되어서 뒤에 0이 생기므로, 큰 수 가 아니고 작은 수다. 소스코드: #include lon.. 2021. 1. 20.

티스토리툴바