숫자를 안만들고 나머지를 구하는 방법, 문자열 연산 없이 두 수를 붙이는 방법

1. 문제 27965번: N결수 (acmicpc.net) 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 2. 풀이1 쉽다는데... 솔직히 까다로운 문제같다 n이 10의 7제곱까지라 n결수를 만들면 당연히 시간초과일거고 (애초에 만들어지지도 않음) 그 전에 근본적으로 나눗셈 연산을 어떻게 하는지 생각을 해보면.. 1234를 5로 나누는 것은 어떻게 할까? 1을 5로 나눠보고.. 몫이 0이고 나머지가 1이니까 ..

• format_list_bulleted 정수론
• · 2023. 5. 8.
• textsms

밀러 라빈 소수 판별법(Miller-Rabin primality test) 배우기

1. 밀러 라빈 소수 판별법(Miller-Rabin primality test) 어떤 홀수 n이 소수인지 확률적으로 판별해주는 알고리즘 확률적이라는 말은, 합성수를 소수로 잘못 판별할 수 있다는 뜻이다. 주어진 n이 "합성수이다" 또는 "아마도 소수일 것이다"라는 대답을 내놓는다는 의미 2. 핵심 아이디어 알고리즘의 아이디어는 페르마의 소정리에서 시작한다. https://deepdata.tistory.com/573 페르마의 소정리 문제 풀어보면서 익히기 1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$ 이다. 1-2) p가 소수이..

• format_list_bulleted 정수론
• · 2023. 5. 5.
• textsms

세그먼트 트리 기본문제로 연습하며 재활(반복문, 재귀 연습)

1. 문제1 11143번: Beads (acmicpc.net) 11143번: Beads The first line of the input consists of a single number T, the number of games played. Each game start with a line describing B, P and Q, the number of boxes, put requests and query requests, respectively. Then follows P + Q lines with either P i a, saying www.acmicpc.net 2. 풀이 문제를 요약하자면 구간의 합을 구하는 세그먼트 트리 create_segment라는 함수는 만들필요가 없다 P라는 query가 ..

• format_list_bulleted 세그먼트 트리
• · 2023. 5. 5.
• textsms

manacher 응용문제로 이해력 높이기 - 회문인 부분문자열의 개수를 찾는법

1. 문제 16163번: #15164번_제보 (acmicpc.net) 16163번: #15164번_제보 www.acmicpc.net 2. 풀이 연속인 부분문자열에서 회문의 개수를 구하는 문제 manacher 알고리즘을 수행하면서, 나타나는 회문의 개수를 세면 될 것이다... 그런데 회문의 개수를 어떻게 세야할까 예를 들어 ABCBA에 대해서.. manacher 알고리즘을 수행하기 위해 #을 붙여가지고 #A#B#C#B#A#으로 바꾸고 나서.. 각 index에 대해서 양쪽으로 확대해나가 회문인지 찾아나갈텐데 A배열은 각 위치에서 가장 긴 회문의 반지름 길이를 나타내는 것으로, 가장 긴 회문의 반지름 길이를 알고 있다면, 이는 그보다 작은 회문도 포함하고 있는거니까, 이 값을 이용한다면 해당 지점에서 회문의 ..

• format_list_bulleted 문자열 알고리즘
• · 2023. 5. 4.
• textsms

반복문으로 구현하는 세그먼트 트리(iterative segment tree) 배우기

1. 반복문으로 구현하는 세그먼트 트리 세그먼트 트리 기본 버전은 재귀함수로 구현되어 있다 import math def create_segment(A,tree,tree_index,start,end): if start == end: tree[tree_index] = A[start] else: mid = (start+end)//2 create_segment(A,tree,2*tree_index,start,mid) create_segment(A,tree,2*tree_index+1,mid+1,end) tree[tree_index] = tree[2*tree_index] + tree[2*tree_index+1] def query_sum(tree,tree_index,start,end,left,right): if lef..

• format_list_bulleted 세그먼트 트리
• · 2023. 5. 4.
• textsms

1부터 n까지의 최소공배수를 빠르게 구하는 방법

1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..

• format_list_bulleted 정수론
• · 2023. 5. 4.
• textsms