본문 바로가기

수학49

[C/C++] 백준 #1740 거듭제곱(수학) 이번문제는 3진수를 생각하면 됩니다. 단지 0과 1로만 이루어진 3진수가 되는 것이죠. 예를 들어서 5번째로 작은 거듭제곱수는 5가 이진수로 101이므로

101_{(3)} = 3^{2} + 3^{0} = 10

이 됩니다. 마찬가지로 10은

1010_{(2)}

1010_{(3)} = 3^{3} + 3^{1} = 30

이 됩니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------ // baekjoon #1740 // - by Edan // - created at 2019-07-02 //------------------------------------------------ #include // .. 2022. 10. 6.

[C/C++] 백준 #1735 분수 합(수학) 이번 문제는 간단하게 분수의 합을 구하는 식을 알면 풀 수 있습니다. 기약분수라고 한다면, 다음과 같이 표현할 수 있습니다.

\frac{a}{b} = \frac{a / g}{b / g} w h e n g = g c d (a, b)

두 분수의 합은

g = g c d (a, b)

라고 할 때,

\frac{n}{a} + \frac{m}{b} = \frac{n b / g + m a / g}{a b / g}

기본적으로 이것들을 알면 이 문제를 풀 수 있습니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------------------------------ // baekjoon #1735 // - by Aubrey C.. 2022. 10. 6.

[C/C++] 백준 #1722 순열의 순서(수학) 이번 문제는 순열의 순서를 아는 것입니다. 순열 경우의 수는 N이 주어지면,

N!

로 아주 큰 수가 됩니다. 순열의 경우의 수가 팩토리얼이라는 것은 아주 중요합니다. 우리가 10진수를 생각한다면, N자리의 숫자는

10^{N}

개의 경우의 수를 가집니다. 이를 이용하면, 우리가 주어진 수가 몇번째 10진수인지 아주 쉽게 구할 수 있습니다. 팩토리얼로 이루어진 수도 마찬가지라고 생각하면 됩니다. N이 4라면 만들 수 있는 순열 수는 24가지가 됩니다. 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 432.. 2022. 10. 4.

[Python] 백준 #1684 같은 나머지(정수론) 이번 문제는 주어진 숫자들에 대해서 나머지가 같은 수가 되는 나눔수 중 최대의 정수를 찾는 것입니다. 나머지가 같다는 것은, 숫자들의 차이에 대한 최대공약수를 구하는 것과 같습니다.

F i n d m a x i m u m s u c h D t h a t \forall i a_{i} m o d D = k ⟺ g c d (a_{i} - m i n (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.

이전 1 ··· 3 4 5 6 7 8 9 다음

728x90

티스토리툴바