수학44 #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. [C/C++] 백준 #1011 Fly me to the Alpha Centauri 이번 문제는 알파 센타우리까지 우주선을 타고 갈 때, 워프기계는 최소 몇번 작동으로 갈 수 있는지 구하는 문제입니다.우주적인 문제이지만, 사실상 거리의 절반까지 가는데, 1+2+3+...+k 의 값이 거리의 절반보다 작으면서 가장 큰 수가 되는 것을 구하는 문제입니다. 알파 센타우리는 지구로부터 4.37 광년정도 떨어져 있습니다. 우주선이 빛의 속도로 가도 4.37년이 걸리는 곳입니다.태양과는 주계열성으로는 가장 가까운 별이라서 지구에서 관측할 때 아주 밝게 빛나는 별입니다만, 아쉽게도 우리나라가 있는 위도상에서는 관측이 힘듭니다. 영화에서도 새로운 지구로 자주 쓰이는 별입니다. 영화 패신저스에서도 알파 센타우리가 쓰였죠. 가는데 백여년이 걸려서 사람을 동면시켜서 갑니다. (사실상 그곳까지 가는.. 2019. 12. 22. [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++] 백준 #1002 터렛(수학) 이 문제 는 백준 사이트에 가입하고 처음 풀었던 것 같습니다. 지식인에서 백준 알고리즘 문제를 물어보았는데, 답변을 달기 위해서 백준 알고리즘에 가입했고, 그 후 몇문제를 풀었던 기억이 납니다. 당시에는 연세대를 다닐때였으니까, 연세대로 등록을 했었는데, 벌써 몇년 전 일이네요. 꽤 오래전부터 프로젝트 오일러 사이트에 익숙했었던 탓에, 백준과 같이 실제 채점서버가 있는 사이트는 거의 안 했었는데, 최근에 다시 시작했습니다. 이 문제의 정답 비율은 19%로 상당히 낮은데, 사실 문제의 난이도보다는 문제의 설명이 알아듣기 힘들어서인 듯 하다. 문제를 푼 사람들이 설정한 문제의 난이도는 Silver IV입니다. . 문제의 링크입니다. https://www.acmicpc.net/problem/1002 1002번.. 2019. 12. 16. [C/C++] 프로젝트 오일러 #508 : \(i-1\) 진법 표시하기(수학) 이번 문제는 아직까지도 푼 사람이 100명이 넘지 않는 문제네요. 그만큼 복잡할 수 있는 문제이므로, 블로그에 자세한 풀이법을 적기는 힘드네요. 문제는 주어진 범위안의 복소수를 \(i-1\) 진법으로 표현했을 때, 1의 갯수의 총 합입니다. 복소수에 보면, 정수가 계수인 복소수들이 자연수의 소수처럼 취급될 수 있는 것들이 있습니다. 이것들을 일반적으로 가우스 소수라고 합니다. 가우스 소수는 몇가지 법칙이 있는데요. 기본적으로 자연수의 소수에서 갈라지게 됩니다. 자연수의 소수 중 \(4k+3\) 형태의 소수는 자체로 가우스 소수가 됩니다. 즉, 3, 7, 11, 19, .. 등입니다. 그 외의 자연수 소수들은 모두 복소수 형태의 가우스 소수로 나누어지게 됩니다. 예를 들어서 소수 2는 \( \pm 1 \p.. 2015. 5. 2. [C/C++] 프로젝트 오일러 #28 : 회전하는 숫자들의 대각선 합 이 프로그램은 사실 원하는 배열을 잡고, 숫자를 배열한 후에 대각선의 합을 구해도 됩니다.그렇게 한다고 해서 시간이 엄청 걸리는 것도 아니니 말이죠. 그러나 처음 제가 이 프로젝트 오일러 글들을 쓰면서, 어떻게 하면 보다 빠르게 계산할 것인가를 고민했기 때문에, 이 문제 역시 복잡도를 낮추어 계산하도록 하였습니다. 1부터 N까지의 합, 제곱 합 등의 공식을 도출할 줄 안다면, 이 문제 역시 간단하게 하나의 식으로 만들 수 있습니다. 여기서는 다음과 같은 식이 나오게 됩니다. \[ \text{result} = 1 + \frac{8n(n+1)(2n+1)}{3} + 2n(n+1) + 4n \] 이 수식에 따라서 구한 프로그램은 다음과 같습니다.역시 이 프로그램은 참고용으로만 해주세요.//-----------.. 2015. 3. 4. 이전 1 ··· 4 5 6 7 8 다음
