1. 문제 14860번: GCD 곱 (acmicpc.net) 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 N*M 테이블에서 최대공약수를 구해본다. 예를 들어 N = 10, M = 10이라고 한다면.. 1은 곱해봤자 의미없으니까 2부터 테이블에 몇개나 나타나는지 한번 찾아보면 5*5 = 25개 있다는 것을 알 수 있는데 이는 행과 열에서 2의 배수가 몇개나 있는지를 세면 된다는 것을 볼 수 있다. 길..
1. 문제 28069번: 김밥천국의 계단 (acmicpc.net) 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 2. 풀이1 그냥 보면 두가지 행동중 하나를 할 수 있는 전형적인 BFS문제 1) 한칸을 올라간다 2) $\left \lfloor \frac{i}{2} \right \rfloor$만큼 올라간다 0번부터 시작한다고 명시되어 있으니 BFS처럼 풀어보면.. 정확히 K번 행동해야하면서 매 행동마다 queue의 길이만큼 순회시키는데 해당 좌표 i가 i+1과 i+i//2를 이동할 수 있으면 queue에 넣어주고.. K번 행동한 후에 n이 queue에 ..
1. 문제 25214번: 크림 파스타 (acmicpc.net) 25214번: 크림 파스타 각 \(A_i\)가 추가된 직후의 문제의 답 \(N\)개를 공백으로 구분하여 출력한다. www.acmicpc.net 2. 풀이 그냥 단순하게 생각해서 배열 원소의 최댓값과 최솟값을 기억해두고, n개의 원소를 처음부터 순회해서, A[i]가 최대인지 검사하고 최대라면 최댓값을 갱신한다음에, dp[i]에 최댓값 - 최솟값을 넣어주면 되는거 아녀? 새로 들어온 값이 최댓값이 아니라면, dp[i]는 이전에 구한 dp[i-1]과 같을거고 최댓값이 아닌 경우에 당연히 A[i]가 최솟값이 될 자격이 있으니까 A[i]가 최솟값인지 검사하고 A[i]가 최솟값이라면 최솟값을 갱신해준다 여기서 $i \leq j$인 i,j에 대하여 A[j..
1. 문제 11414번: LCM (acmicpc.net) 11414번: LCM 두 자연수 A, B가 주어졌을 때, A + N과 B + N의 최소공배수가 최소가 되는 자연수 N을 구하시오. www.acmicpc.net 2. 풀이 임의의 정수 k에 대하여 $$gcd(a,b) = gcd(a+kb,b)$$를 이용하자. 그러면, $$gcd(a+n, b+n) = gcd(a-b, b+n) = gcd(a+n, b-a)$$를 얻는다. 그래서 a < b이면, $a+n \leq gcd(a+n,b+n) \leq b-a$ 최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면... (gcd(a,b) = gcd(abs(a),abs(b))이기 때문) b+n이 b-a의 배수라는..
1. 문제 15897번: 잘못 구현한 에라토스테네스의 체 (acmicpc.net) 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 2. 풀이 다음에서 6번줄이 몇번이나 실행되는지 구하는 문제 int n; cin >> n; int* sieve = new int[n+1]; for (int i = 1; i
1. 문제 2247번: 실질적 약수 (acmicpc.net) 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1부터 n까지 각각 약수들 중 1과 자기 자신을 제외한 약수들의 합들의 누적합을 구하는 문제 2. 방법1 가장 쉬운 방법은 1부터 n까지 순회해서 각 자연수를 i라고 한 다음, i에 대한 모든 약수를 구해서 1과 자기 자신을 제외하고 더하면 된다 약수는 $O(\sqrt{n})$ 알고리즘으로 모두 나눠보는 방식으로 구한다 그런데 p = 1부터 시작하면, i를 1로 나누면 1과 i를 더하게 되는데 실질적 약수라면 1과 i를 제외한 나머지들의 합을 구해야하니 p = 2부터 시작하는게 핵심 n = int(input()) ans..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
