15319번: 동혁이의 생일선물 정수 x의 거듭제곱 $x^{0}, x^{1}, x^{2}, ... $에 대하여 이들의 모든 부분집합 A1, A2, ...을 생각하자 각 부분집합의 원소들의 합을 M1, M2,...라고 할 때 이들을 오름차순으로 정렬하면 수열 a1, a2,...를 얻는다 이때 k번째 원소 ak에 대하여 n개의 x,k가 주어질때 각각 구한 모든 ak의 합을 10^9 + 7로 나눈 나머지를 구한다 --------------------------------------------------------------------------------------------------------------------------------------------------------------- 2,3,4,....
1206번: 사람의 수 (acmicpc.net) n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가 실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제 평균이 소수점 셋째자리까지만 주어진다 예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는 ---------------------------------------------------------------------------------------------------------------------------------- 만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면 $$\frac{v}{x} \approx A[i]$$ A..
1. 1보다 큰 10진수를 다른 진수로 변환하는 방법 주어진 수를 변환하고자하는 진수의 base로 계속 나누고 나머지를 써둔다 마지막에 저장해둔 나머지 뒤에서부터 가지고옴 예를 들어 133은 3진법으로 변환하면 $11221_{(3)}$이다. 2. 10진수 소수를 진수 바꾸는 방법 반면 소수는 방법이 조금 다른데 base를 계속 곱해나간 뒤 소수점을 넘은 정수는 옆에 따로 저장해두고 정수를 뺀 나머지를 다음 단계로 보낸 뒤 base를 계속 곱해 다음 단계로 보낸 나머지 부분이 0이 될때까지 반복함 정수 변환은 맨 뒤에서부터 앞으로 가지고 왔지만 맨 처음부터 따로 저장한 수를 맨 뒤까지 가지고 오면 끝 예를 들어 0.375는 8진수로 변환하면 $0.3_{(8)}$이고 0.1을 2진수로 변환하면 $0.00..
8672번: Drabina (acmicpc.net) 사다리의 맨 끝단 s까지 올라가는데 한걸음 혹은 두걸음씩 올라갈 수 있다 이 때 끝까지 올라가는 방법의 수를 $2^{p}$로 나눈 나머지를 구해야한다. 이것만 보면 매우 쉬운 문제다 dp[i] = i번째까지 올라가는 방법의 수하면 가능한 경우는 한걸음 혹은 두걸음이므로... dp[i] += dp[i-1]dp[i] += dp[i-2] 인 전형적인 문제 dp = [0]*(s+1)dp[0] = 1mod = 2**pfor i in range(1,s+1): for j in range(1,3): if i >= j: dp[i] += (dp[i-j]) dp[i] %= mod 문제는 최대 ..
25309번: K개의 소수 (acmicpc.net) 정수 n을 k개의 소수 합으로 표현하라는 문제 여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다. 그리고 문제는 n이 최대 $10^{8}$이고 k는 최대 10000이라 단순한 방법으로는 어렵다 먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다. 따라서 n = 2k이면 일단 분해하는 것이 가능하다. n,k = map(int,input().split())if n 만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다. $O(\sqrt{n})$에 소수 판단할 수 있다. def is_prime(n): for i in range(2,int(n**..
SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어떤 정수 x의 약수 중 홀수인 약수의 합을 f(x)라고 할때, L,R이 주어지면 L이상 R이하의 모든 x에 대해 f(x)의 합을 구하는 문제 단순한 방법으로는 소인수분해를 해서 홀수인 소인수들의 곱으로 약수의 합을 구하면 된다. https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
