본문 바로가기

(임시휴재) Fanta's Post

16. 2^1000의 각 자리의 합은? 215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 21000? 215 = 32768 이고 각 자리의 합은 3 + 2 + 7 + 6 + 8 = 26 이다. 21000의 각 자리 합은 몇인가? 배열 하나에 한자리수를 저장해서 긴 자리수를 계산합니다. #include #include #define SIZE 302 void add(int *a, int *b) { int i,j; for(i=SIZE-1; i>=0; i--) { a[i]+=b[i]; for(j=i; a[j]>=10; j--) { a[j-1]+=a[j]/10; a[j]-=a[j]/10*10; } } } vo.. 더보기
15. 20X20그리드의 좌상단에서 출발할 때 우하단으로 가는 길의 개수는? Starting in the top left corner of a 2X2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20X20 grid? 2X2그리드의 좌상단에서 우하단으로 가는 길은 6개가 있다. 20X20그리드에선 몇개의 길이 있는가 파스칼의 삼각형을 이용해 풉니다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 1C0 1C1 2C0 2C1 2C2 3C0 3C1 3C2 3C3 4C0 4C1 4C2 4C3 4C3 5C0 5C1 5C2 5C3 5C4 5C5 nXn그리드에서 길의 개수는 2nCn 입니다. #incl.. 더보기
14. 3n+1 The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is though.. 더보기
13. 100개의 50자리 수의 합에서 앞의 10자리 출력 이 숫자들의 합에서 앞의 10자리를 출력 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 442742289174325203.. 더보기
12. 500개 이상의 약수를 가진 트라이앵글 숫자는 무엇인가 The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28We can see that 28 is the first triangle n.. 더보기
11. 20X20그리드에서 인접한 4개의 수로 만들수 있는 가장 큰 곱이 뭘까? In the 20X20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 9.. 더보기
10. 200만 미만의 소수의 합을 구해 The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. 10미만의 소수들의 합은 2 + 3 + 5 + 7 = 17이다. 200만 미만의 소수들의 합을 구하여라. 짝수인 소수는 2밖에 없으니 sum=2로 초기화 해주고 홀수만 확인합니다. is_prime함수도 홀수만 확인하니 i=3부터 나머지를 확인합니다. #include #include int is_prime(int a) { int i, sqrn=(int)sqrt(a); for(i=3; i 더보기
9. a+b+c=1000 을 만족하는 피타고라스의 수를 찾아라 A Pythagorean triplet is a set of three natural numbers, a b c, for which, a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc. Pythagorean triplet은 세개의 자연수 a < b < c가 a2 + b2 = c2이 성립하는 것이다. 예를들어, 32 + 42 = 9 + 16 = 25 = 52와 같다. a + b + c = 1000. 조건을 만족하는 Pythagorean triplet를 찾고, 그것들의 곱 abc를 구하여라. a,.. 더보기
4. 두개의 3자리 수의 곱으로 만들 수 있는 가장 큰 palindrome을 찾아 A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99. Find the largest palindrome made from the product of two 3-digit numbers. palindromic 숫자는 양쪽 어느 방향으로 읽어도 동일하다. 2자릿수에서 만들 수 있는 가장 큰 palindrome은 9009 = 91 * 99 3자릿수에서 만들 수 있는 가장 큰 palindrome을 찾아 세자리 숫자는 전부 다 곱해보면서 최대값을 찾습니다. #include #include int check(int n) { char.. 더보기
8. 1000개의 숫자안에서 다섯 숫자의 곱중 가장 큰 수를 찾아라 Find the greatest product of five consecutive digits in the 1000-digit number. 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 3035890729629.. 더보기
7. 10001번째 소수를 찾아 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number? 첫 여섯개의 소수를 나열하면 2, 3, 5, 7, 11, 13 이다. 우리는 6번째 소수가 13이란 걸 안다. 10001번째 소수를 찾아라 #include #include #include #include int prime[10002]; int is_prime_0(int a)//소수목록으로 확인 { int i; for(i=1; prime[i]; i++) if(a%prime[i]==0) return 0; return 1; } int is_prime_1(int a)//포인.. 더보기
6. 제곱의 합과 합의 제곱의 차이 The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025 Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbe.. 더보기
5. 1부터 20까지의 숫자들로 나누어지는 가장 작은 수가 뭐야?? 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest number that is evenly divisible by all of the numbers from 1 to 20? 2520은 1부터 10까지의 수로 나머지 없이 나누어지는 가장 작은 수다. 1부터 20까지의 숫자들로 나누어지는 가장 작은 수가 뭐야?? 1부터 20까지의 최소공배수를 찾으면 됩니다. 참고 최대공약수와 최소공배수 long long gcd(long long u, long long v) { return (v==0)? u : gcd(v, u%v); } long lo.. 더보기
3. 가장 큰 소인수 찾기 The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? 13195의 소인수는 5, 7, 13, 29다. 600851475143의 가장 큰 소인수는 무엇인가? 소수 판단 알고리즘처럼 600851475143의 제곱근에서 수를 감소하며 소인수인지 확인하면 됩니다. 가장 큰 소인수가 2일 리는 없으니 홀수만 검사합니다. #include #include int is_prime(int n) { int i, sqrn; sqrn = (int)sqrt(n); for (i = 2; i 더보기
2. 4000000 이하의 피보나치 수열 중 짝수들의 합 구하기 Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms in the sequence which do not exceed four million. 피보나치의 새로운 항은 앞의 두 항을 더해 만들어진다. 1과 2로 시작하는 피보나치 수열의 처음 10개의 항: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 4000000(4백만)이하의 피보나치 수열중 .. 더보기
1. 3또는 5의 배수 더하기 If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000. 10미만의 3또는 5의 배수를 찾으면 3, 5, 6, 9가 나온다. 1000미만의 3또는 5의 배수들의 합을 구해. 나머지연산으로 배수인지 확인만 하면 되는 간단한 문제입니다. #include int main() { int i, sum; for(sum=0, i=3; i 더보기
Fanta's 포스팅연기 --------------------------------------------------------------------------------- 사유 : 수학여행으로 몸이 개아작남 연기일자 : 4. 25. 토. ~ 예상 복귀 일자 : 다음주 토요일 쯤? --------------------------------------------------------------------------------- 수학여행이 너무 피곤하네요 잠도 못자고; 라면 먹은 것 빼곤 기억에 남는 것도 없어요; 아직도 소재를 정하지 못해서 헬로월드문제만 풀고있습니다; 좋은 떡밥 투척 부탁드려요; 힘드네요 ㅋㅋㅋ 더보기
제라의 공식으로 요일맞히는 프로그램 제라의 공식은 ((21*a/4)+(5*b/4)+(26*(c+1)/10)+d-1)%7; 외울 필요 없어요 a는 연도의 앞 두자리 b는 연도의 뒤 2자리. c는 월, d는 일. 예를 들어 2007년 07월 07일은 a=20,b=7,c=7,d=7; 참쉽죠? 그리고 하나 더해야될 게 있어요. c(월)가 1이나 2일경우 연도는 -1을하고 1은 13, 2는 14로 바꿔줘야해요 예를들면 2007년 01월 01일은 a=20,b=6,c=13,d=1; 참쉽죠? 위 공식을 사용해 나온 값에 따라 요일을 정합니다. 0=일요일 1=월요일 2=화요일 3=수요일 4=목요일 5=금요일 6=토요일 #include int calc(int y, int m, int d) { int a, b; if(m 더보기
A la russe 곱셈 알고리즘 일반적인 곱셈은 315 x37 -------------------------------- 2205 945 -------------------------------- 11655 315 x 47= (300 + 10 + 5) x 47 = (47 x 300) + (47 x 10) + (47 x 5) = 11655 이렇게 계산합니다. 정수 x 한 자리 정수 더하기 우리 눈엔 편하지만 융통성없는 컴퓨터님은 이런 수행을 하기가 참 힘드시죠. 다른 방법으론 A la russe가 있습니다. 1. 두 개의 정수를 a, b의 위치에 각각 쓴다. a가 홀수이면 b위치의 수를 c 위치에 쓴다. 2. a를 2로 나누고 b에 2를 곱한 수를 각각 다음 a, b위치에 쓴다. 이 때 a를 2로 나눈 값이 홀수이면 b위치의 수를 c위치.. 더보기
이번주는 쉽니다. 황금같은 짝수주 토요일에 새벽에 학교에 불려가서 시험을 보고 오니 랑 사이가 땡기네요. 엉헉. 살려주세요. 더보기
비트연산 활용 모두들 비트연산은 그냥 안배우고 넘어가셨겟죠.(그렇다고 말해줘요) 비트연산은 &, |, ^, ~, 가 있습니다. 식상한 설명 & AND 둘 다 1이면 1 | OR 하나만 1이면 1 ^ XOR 다르면 1 ~ NOT 1이면 0, 0이면 1 RIGHT SHIFT 오른쪽으로 비트이동 비트란 말이 생소하다면. 32비트 정수형 변수라고 불리는 int는 32자리의 2진수로 구성되어있습니다. 4102100 = 11 1110 1001 0111 1101 0100 비트연산은 이진수에대한 숫자놀음과 같습니다. & 원하는 비트만 변경 만약 32비트에서 4번째와 16번째 비트만 1로 만들고 싶을 땐 a=0x10010000 0x는 16진수를 나타내고 0x10010000는 2진수로 0001 0000 0000 0001 0000 000.. 더보기
최대공약수와 최소공배수 최대공약수 (GCD : greatest common divisor) 유클리드의최대공약수 알고리즘 1. 두 개의 정수 u, v를 입력받는다. 2. v가 u보다 크면 값을 교환한다. 3. u에는 u-v의 값을 저장한다. 4. u가 0이면 v가 최대공약수. u가 0이 아니면 2로 돌아간다. 하지만 이 방법은 u와 v의 차가 크면 성능이 떨어지기때문에 다른 방법을 씁니다. 1. 두 개의 정수 u, v를 입력받는다. 2. v가 0이면 u가 최대공약수. 0이 아니면 u에 u%v를 대입하고 u와v의 값을 교환한다. 3. 2로 돌아간다. 함수 int gcd(int u, int v)//최대공약수 { return (v==0)? u : gcd(v, u%v); } 재귀함수로 간단히 구현할 수 있습니다. 삼항연산자를 처음보는 .. 더보기
Bit twiddling Hack : 정수의 부호 계산 정수의 부호 계산 경고 : 오역이 넘쳐날 수도 있어요. int v; // v의 부호를 찾고싶어 int sign; // 결과는 여기에 저장됨. // CHAR_BIT는 1바이트당 비트수를 나타낸다. (일반적으로 8). sign = -(v > (sizeof(int) * CHAR_BIT - 1)); // 또는, 짧은 명령 (근데 이식성은 없음.): sign = v >> (sizeof(int) * CHAR_BIT - 1); 바로 위의 마지막 식은 32비트 정수의 sign = v >> 31의 값을 구한다. 이건 sign .. 더보기
변수의 범위 타입 크기(byte) 범위 char 1 -127 ~ 127 int 4 -2147483647 ~ 2147483647 __int64 8 -9223372036854775807 ~ 9223372036854775807 C언어를 배우면서 이런 표는 다들 보셨을겁니다. 정말로 표에 저것만 나와있다면 던져버리세요. 왜 변수의 범위가 저렇게 정해졌는지 궁금하셨죠? 알고 있어도 궁금하다고 해요. 1바이트는 8비트 입니다. 1비트는 오직 0과 1만 가질 수 있죠. int형 변수는 32(4 X 8)개의 비트로 숫자를 나타냅니다. 이렇게 0000 0000 0000 0000 0000 0000 0000 0000 감이 오나요? 이진수입니다. int형의 최대값인 2147483647는 2진수로 0111 1111 1111 1111 111.. 더보기
시간복잡도 시간복잡도 처리해야하는 데이터의 양(N이나 n으로 표기)에 따라 걸리는 시간 절대적인 시간이 아닌 비례적인 시간을 나타냄. O(f(n))과 같이 표기. 그렇게 믿을만한 건 못됨. 평균적인 경우 일반적 입력데이터에 따라 걸리는 시간 예) 반쯤정렬된 배열에 대한 정렬 최악의 경우 가능한 최악의(오래걸리는) 입력데이터에 따라 걸리는 시간 시간복잡도는 보통 최악의 경우로 나타냅니다. 예) 반대로 정렬된 배열에 대한 정렬 시간복잡도의 예 O(1) 데이터의 크기에 상관없이 일정 시간 안에 실행을 마침 상수시간이라고도 부름 O(n) 데이터의 크기에 비례하는 시간이 걸림 선형시간이라고도 부름 순차검색이 해당됨 O(n2) n2에 비례하는 시간이 걸림 선택정렬이 해당됨 O(log n) 이진검색이 해당됨 O(n log n).. 더보기
포스팅연기 ------------------------------------------------------------------------------------------- 연기 사유 :졸업식으로 인한 주변의 독촉 연기 일자 : 2. 11 월요일 재 연재 일자 : 가능한 빨-_-리 ------------------------------------------------------------------------------------------- 졸업식은 내일인데 오늘부터 난리치기 시작하네요. 더보기
순열과 조합 순열 1.순서를 고려하여 일렬로 배열하는 것 예제) 철수, 영희, 명수를 줄세우는 경우의 수 n개를 배열하는 경우의 수 n! = n x (n-1) x (n-2) x...x 1 2.n개중 r개를 선택하는 순열 예제) 철수, 영희, 명수중 반장 무반장을 뽑는 경우의 수 n개중 r개를 선택하는 경우의 수 n x (n-1) x...x {n-(r-1)} 조합 1.순서를 고려하지 않고 선택하는 것 예제) 철수, 영희, 명수, 명박중 세 명을 골라 굶기는 경우의 수 n개중 r개의 조합을 택하는 개수 같은 경우의 순열의 개수를 r!로 나눈 값 n x (n-1) x...x {n-(r-1)}/r! 알고 있으면 소스코드의 길이를 많이 줄일 수 있습니다. 그나저나 배치고사는 망했지요. 흥덕고등학교는 1등하나마나 공부하긴 글러.. 더보기
퀵소트 알고리즘 구현 퀵정렬에 대한 자세한 설명은 Algorithm #1. Sort algorithm. - 1.4 Quick Sort algorithm. 축값은 가장 오른쪽의 값을 이용합니다.#include #include char str[256]; void print(char *a, int n) { int i, off; for(off=a-str; off>0; off--) { printf(" "); } for(i=0; i 1) { mid=a[n-1]; i=-1;//앞부터 j=n-1;//뒤부터 탐색 while(1)//분할 { while(a[++i] mid);//오른쪽부터 축값보다 작은 값을 찾음 if(i >= j)//분할이 끝나면 종료 break; tm.. 더보기
삼각형 넓이구하기 프로그래밍 - 헤론의 공식 중학교에선 4,5,6의 세 변을 가진 삼각형넓이를 구할 땐 h2 = 42 - (6-x)2 = 52 - x2 16 - (36 - 12x + x2) = 25 - x2 16 - 36 + 12x = 25 x = 15/4 h2 = 52 - x2 h2 = 400/16 - 225/16 = 175/16 h = √175/4 = 5√7/4 넓이 = 6 x 5√7/4 x 1/2 넓이 = 15√7/4 이런 방법을 알려줍니다.. 삼각형을 2개의 직각삼각형으로 나누어서 계산하는 것이죠. 참 싫죠? 헤론의 공식 √{s(s-a)(s-b)(s-c)} s = (a+b+c)/2 s = (4+5+6)/2 = 15/2 넓이 = √{(15/2)x(7/2)x(5/2)x(3/2)} = √(1575/16) = 15√7/4 참 쉽죠? s는 넓이가 아.. 더보기
메모리 패치 치트엔진 튜토리얼 3 값이 0에서 500사이인 것만 아는 데 이 값을 5000으로 바꾸라는 문제입니다. 스캔 타입으론 사이값을 찾아주는 Value between, 0~500의 값을 찾아줍니다. Hit me를 클릭하면 얼마나 감소했는 지 알려줍니다. 얼마나 감소했는 지 알 때는 Decreased value by로 감소된 값을 입력하고 찾아줍니다. 체력값으로 의심되는 값을 5000으로 바꾸어줍니다. Next버튼이 활성화되면 넘어가줍시다. PW는 890124 기억해두세요. ps. 요즘 항문에서 수분함량 90%이상의 물질이 나오면서 하루에 셀 수 없이 화장실을 들락날락합니다. 똥싸다가 살빠진다는 말이 사실이었네요. ㅋㅋㅋ 금방회복해서 제대로된 글 쓰겠습니다 ;;; 더보기

티스토리툴바