C - Even Digits (atcoder.jp) C - Even Digits AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 0,2,4,6,8로만 이루어진 모든 10진수 정수들을 오름차순으로 나열할 때, N번째 숫자를 구하는 문제 N이 $10^{12}$까지니 다 해보면 당연히 시간 초과일거고 최초 몇가지를 한번 나열해보면? 0 0 2 1 4 2 6 3 8 4 20 10(5) 22 11(5+1 = 6) 24 12(5+2 = 7) 26 13(5+3 = 8) 28 14(5+4 = 9) 0,2,4,6,8,20,22,24,26..
1. 문제 20915번: 숫자 카드 놀이 (acmicpc.net) 20915번: 숫자 카드 놀이 Albert 는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지 숫자 하나씩이 적혀있고, 6이나 9가 적힌 카드를 회전할 경우 구분할 수 없다 (즉, 6이 적힌 카드는 회전하면 9로 보이고, 9가 www.acmicpc.net 2. 풀이 숫자를 두 부분으로 나눠서 곱했을때, 최대가 되도록 만들기 두 부분은 적어도 하나의 숫자를 반드시 포함해야한다 6이나 9는 회전해도 구분할 수 없으니 회전해서 사용가능하다. 그렇다면 곱했을때 최대가 될려면 6은 무조건 9로 만들어서 사용하는게 유리하다. 또한 두 수의 곱이 최대가 될려면, 앞자리에는 무조건 큰 수가 오는게 유리하다 또한 두 수 a,b에 대하여 그 차..
1. 문제 3908번: 서로 다른 소수의 합 (acmicpc.net) 3908번: 서로 다른 소수의 합 양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 n과 k가 주어졌을 때, n을 서로 다른 k개의 소수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 여기서 덧셈의 순 www.acmicpc.net 2. 풀이 소수만을 사용하는데, 서로 다른 소수를 사용해야하고 k개를 사용해서 합했을때 n을 만드는 방법의 수를 구하기 일단 도구로 소수를 구해야겠지 n이 최대 1120이니까 1120이하의 소수를 모두 에라토스테네스의 체로 구해놓고 def get_prime(n): result = [1]*(n+1) for i in range(2,int(((n+1)**(1/2)))+1): if res..
1. 문제 9764번: 서로 다른 자연수의 합 (acmicpc.net) 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 2. 풀이 dp[j][i]를 1부터 i까지의 자연수 중에서 최대 하나씩만 사용해서 j를 만드는 방법의 수라고 정의하자. 여기서 구성이 같은데 순서가 달라도 같은 방법으로 취급한다 https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테..
1. 문제 27514번: 1차원 2048 (acmicpc.net) 27514번: 1차원 2048 첫 줄에 흐즈로가 정의한 연산을 $0$번 이상 수행해 만들 수 있는 가장 큰 최댓값을 출력하세요. 문제의 답은 $2^{62}$보다 크지 않음이 보장됩니다. www.acmicpc.net 2. 풀이 0이나 2의 거듭제곱으로 이루어진 수열이 있는데, 서로 같은 두 수를 찾으면 하나를 2배 해주고 다른 수는 0으로 바꿔준다 이 과정을 반복했을때, 남아있는 수열의 수 중 최댓값을 찾는 문제 처음에는 걍 수의 위치가 중요한 문제는 아니니.. 수열의 값 a와 그 개수를 value로 해서 dict[a] = value로 만들고 dict를 순회해서 value가 2개 이상 있으면 2배한 dict[2a] += 1 해주고, dict..
1. 연분수 표현에서 a,b의 최대공약수를 바로 구하는 방법 $\frac{A}{B}$의 연분수 표현을 구하고자 한다면, A/B가 기약분수 형태로 들어가줘야한다. 기약분수로 바꿀려면 A,B의 최대공약수가 g = gcd(A,B)일때, $p_{k} = A/g, q_{k} = B/g$이고 그래서 $\frac{A}{B} = \frac{p_{k}}{q_{k}}$이다. 따라서, A/B가 기약분수가 아닐때, 연분수 표현 p,q를 구한 다음 A를 p[-1]로 나눠주면 A,B의 최대공약수가 된다. #A/B가 기약분수가 아닐때, A,B의 최대공약수 구하기 def continued_fraction(p,q): f = [] while q != 0: f.append(p//q) p,q = q,p%q return f def conve..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
