본문 바로가기
반응형

수학35

[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.
#1214 쿨한 물건 구매(정수론) 이번 문제는 정수론을 잘 이해하셔야 풀기 편한 문제입니다. 보통 확장 유클리드 소거법이라는 것을 이용하게 되는데요. 확장 유클리드 소거법은 두개의 수가 주어졌을 때, 유클리드 소거법을 이용해서 최대공약수를 구하는 과정을 거꾸로 하는 것입니다. 예를 들어서 12와 20의 최대공약수를 구하는 과정을 볼께요. \[ 8 = 20 - 12 \] \[ 4 = 12 - 8 \] 로 12와 20의 최대공약수는 4임을 알 수 있습니다. 그리고 이 식을 거꾸로 가게 되면, \[ 4 = 2 \times 12 - 20 \] 을 얻을 수 있죠. 이렇게 최대공약수를 구하는 파라미터터 (2, -1)을 얻는 것이 확장 유클리드 소거법의 목적입니다. 아래의 소스는 확장 유클리드 소거법을 프로그램한 것입니다. void xgcd(long.. 2020. 1. 7.
728x90

티스토리툴바