본문 바로가기

분류 전체보기

 (116)
$1$부터 $N$까지의 합에 $1$부터 $N$까지의 합 붙이기... $\times \infty$ 이게 무슨 의미냐면, 먼저 $1$부터 $N$까지의 합부터 생각해보자. $\sum\limits_{i=1}^{n} i$는 간단하게 $\frac{n(n+1)}{2}$로 쓸 수 있다. 그러면 이 값에 다시 시그마를 붙이면? $\sum\limits_{i=1}^{n} \frac{i(i+1)}{2}$이 된다. 이 값은 무엇일까? 일단은 그냥 식 정리를 해보자. $\frac{1}{2} \sum\limits_{i=1}^{n} (i^{2}+i)$로 바꿔 쓸 수 있고,  $ \sum\limits_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} $이므로 $\frac{1}{2} (\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2})$가 된다.$\frac{n(n+1)(2n+1)}{..
$1$부터 $N$까지의 합은 항상 합성수일까? 한 줄 요약: $N \geq 3$부터 합성수다. $1$부터 $N$까지의 합은 간단하게 $S(N) = \frac{N(N+1)}{2}$로 나타낼 수 있다. 합성수는 소수와 소수의 곱 혹은 소수와 합성수의 곱 혹은 합성수와 합성수의 곱이다. 1. $N$이 $1$이라면 $S(1) = 1$이므로 이는 소수도 아니고 합성수도 아니다.2. $N$이 $2$라면 $S(2) = \frac{2 \times 3}{2} = 1 \times 3$이므로 소수다.3. $N$이 $3$보다 크거나 같다면 $S(N) = \frac{N(N+1)}{2}$에서 $N$은 $3$보다 크거나 같고 $N+1$도 $4$보다 크거나 같다. 이는 둘 중에 하나가 짝수여서 $2$로 나누어떨어진다고 가정했을 때, $N = 2$와 같이 $1$이 되지 않는다. ..
$N$의 양의 약수의 합이 짝수일까? 홀수일까? 한 줄 요약: $N$이 제곱수이거나 제곱수를 $2$로 나눈 값이라면 양의 약수의 합은 홀수고 아니라면 짝수다.($16(4^{2})$, $72(\frac{12^2}{2})$, $\cdots$ 등은 홀수, $19$, $34$, $\cdots$ 등은 짝수) $N$이 주어졌을 때 양의 약수의 합이 무엇이냐고 한다면, 직접 약수를 구해서 합을 더해 줄 수 있다. 그리고 그 값이 홀수인지 짝수인지 판단 해볼수 있다. 그렇다고 이 방식이 컴퓨터로 계산했을 때 $10^{18}$ 스케일 정도까지는 폴라드 로 알고리즘을 사용한다면 엄청 느리거나 하지 않는다. 하지만 우리는 $N$을 이렇게도 나타낼 수도 있다. $N = p_{1}^{q_{1}} p_{2}^{q_{2}} \cdots p_{n}^{q_{n}} $ (단, $p_..
골드 이상 풀이 정리 2주차 1. 숫자 연결하기 (BOJ 1323)pigeonhole principle 언제 한번 순환소수 구할 때 나눗셈을 해본 적이 있다면 좋은 아이디어를 떠올릴 수 있다.1. 수를 계속 추가하면서(순환소수라면 0이었고, 이 문제에서는 N이다.) K로 나눠서 나머지를 알아낸다. 그후 그 나머지+N(여기선 문자열 연산이라 생각)을 다시 합쳐서 K로 나눈다.2. 계속 하다보면 언젠가 반복되었다.즉, 예제를 생각해보면 2%9=2 -> 22%9 -> 42%9 -> 62%9 -> ... 이런 식으로 계속 연산해준다. K로 나눈 나머지는 반드시 0~K-1이므로 비둘기집 원리에 따라 최대 K번 안에 반복된다. 같은 나머지가 나왔는데도 나머지가 0으로 안 나온다면 영원히 못 나누므로 -1을 출력하고 아니면 횟수를 출력하면 된다..
골드 이상 풀이 정리 1주차 1. 동전 (BOJ 9084)dp, knapsack 동전 하나를 잡고 그 동전의 값 이상부터 n까지 이전 값을 불러오면 된다. 당연히 0원은 무조건 만들 수 있으니 1로 초기화 해서 시작하면 된다. 2. 겹치는 선분 (BOJ 1689)sweeping, sorting imos법 같이 돌리면 된다. 즉, 시작 점은 1로 두고, 끝 점은 -1로 둬서 점의 위치를 중심으로 정렬해준다.예를 들어 (1, 5), (3, 6), (2, 3)가 있으면 (1, 1), (2, 1), (3, -1), (3, 1), (5, -1), (6, -1)로 될 것이다. 그리고 좌표 하나하나씩 순서대로 확인해서 변수에 +1, 혹은 -1을 하고 최댓값을 갱신하면 된다. 당연히 -1이 1보다 작으므로 먼저 계산되기 때문에 '선분의 끝 점에서..
[BOJ][Python] 백준 32454번 - Fibonacci Lucky Numbers 문제 링크: https://www.acmicpc.net/problem/32454 문제 풀이피사노 주기, 오일러 피 함수, 분할 정복을 이용한 거듭제곱 일단 $7^{7^{7^n}}$을 먼저 보면 벌써부터 답이 없어지는데, 이 수는 매우 크기 때문에 사실상 직접 구하는 것은 불가능하다. 그래서 접근하기가 힘든데, $7^{7^{7^n}}$번째 피보나치 수를 $10$번째 자리까지 출력하라고 적혀있다. 이 말은 피보나치 수를 구했을 때 $10^{10}$으로 나눈 값만 구하면 된다. 그렇다면 여기서 떠올리는 게 있다면 쭉쭉 풀려질 것이다. 피사노 주기를 이용하면 된다. 피보나치 수에서 나누는 값이 $10^{m} (m > 2)$라면 주기는 $15 \times 10^{m-1}$다. $m = 10$이므로 주기는 $15 ..
[BOJ][Python] 백준 32242번 - $Axy+Bx+Cy+D=0$ 문제 링크: https://www.acmicpc.net/problem/32242문제 풀이폴라드 로, 정수론 처음에는 서브테스크로 나눠서 생각을 해봤는데, $A$가 0이냐 0이 아니냐를 기준으로 나눠서 생각했다. 생각해야할 케이스가 매우 많으므로 천천히 생각해봐야 한다. 1. $A=0$인 경우1-1. $B \neq 0$, $C \neq 0$ 인 경우$Bx+Cy+D=0$의 형태가 되는데 베주 항등식이 떠오를 것이다. 정수 해가 무한히 존재하는 지 혹은 없는지에 대해 알 수 있다.$GCD(B, C) = X$라 하고, 베주 항등식에 따르면 $X$가 $D$의 배수이면 정수인 $x, y$가 무수히 많기 때문에, 이를 판별해서 구하면 된다. 1-2. $B = 0$, $C \neq 0$ 인 경우$Cy+D=0$이 되고,..
랜덤 마라톤 14주차 A. Card Game Contest (백준 14551)조합론 각각의 덱은 독립적이므로 총 방법의 수는 $A_1$부터 $A_N$까지 곱하면 된다. 단, 덱이 없을 수도 있는데, 이때는 스킵하거나 0을 1로 바꾸면 된다. $M$으로 나눈 나머지를 구해야 하므로 곱할 때마다 모듈러 연산을 취해주면 된다.  B. 행사장 대여 (Small) (백준 14732)구현 범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다. C. 체크포인트 달리기 (백준 29891)그리디, 정렬 일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면, $N$이 $K$의 배수라면 거리가 먼 순서부터 체크하던지, 가까운 순서부터  체크하던지 상관없지..

티스토리툴바