값 압축(value compression) 기본 문제로 연습

1. 문제 18869번: 멀티버스 Ⅱ (acmicpc.net) 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 2. 풀이 문제 이해하는것부터 쉽지 않았다 m개의 줄마다 리스트 A를 입력받아서 전체 리스트 universe에 저장해두고, universe에서 i,j 2개를 선택해서, (i universe[j][b]를 만족해야한다. -----..

• format_list_bulleted 압축 알고리즘
• · 2023. 4. 28.
• textsms

세 수의 최소 공배수를 최대로 만드는 방법

1. 문제 25342번: 최대 최소공배수 (acmicpc.net) 25342번: 최대 최소공배수 $N = 3$인 경우, $1, 2, 3$을 선택하면 최소공배수는 $6$이다. $N = 4$인 경우, $2, 3, 4$를 선택하면 최소공배수는 $12$이다. www.acmicpc.net 2. 풀이 3개의 수의 최소공배수가 최대가 될려면 어떻게 해야할까 두 수 a,b의 최소공배수는? a = Gn이고 b = Gm으로 표현할 수 있다면(G는 a,b의 최대공약수, n,m이 서로소) a,b의 최소공배수는 L = Gnm이다. 이 최소공배수가 가장 클려면 어떻게 해야할까? L = Gnm이므로, L = am이거나 L = bn으로 표현할 수 있다. 이 둘은 모두 ab보다 작거나 같다. 따라서, L

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

약수의 합 아주 빠르게 찾기 - 더블 카운팅(배수를 이용해 약수를 찾기), smallest prime factor

1. 문제 17427번: 약수의 합 2 (acmicpc.net) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 2. 풀이 문제를 요약하면 1부터 n까지 각각 약수의 합을 전부 더한 값을 출력하는 문제 시간이 0.5초라서 당연히 1부터 n까지 소인수분해하고 약수의 합을 구한다면 시간초과겠지 약수의 합을 구하는 공식은... https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수..

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

정수론 문제 - 나머지 연산을 꼭 기억하고 있어라

1. 문제 4375번: 1 (acmicpc.net) 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이1 문제는 n의 배수인, 1로만 이루어진 수 중에서 자리수가 가장 작은 수를 찾는 문제 아주 단순하게는 n보다 큰 1로만 이루어진 수를 생성한 다음에.. 그 수가 n으로 나누어 떨어지는지 검사해보면 된다 n의 길이를 i라 한 다음에... 1로만 이루어진 길이 i인 수부터 시작해서.. n으로 나누어가지고 가장 먼저 나누어 떨어지는 수를 출력 from sys import stdin while 1: try: n = int(stdin.readline()) i = len..

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

라그랑주의 네 제곱수 정리를 이용한 알고리즘(다이나믹 프로그래밍, 브루트포스 연습)

1. 라그랑주의 네 제곱수 정리 모든 자연수 n은 많아야 음이 아닌 4개의 정수의 제곱수 합으로 표현할 수 있다. $$n = a^{2} + b^{2} + c^{2} + d^{2}$$ 을 만족하는 0 이상의 정수 a,b,c,d가 존재한다. 증명은 매우 까다롭다.. 너무 길어서 따라하기도 힘들다.. https://jjycjnmath.tistory.com/295 [퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명 ※ 출처 - http://kevin0960.tistory.com/ 디오판토스의 저서 '산학'에는 '모든 양의 정수는 네 제곱수의 합으로 표현될 수 있다.' 라는 내용이 담겨 있다. 예를 들어, \[ \begin{aligned} 3 &= 1^2 + 1^2 + 1^2 + 0..

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

최대 비용을 가지는 신장 트리를 만드는 방법?

1. 문제 7044번: Bad Cowtractors (acmicpc.net) 7044번: Bad Cowtractors Bessie has been hired to build a cheap internet network among Farmer John's N (2

• format_list_bulleted 최소 스패닝 트리
• · 2023. 4. 20.
• textsms