정수론 검색 결과

해당 글 2건
백준 11691 lcm(i,j) : lcm과 gcd의 관계를 이용한 역발상이 필요하다.

오늘은 2019년 마지막 날이니, 마지막 날을 장식할 만한 포스트를 작성하도록 하겠습니다. 아래 수식의 결과 값을 10억 7로 나눈 나머지는 얼마일까요? 단, n은 2이상, 10^6 이하 자연수입니다. n = 10^6이면 대충 O(n)이나, O(128n)에 돌려도 무난할 복잡도입니다. 이것이 생각보다 꽤 큰 힌트 중 하나입니다. 먼저, 최대 공약수에 대한 관점을 비틀어 봅시다. a와 b의 최대 공약수가 g였다고 해 봅시다. 이걸 P라고 합시다. 그러면 위 수식이 성립합니다. 그런데 정말 그럴까요? 위 수식을 Q라고 해 봅시다. 만약에, gcd(a/g,b/g)의 값이 c이고, 이 값이 1이 아니라면, gcd(a,b)의 값은 gc가 됩니다. c가 1이 아니므로, gc의 값은 g가 아닙니다. 즉, not Q이..
자료알고/알고리즘 2019. 12. 31. 21:57
부동 소수점 : 왜 0.1을 저장하면 오차가 생길까요?

부동 소수점은, 가수부와 지수부로 나누어서 저장을 합니다. 즉, (a)*2^b꼴로 저장을 하는데요. 이 때, a는 1보다 크거나 같고, 2보다 작은 실수입니다. 즉, (1.xxx)*2^b 꼴로 저장을 한다는 겁니다. 여기까지는 그리 어렵지 않을 것이라고 생각합니다. 보통 부동 소수점, 우리가 흔히 알고 있는 float이나 double형은 이런 식으로 저장이 됩니다. 지수부랑, fraction. 즉 가수부랑 나누어서 저장을 하고 있는데요. 이 fraction 부분은 (1.xxx)*2^b로 표현했을 때, 0.xxx 부분을 저장한다고 보시면 됩니다. 0.xxx를 2진수로 표현해서 저장할 겁니다. 그러면, 실제로 0.1이 어떻게 저장되는지 봅시다. 저는 먼저 double과 long long이 같은 메모리 공간을..
코딩/C 2019. 6. 29. 19:50