반응형 수학35 [C/C++] 백준 #1929 소수 구하기(에라토스테네스의 체) 주어진 범위안의 숫자에 대해서 소수를 출력하라는 문제입니다. 사실 소수 구하기는 여러가지 방법이 있지만, 에라토스테네스의 체를 사용하는 것이 가장 빠른 편입니다. 에라토스테네스의 체를 사용하는 데 있어서 단점은 처음부터 해야한다는 것입니다. 특히 2의 배수의 개수는 많으므로, 보다 효율적인 형태를 만들려면, m이 2보다 작거나 같고, n이 2보다 크거나 같으면, 2는 무조건 출력하고, 홀수에 대해서만 처리하는 방법입니다. 그렇게 하면 전체적으로 \(\frac{1}{4}\)로 줄일 수 있습니다. 또한 메모리 문제입니다. 메모리 제한이 작으면, 에라토스테네스의 체를 비트필드 형태로 하든지 아니면, \(n \sqrt{n}\) 알고리즘으로 만들어야 합니다. 이 문제 자체가 Silver III 등급정도의 문제로 .. 2022. 11. 11. [C/C++] 백준 #1913 달팽이(수학) 이번 문제는 C언어를 배우다보면 자주 나오는 달팽이 수열을 적는 것입니다. 일반적으로 왼쪽 위가 1의 자리이지만, 이번 수열은 가운데가 1의 자리입니다. 그래서 N은 홀수로 제한됩니다. 그냥 가운데부터 시작해서 차례차례 적어도 되고요. 숫자를 감소시키면서 거꾸로 적어나가도 됩니다. 저는 계산에 의해서 수열을 적었습니다. 굳이 이럴 이유는 하나도 없습니다. 성능상 이슈가 있는 것도 아니니까요. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------ // baekjoon #1913 // - by Aubrey Choi // - created at 2019-07-22 //-----------------------------.. 2022. 11. 3. [C/C++] 백준 #1850 최대공약수(수학) 이번문제는 문제를 살짝 꼬았지만, 결국 최대 공약수를 구하는 문제입니다. 유클리드 호제법을 이해하고 있다면, 이 문제를 쉽게 풀 수 있습니다. 유클리드 호제법에서 큰수에서 작은수로 나눈 나머지를 가지고 우리는 최대 공약수를 구할 수 있습니다. \[ g = gcd(a, b) = gcd(a-b, b) \] 형태가 성립하기 때문이죠. 위식에서는 뺄셈을 했지만, 나눈 나머지를 해도 됩니다. a 개의 연속된 1이 있는 숫자와 b개의 연속된 1이 있는 숫자 역시 마찬가지죠. \(a \gt b\)라고 한다면, a개의 연속된 1이 있는 숫자를 b개의 연속된 1이 있는 숫자로 나눈 나머지는 a를 b로 나눈 나머지의 개수만큼 1이 연속된 수가 됩니다. 예를 들어서 5개의 1이 연속된 11111 과 3개의 1이 연속된 11.. 2022. 10. 25. [C/C++] 백준 #1812 사탕(수학) 이번 문제는 N명의 학생들이 있는데, 학생들이 원형으로 둘러 앉아있습니다. 각 학생들은 사탕을 가지고 있는데, 우리가 알고 있는 것은 이웃한 두 학생들의 사탕의 합만을 알고 있습니다. 이 때, N명은 홀수라는 것이 중요합니다. 이 문제는 N이 홀수가 아니라면 풀기 어려운 문제가 됩니다. 각 학생들이 가지고 있는 사탕의 개수를 \(c_i\)라고 하자, 그리고 \(c_i + c_{i+1}\)을 \(s_i\)라고 하자. 참고로 \(c_{N+1} = c_1\)로 규정하도록 한다. 그러면 다음과 같은 식을 만들 수 있다. \[ \sum_{i=1}^{N} (-1)^{i+1} s_i = 2c_1 \] 만약 짝수의 학생들이 있었다면, 위식은 0이 된다. 예를 들어서 5명의 학생이 사탕을 2, 3, 1, 4, 3개씩 가.. 2022. 10. 23. [C/C++] 백준 #1790 수 이어쓰기 2(수학) 수를 그냥 있는 그대로 이어쓰기를 하면 자릿수가 늘어나면서 수 하나당 2개, 3개씩 숫자가 쓰여질겁니다. 이것만 체계적으로 잘 정리하면 풀 수 있는 문제입니다. 한자리 숫자의 개수는 9개, 두자리 숫자의 개수는 90개, 세자리 숫자의 개수는 900개로 k개의 자릿수의 숫자는 \(9 \times 10^{k-1}\)로 표현할 수 있습니다. 이것만 알면 손쉽게 문제를 풀 수 있습니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------ // baekjoon #1790 - Making number with serial numbers 2 // - by Aubrey Choi // - created at 2019-.. 2022. 10. 22. [C/C++] 백준 #1789 수열의 합(수학) 서로 다른 수들로 이루어진 수열의 합을 원하는 값으로 맞추는 방법은 아주 다양하게 있을겁니다. 그런데, 참여하는 수의 갯수를 최대한으로 하기 위해서는 참여하는 수가 작을 수록 좋겠죠. 이 문제를 풀기 위해서는 바로 이 방법을 사용했습니다. \[ N(N+1)/2 \le S \] 위의 식을 만족하는 최대의 N을 구하면 되겠죠. 근의 공식을 이용하면 쉽게 N의 범위를 구할 수 있습니다. \[ N \le \frac{1 + \sqrt{1+8S}}{2} \] 오른쪽항은 정수일수도 아닐 수도 있지만, N은 정수여야 하므로, 오른쪽항의 값의 정수값을 구하면 됩니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //--------------------------------------------------.. 2022. 10. 22. 이전 1 2 3 4 5 6 다음 728x90
