ABC 324 - D번 복기, 순열 다루는 테크닉 - 두 문자열이 서로의 순열일려면? -

1. 문제 D - Square Permutation (atcoder.jp) D - Square Permutation AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 주어진 정수 문자열의 순열이 어떤 정수의 제곱수가 될때, 그러한 순열의 개수를 구하는 문제. 길이 제한이 13이라고 해도 모든 순열을 찾고, 각 순열이 어떤 수의 제곱수인지 검사하면 매우 느리다 1) 만약 길이 N인 s의 순열이 X의 제곱수가 될려면, X는 아무리 커봐야 $\sqrt{10^{N}}$이다. 그러므로 0부터 $\sqrt{10^{N}}$까..

• format_list_bulleted Atcoder
• · 2023. 10. 15.
• textsms

디오판토스 분수방정식의 정수 해법 배우기(+팩토리얼 인수분해, 제곱수의 약수의 개수)

1. 문제1 7516번: 알렉산드리아의 디오판토스 (acmicpc.net) 7516번: 알렉산드리아의 디오판토스 알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오 www.acmicpc.net 2. 풀이 주어진 방정식 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 정리하면, $$\frac{y+x}{xy} = \frac{1}{n}$$ 이다. 그래서 $$n(y+x) = xy$$ 를 얻는다. 솔직히 여기서 넘어가기 어려운데, (억지라는 생각이 들 정도..) $n^{2} = pq$라 하자. p,q는 정수이다. 즉, p,q는 $n^{2}$의 약수이다. 그리고..

• format_list_bulleted 정수론
• · 2023. 7. 14.
• textsms

알고리즘 테크닉 - 런타임 전의 전처리 기법

1. 런타임 전의 전처리(preprocessing) 실제 문제를 해결하는 프로그램을 작성하기 전에, 해당 프로그램의 핵심을 얻기 위한 다른 프로그램을 미리 작성하여 원하는 값을 구해놓고, 문제를 해결하는 프로그램을 작성하는 기법 프로그램 안에 원하는 값을 계산하는 코드를 작성하지 않고, 미리 필요한 값을 계산해놓은 다음에 실제 프로그램에서 시간복잡도를 줄이는 기법이다. 이런 기법은 사실 알게모르게 많이 써왔다.. 최근에 이것이 핵심인?문제를 풀어서 복기해본다 (태그는 이분탐색이었지만) 2. 문제 4030번: 포켓볼 (acmicpc.net) 4030번: 포켓볼 선영이는 당구대를 상근이에게 빌렸다. 상근이는 선영이에게 공 16개가 들어갈 수 있는 4×4 크기의 트레이도 같이 주었다. 이 트레이는 그림 (a)..

• format_list_bulleted 전처리
• · 2023. 4. 3.
• textsms

약수의 개수가 짝수인지 홀수인지 바로 알아내는 제곱수 판단하는 방법

1. 문제 11815번: 짝수? 홀수? (acmicpc.net) 11815번: 짝수? 홀수? B를 A로 나누었을 때 나머지가 0 이라면 A는 B의 약수라고 할 수 있다. (A > 0, B > 0) 예를 들면 15 의 약수는 1, 3, 5, 15 이다. 주어진 수가 가지는 약수 개수가 홀수인지 짝수인지 판별해보자. www.acmicpc.net 2. 풀이 소인수분해 해서 (지수+1)의 곱의 합으로 짝수인지 홀수인지 판단해볼라했는데 수가 10의 18제곱까지 있어서 그런지 시간초과 from sys import stdin n = int(stdin.readline()) num_list = list(map(int,stdin.readline().split())) for i in num_list: p = 2 answer..

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

약수의 합과 약수의 개수 공식 익히기

1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$ 라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$ n을 소인수분해하여, 소인수들의 지수 + 1의 곱의 합이 약수의 개수이다. 1-1) 간단한 증명 왜냐하면 n의 약수는 $p_{1}, p_{2}, ... , p_{k}$들의 곱으로 이루어져 있는데, 각각은 $x_{1}, x_{2}, ... , x_{k}$개씩 사용할 수 있다. 따라서 곱의 법칙에 의해 모든 경우의 수는 $p_{1}, p_{2}, ... , p_{k}$을 각각 (0,1,2,...,$x_{1}$), (0,1,2,...,$x_{2}$), ... , (0..

• format_list_bulleted 정수론
• · 2022. 12. 26.
• textsms