약수의 합이 짝수인지 홀수인지 바로 알 수 있을까?(시그마 함수의 성질 + 제곱수의 개수 바로 구하기)

1. 문제 11692번: 시그마 함수 (acmicpc.net) 11692번: 시그마 함수 첫째 줄에 1 ≤ n ≤ m인 모든 n의 σ(n) 중에서 값이 짝수인 것의 개수를 출력한다. www.acmicpc.net 2. 약수의 합의 성질 - 언제 짝수이고 언제 홀수가 될 수 있는가? 정수 n의 모든 양의 약수의 합을 시그마 함수(sigma function)라고 부르는데 일반적인 정의로... $$\sigma_{z}(n) = \sum_{d | n} d^{z}$$ z = 1이면 모든 양의 약수의 합을 나타내고 z = 0이면 n의 약수의 개수를 나타낸다. 편의상 지금부터 서술하는 모든 시그마 함수는 z = 1인 경우이다. https://en.wikipedia.org/wiki/Divisor_function

• format_list_bulleted 정수론
• · 2023. 6. 26.
• textsms

비둘기집 원리(pigeonhole principle) 기본개념 배우기

1. 비둘기집 원리(pigeonhole principle) "n+1개의 물건을 n개의 상자에 넣을때, 최소한 한 상자에는 적어도 2개 이상의 물건이 반드시 들어있다" n+1개의 물건과 n개의 상자가 있으며, 각 상자당 한개씩의 물건만 존재한다고 가정한다면, 최대 n개의 물건이 존재할 수 있는데, 물건의 숫자는 n+1개이므로 어느 상자에도 들어가지 못한 물건이 하나 남을 수밖에 없으므로 모순이다. 그러므로 각 상자당 한개씩의 물건만 들어가야한다는 가정은 성립할 수 없으며, 적어도 하나의 상자에는 2개 이상의 물건이 존재한다. 너무나도 당연한 이 사실에 "비둘기집 원리(pigeonhole principle)"이라는 거창한 이름이 붙은 이유는 생각보다 많은 수학적 원리를 증명하기 위해 비둘기집 원리가 사용되며..

• format_list_bulleted 비둘기집 원리
• · 2023. 6. 25.
• textsms

팩토리얼을 계산하지 않고도 소인수분해하는 기본기

1. 문제 15996번: 팩토리얼 나누기 (acmicpc.net) 15996번: 팩토리얼 나누기 음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1) www.acmicpc.net 2. 풀이 n의 범위가 $2^{31} = 2147483648$까지로 이것의 팩토리얼을 계산하면... 상상하기도 힘든 숫자가 나올거는 뻔하니 계산하지 않고 $A^{k}$로 나눠보라는 말일텐데 어떻게 가능할까 예를 들어 생각하면 생각보다 간단한 문제다 5! = 5*4*3*2*1인데 $2^{k}$로 나눈 나머지가 0이 되는 최대의 k는 어떻게 찾을까 만약 k = 0이면 당연히 5!은 ..

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

최대공약수 파헤치기1 - N*M 최대공약수 테이블이 만들어내는 아름다운 패턴

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의 배수가 몇개나 있는지를 세면 된다는 것을 볼 수 있다. 길..

• format_list_bulleted 정수론
• · 2023. 6. 20.
• textsms

다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

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에 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 6. 20.
• textsms

배열에 수가 추가될때마다 원소간 차이의 최댓값 구하기

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..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 6. 18.
• textsms