본문 바로가기

정수론

 (37)
[Python] 4375번 1 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 22/10/08 처음에는 특별한 규칙이 있는 문제인 줄 알고 괜히 시간을 오래 썼었다. 알고 보니 그냥 단순한 브루트 포스라는 것을 알고 그냥 깡 구현하여 문제를 풀었다. 문제 접근 방식: 어떤 정수가 주어지면, 그에 맞춰서 가장 작은 1로만 구성된 그 정수의 배수의 자릿수를 출력하는 것이 우리의 목표이다. 때문에 파이썬의 큰 수 연산에 대한 장점을 살려서 10을 곱하고 1을 하는 연산을 반복하다 입력받은 N으로 나눠질 때, 그 자리 수를 출력하도록 단순 ..
[Python] 21919번 소수 최소 공배수 https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 22/09/25 간단한 에라토스테네스의 체 알고리즘을 적용하는 문제로, 그다지 어려운 문제는 아니다. 만약 에라토스테네스의 체 알고리즘을 잘 모르는 상태라면, 먼저 배우기를 권장한다. 문제 접근 방식: 수열들 중에서 소수들을 먼저 골라야 되고, 주어지는 숫자의 크기가 백만 이하이므로, 백만 개의 배열을 불러와 에라토스테네스의 체 알고리즘을 진행하여 소수들을 골라낸다. 이후 이 소수들의 최소공배수를 구하는 것이 우리의 목적이다. 근데 우리는 소수들끼리는 모두 최대공약수가 1이라는 사실을 알고 있다. 때문에 최소 공배수를 구하려면 그냥 그 ..
[Python] 2407번 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 22/09/17 이 문제는 파이썬의 강점을 제대로 보여주는 문제로, 다른 언어에 비해서 큰 수 연산이 뛰어나고 지원하는 함수가 많다는 장점을 매우 잘 살릴 수 있는 문제다. 문제 접근 방식: 여러 방식으로 풀 수 있지만, 나는 문제에서 의도하는 바 대로 풀고자 했다. 사실 제일 간단한 풀이는 파이썬의 math 모듈에서 지원하는 factorial함수를 사용하여 combination의 정의를 사용해 문제를 푸는 것이다. 나 같은 경우는 문제에서 원하는 바 대로, 파스칼의 삼각형을 이용하여 DP문제로 풀었다. nCm ..
[Python] 4948번 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 22/09/15 마찬가지로 그룹 채점 현황에 있는 무작위 문제 중 한 문제를 푼 것으로, 기존에 있던 에라토스테네스의 체 코드를 재활용하여 문제를 쉽게 풀었다. 문제 접근 방식: 문제가 n을 입력받으면 n과 2n 사이에 있는 소수의 개수를 출력하는 것이 문제이므로, 에라토스테네스의 체를 구현하면 될 것이라고 생각했다. 에라토스테네스의 체는 다음과 같이 구현했다. 먼저 크기가 정해진 배열을 ..
[Python] 25371번 k진수 정수의 자릿수 나누기 25371번: k진수 정수의 자릿수 나누기 (acmicpc.net) 25371번: k진수 정수의 자릿수 나누기 양의 정수 n과 k가 주어진다. n을 k진수로 변환한 수를 a라고 하자. a의 각 자릿수를 0을 기준으로 나눈 결과를 집합 b라고 하자. 0이 연속으로 나와서 공백이 생기는 경우는 집합 b에 포함되지 않는 www.acmicpc.net 22/09/09 정직한 제목, 정직한 문제이다. 제목과 걸맞게 잘 구현하면 되는 문제이다. 문제 접근 방식: 10진법으로 입력받은 숫자를 k진법으로 변환시켜주는 함수를 정의했다. 이 함수는 너무나도 잘 알려져 있고, 진법에 관한 지식이 있다면 충분히 구성할 수 있기 때문에 설명하지 않겠다. 그냥 그 함수와 파이썬의 sum함수, 그리고 '0'을 기준으로 분리하는 sp..

티스토리툴바