본문 바로가기

수학44

[Python] 백준 #1684 같은 나머지(정수론) 이번 문제는 주어진 숫자들에 대해서 나머지가 같은 수가 되는 나눔수 중 최대의 정수를 찾는 것입니다. 나머지가 같다는 것은, 숫자들의 차이에 대한 최대공약수를 구하는 것과 같습니다. \[ Find~ maximum~ such~ D~ that~ \forall i ~ a_i ~mod ~D = k \Longleftrightarrow gcd( a_i - min(a) ) \] 음수를 피하기 위해서 주어진 수 중에 가장 작은 수를 찾습니다. 그리고 나머지 수 중에 가장 작은 수와 같은 경우를 제외하고, 그 차이를 기록합니다. 마지막으로 그 차이들의 수열의 최대 공약수를 구합니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. """ baekjoon #1684 - by Aubrey Choi - creat.. 2022. 9. 29.
[C/C++] 백준 #1676 팩토리얼 0의 개수(수학) 이번 문제는 팩토리얼을 계산했을 때, 뒤에서부터 연속된 0의 개수를 세는 것입니다. 팩토리얼은 1부터 n까지의 곱을 계산한 것인데요. 20 팩토리얼만 해도 2,432,902,008,176,640,000 값이 나와서 정수 계산으로는 힘듭니다. 물론 64비트 정수형을 사용하면 조금 더 계산할 수는 있습니다. 그런데 문제는 500까지의 숫자 범위를 가지고 있습니다. 500 팩토리얼은 \( 1.2 \times 10^{1134} \) 의 숫자로 굉장히 큰 숫자가 나오며, 파이썬이나 C#과 같이 기본적으로 Big Integer가 제공되는 언어가 아니라면, 실제 팩토리얼을 계산하기 힘듭니다. n 팩토리얼 계산은 \(O(n)\) 알고리즘이라고 할 수 있지만, Big Integer 곱셈이 기본 연산이 아닌 관계로 더 오.. 2022. 9. 28.
[C/C++] 백준 #1541 잃어버린 괄호(탐욕 알고리즘) 이번 문제는 생각만 간단하게 하면 됩니다. 문제를 풀 때, 어떻게 하면 간단하게 풀 수 있는지 생각하게 해주는 문제입니다. 아래는 백준 사이트에 있는 문제입니다. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제는 +, - 연산자만 사용된 수식에서 괄호를 적당하게 넣어 수식의 값을 최소로 만드는 것이다. 이 문제에서는 - 기호가 있느냐가 핵심입니다. 괄호를 마음껏 칠 수 있기 때문에, +로만 이루어진 수식은 괄호가 아무런 의미가 없.. 2022. 9. 2.
#1492 합 이번 문제는 Platinum II로 꽤 높게 책정된 문제입니다. 문제 자체는 상당히 쉽습니다. 1부터 n까지 \(n^k\)의 합을 구하라는 문제입니다. 여기서는 파스칼의 삼각형과 연관된 이항계수에 대해서 먼저 알고 있어야 합니다. 이항 계수는 n개에서 r개를 고르는 경우의 수를 나타내는 것으로 \( _nC_r \)로 표현됩니다. 이항 계수를 바로 구할 수도 있겠지만, 저는 프로그램에서는 파스칼의 삼각형을 이용했습니다. n이 최대 51까지밖에 안 되기되문에 크게 문제가 없습니다. 더 크다면 이항 계수를 구하기 위해서는 별도의 방법을 이용해야 합니다. 다음 코드는 파스칼 삼각형을 이용해서 주어진 n에 대해서 이항계수를 구하는 것입니다. 사실 그냥 for 루프를 이용해서 작성할 수 있겠지만, 여기서는 동적 계.. 2022. 8. 21.
#1476 날짜 계산 이번 문제는 난이도는 Silver V로 쉬운 편입니다. 수학적 지식을 가지고 있다면 손쉽게 풀 수 있습니다. E, S, M 이란 단위가 1부터 시작해서 각각 15, 28, 19 의 범위를 가지는데, 모두 같이 증가하기 시작해서 16이 되면 E의 값은 1이 됩니다. 즉 다음과 같이 움직이게 되죠. 1 1 1 -> 2 2 2 -> 3 3 3 -> ... -> 15 15 15 -> 1 16 16 -> 2 17 17 -> ... -> 4 19 19 -> 5 20 1 -> ... 우리가 얻고자 하는 숫자가 x년도라면, E, S, M은 다음과 같이 표현할 수 있습니다. \[ ( (x-1)~ mod~ 15 + 1, (x-1)~ mod~ 28 + 1, (x-1)~ mod~ 19 + 1 ) \] 15, 28, 19 는 .. 2022. 8. 19.
#1457 정확해 정확해라는 문제는 약수들의 합을 구하는 문제입니다. 난이도는 Gold I 문제이긴 하지만, 이게 수학적인 이해를 하지 못 하면 조금 어렵습니다. 그래서인지 정답자가 제가 푼 시점에서는 40명에 그칩니다. 약수의 개수를 구하는 문제는 꽤 어렵습니다. \[ \sigma_0(n) = n( \lbrace x | n~ mod~ x = 0 \rbrace ) \] 으로 약수를 구하는 식을 사용한다면, \(\sqrt{n}\)에 해당하는 만큼 약수가 되는 개수를 구하던지, 소인수 분해를 해주어야 합니다. 그런데 만약 1 부터 n까지의 약수들의 개수의 합을 구하라는 문제라면 어떨까요? \[ S(n) = \sum_{k=1}^{n} \sigma_0(k) \] 하나의 수의 약수의 개수를 구하는 것도 어려운데, 일정 숫자 범위의.. 2022. 8. 16.

티스토리툴바