반응형 mathematics12 [C/C++] 백준 #2247 실질적 약수(수학) #2247 문제는 주어진 범위안의 1과 자기자신을 제외한 약수들의 합을 계산하는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2247 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 수학에서 약수와 배수는 밀접한 상관관계가 있습니다. \(2 \times 5 = 10 \)이란 식에서 2와 5는 10의 약수이기도 하지만, 10은 2의 배수이고, 10은 5의 배수이기도 합니다. 이 문제는 위의 원리를 잘 이해하는데에서 출발합니다. 문제는 주어진 N에 대해서 1부터 N까지 1과 자기자신을 제외한 약수들의 총 합을 구하라는 문제입니다. 일일이 하나씩 해보면, 1과 소수는 조건에 맞는(실질적).. 2023. 4. 18. [Python] 프로젝트오일러 #80 제곱근 확장(수학) 이번 문제는 난이도 20%입니다. 사실 이 문제의 뜻을 정확하게 파악하는데 좀 문제가 있습니다. 영어권 사용자들에게도 헷갈리는 문제이기도 하죠. https://projecteuler.net/problem=80 일단 중요한 것은 이 문제를 풀기 위해서는 큰 정수 계산을 할 수 있거나, 높은 정밀도의 실수 연산이 필요합니다. 이미 알고있는 32비트 실수형이나 64비트 실수형은 정밀도가 그렇게 높지 않습니다. 32비트 실수형은 유효자리수가 6자리정도이고, 64비트 실수형은 유효자리수가 15자리 정도입니다. 그런데 이 프로그램은 100자리 이상의 유효자리수를 요구합니다. 일단 문제를 해석하면, \(\sqrt{2}\)와 같은 자연수의 제곱근은 무한소수로 표현됩니다. \( \sqrt{2} = 1.4142135623.. 2022. 9. 13. #78 코인 나누기(Dynamic Programming) 코인 나누기는 유명한 문제 중 하나입니다. 동적 프로그래밍을 이용해서 구할 수 있는데, 그것을 하기 위해서는 수학적 기반 지식이 있어야 합니다. 코인 나누기라는 것은 N개의 코인을 가지고 코인 갯수를 나누는 방법의 수를 구하는 것입니다. 또는 무한정의 1$, 2$, 3$, .., N$ 코인으로 N$를 만드는 방법의 수라고 할 수도 있습니다. 예를 들어서 코인이 5개 있다면, 아래의 그림과 같이 7가지 방법으로 나눌 수 있습니다. 문제에서 요구하는 것은 이 경우의 수가 1,000,000으로 나누어 떨어지는 가장 적은 수를 구하라는 문제입니다. 단순하게 N에 대해서 경우의 수를 구하는 문제였다면 크게 어렵지 않았을겁니다. 난이도가 30%로 설정된 이유도 아마 비슷할 것이라고 봅니다. 수학적으로 본다면 다음과.. 2020. 1. 27. [C/C++] 프로젝트 오일러 #72 분수 세기(수학) 이번 문제는 분수를 세는 문제입니다. 해당 문제는 아래 링크입니다. https://projecteuler.net/problem=72 Problem 72 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 이 문제는 분모의 범위가 정해졌을 때, 기약분수로 표현할 수 있는 분수는 총 몇개인가에 대한 문제입니다. 모든 경우를 다 따져서 기약분수로 만들어서 겹치는 것 제외하면 되겠다고 생각할 수 있지만, 이것이 생각처럼 쉽지 않습니다. \(d \leq 8\)인 분모 d를 갖는 기약분수는 다음과 같습니다. 1/8 3/8 5/8 7/8 1/7 2/7 3/7 4/7 5/7 6/7 1/6.. 2019. 12. 20. [C/C++] 프로젝트 오일러 #508 : \(i-1\) 진법 표시하기(수학) 이번 문제는 아직까지도 푼 사람이 100명이 넘지 않는 문제네요. 그만큼 복잡할 수 있는 문제이므로, 블로그에 자세한 풀이법을 적기는 힘드네요. 문제는 주어진 범위안의 복소수를 \(i-1\) 진법으로 표현했을 때, 1의 갯수의 총 합입니다. 복소수에 보면, 정수가 계수인 복소수들이 자연수의 소수처럼 취급될 수 있는 것들이 있습니다. 이것들을 일반적으로 가우스 소수라고 합니다. 가우스 소수는 몇가지 법칙이 있는데요. 기본적으로 자연수의 소수에서 갈라지게 됩니다. 자연수의 소수 중 \(4k+3\) 형태의 소수는 자체로 가우스 소수가 됩니다. 즉, 3, 7, 11, 19, .. 등입니다. 그 외의 자연수 소수들은 모두 복소수 형태의 가우스 소수로 나누어지게 됩니다. 예를 들어서 소수 2는 \( \pm 1 \p.. 2015. 5. 2. [C/C++] 프로젝트 오일러 #5 : 1~20으로 나누어지는 가장 작은 자연수(수학) 문제의 난이도가 조금씩 높아져 가는 것을 느끼네요. 이번 문제는 효율성을 충분하게 발휘할 수 있는 문제입니다. 가장 쉬운 알고리즘으로는, 1부터 차례대로 모든 수에 대해서 1부터 20까지의 숫자로 나누어 떨어지는 첫번째 수를 찾으면 쉽게 해결이 되겠지만, 그렇게 되면 너무 많은 수에 대해서 검사를 해야 합니다. 여기서는 유클리드 방법에 의해서 최대 공약수를 찾고, 그 수를 가지고 곱을 해내가는 방식으로 알고리즘을 생각했습니다. 유클리드 방법에 의해서 최대공약수를 찾는 것은, 두 수중 작은 수 N에 대하여 O(log N)의 알고리즘으로 찾을 수 있습니다. 그러면 결국 20까지의 숫자를 N으로 표현한다면 O(N log N) 알고리즘으로 답을 찾을 수 있습니다. 가장 쉬운 알고리즘이라고 소개한 경우에는 답을 .. 2014. 12. 22. 이전 1 2 다음 728x90
