이누의 개발성장기

소수의 개수 자연수 N을 입력하면 1~N까지의 수 중 소수를 찾아 출력해준다. 예를 들어, 20이 입력되면 2, 3, 5, 7, 11, 13, 17, 19 총 8개의 소수가 출력된다. 시간 제한이 짧다고 가정하고 최대한 효율적인 알고리즘을 생각해보자. 풀이1 #include int a[200001]; int main() { //freopen("input.txt", "rt", stdin); int n, i, j, res = 0; scanf("%d", &n); for(i = 1; i

가장 많이 사용된 자릿수뒤집은 숫자의 소수 여부 판단 N을 입력받고 N개의 자연수를 입력받는다. 자연수를 뒤집고 소수 여부를 판단하여, 소수일 경우 출력한다. 예를 들어, 910을 뒤집으면 19로 바꾸어 판단해야 한다. 예를 들어, 5을 입력하고 32 55 62 3700 250을 입력하면 23과 73이 출력된다. 풀이 #include int reverse(int x) { int res=0, tmp; while(x > 0) { tmp = x % 10; res = res * 10 + tmp; x = x / 10; } return res; } bool isPrime(int x) { int i; if (x == 1) { return false; } for(i=2; i

가장 많이 사용된 자릿수 N자리의 자연수가 입력되면 해당 자연수에서 가장 많이 사용된 자릿수를 출력한다. 답이 여러개일 경우 가장 큰 수를 출력한다. 예를 들어 1230565625라는 자연수가 입력되면 5가 3번 사용되어 가장 많이 사용된 자릿수이므로 5가 출력된다. 풀이 #include int ch[10]; int main() { freopen("input.txt", "rt", stdin); int i, digit, max = -2147000000, res; char a[101]; scanf("%s", &a); for (i=0;a[i]!='\0';i++) { digit = a[i] - 48; ch[digit]++; } for(i=0;i= max) { max = ch[i]; res = i; } } pri..

숫자의 총 개수 특정 숫자 n을 받아서 1~n까지 숫자가 총 몇개 쓰였는지 출력한다. 예를 들어, 15를 입력할 경우 1부터 15까지 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였으므로 21이 출력된다. 풀이 (단순 접근) #include int main() { //freopen("input.txt", "rt", stdin); int n, i, j, sum = 0; scanf("%d", &n); for(i=1;i 0;j = j/10) { sum++; } } printf("%d",sum); return 0; } - 가장 간단하게 위와 같은 코드를 작성할 수 있다. - 단, 해당 코드는 효율이 좋지 못하여 매우 큰 숫자가 ..

자릿수의 합 비교하기 자연수 n을 받고, n개의 자연수를 받는다. 각 자연수의 각 자릿수를 모두 더한 값(자릿수의 합)을 비교하여 그 값이 가장 큰 자연수를 출력한다. 자릿수의 합이 같을 경우 더 큰 수를 출력한다. 예를들어 5를 n으로 입력하고, 125 15232 79 1325 97를 입력하면 97이 출력된다. 풀이 #include int digit_sum(int x) { int tmp,sum = 0; while (x>0) { tmp = x % 10; sum += tmp; x = x / 10; } return sum; } int main() { //freopen("input.txt", "rt", stdin); int n, num, i, sum, max=-2147000000, res; scanf("%d"..

N까지의 약수 갯수 모두 구하기 N을 입력받고 1~N까지의 약수를 하나씩 출력한다. 예를 들어, 8을 입력하면 1의 약수 개수 ~ 8의 약수 개수를 하나씩 출력하여, 1 2 2 3 2 4 2 4 와 같이 출력된다. 풀이 (단순 접근) #include int main() { //freopen("input.txt", "rt", stdin); int n, i, j, num = 0; scanf("%d", &n); for(i=1; i

영어단어 복구 알고리즘 특정 단어를 대소문자 구문없이 중간중간 공백을 포함하여 한줄로 입력하면, 그를 소문자의 이어진 문자로 복구해주는 알고리즘이다. 예를 들어, 'bE au T I fu L'과 같이 입력하면 이를 'beautiful'로 바꾸어 출력해준다. 풀이 #include int main(){ //freopen("input.txt", "rt", stdin); char a[101], b[101]; int i, p=0; gets(a); for(i=0; a[i]!='\0'; i++){ if(a[i]!=' '){ if(a[i]>=65 && a[i]