나의 개발일지

'에라토스테네스의 체' 란? '에라토스테네스의 체'란, 2부터 시작하는 양의 정수들 중에서 소수(prime number)인 것을 찾아내는 알고리즘 중 하나입니다. 이 알고리즘은 2부터 시작하여, 그 다음 소수의 배수를 모두 지워가면서 소수를 찾아내는 방식으로 동작합니다. 먼저, 2부터 n까지의 모든 정수를 배열에 저장합니다. 그리고 배열에서 2를 제외한 2의 배수를 모두 지웁니다. 다음으로, 배열에서 3을 제외한 3의 배수를 모두 지웁니다. 이렇게 배열에서 지워지지 않은 가장 작은 수를 다음 소수로 간주하고, 그 수를 제외한 그 수의 배수를 모두 지웁니다. 이 과정을 반복하여, 배열에서 지워지지 않은 수가 소수가 됩니다. 예를 들어, 2부터 10까지의 소수를 찾는 과정을 살펴보겠습니다. 먼저, 2를 제외..

실버Ⅴ https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 방법 우선 이 문제는 M과 N을 입력받고, M과 N 사이의 수 중 소수를 찾아 그 소수들을 모두 합한 값과, 그 소수 중 가장 작은 값을 각각 출력하는 문제이다. 먼저 나의 경우 N의 값을 입력받으면서 배열의 크기가 최대 N으로 고정되기 때문에 10000의 원소를 갖는 배열을 만드는 방법이 아닌, 동적할당을 이용해 배열을 할당했다. 만약 동적할당의 사용법을 모른다면 동적할당에 관한 글을 아래에 ..

실버Ⅴ https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 방법 *소수는 약수가 1과 자기자신뿐인 자연수이다. 입력받은 각각의 수를 배열에 저장하고, 2중 for문을 이용해 배열에 저장된 수의 약수의 개수가 2개인 경우(1과 자기자신) 소수의 개수를 +1 증가시키면 된다. 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #pragma warning(disable:4996..

C 언어는 아스키 코드를 사용하여 문자와 숫자를 표현합니다. 아스키 코드는 7비트 문자 코드이며, 총 128개의 문자와 기호를 포함합니다. 이 코드는 ASCII(American Standard Code for Information Interchange)라고도 불립니다. 아스키 코드에서는 각 문자와 기호에 대해 고유한 7비트 이진 숫자 값이 할당됩니다. 이 값은 0부터 127까지의 범위에 있습니다. 예를 들어, 대문자 A의 아스키 코드 값은 65이고, 소문자 a의 아스키 코드 값은 97입니다. C 언어에서 아스키 코드를 사용하는 방법은 간단합니다. 문자를 사용하는 대신, 해당 문자의 아스키 코드 값을 변수에 할당하거나 출력하는 등의 작업을 수행할 수 있습니다. 아래는 아스키 코드를 출력하는 예제 코드입니다..

브론즈Ⅰ https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 풀이 방법 n을 입력받고 1부터 n-1까지(자기 자신을 제외한 모든 약수들을 구해야 하므로)의 수 중 n의 약수를 찾기위해 for문을 이용해 i에 1부터 n-1까지 대입한다. 만약 n%i(n을 i로 나눈 나머지)가 0일 경우(i가 n의 약수일 경우) 배열에 그 수를 저장하고 n의 약수의 개수를 셀 cnt를 1 증가시킨다. 또한, n이 완전수인지를 판단해야 되기 때문에 sum에 약수..

C언어에서는 printf와 scanf를 이용한 입출력을 하기 위해서는 그 형태가 정수인지, 실수인지, 문자인지 등을 지정해주어야 한다. 이때 사용되는 것이 서식지정자이며, 보통 '%'로 시작한다. 대표적으로 많이 사용되는 서식지정자는 %d, %f, %s, %c 가 있으며, 각각 정수형, 실수형, 문자열, 문자를 입출력할때 사용된다. c언어에서 사용되는 서식지정자는 다음과 같다. %d: 10진 정수를 출력할 때 사용됩니다. %ld: 10진 long형 정수를 출력할 때 사용됩니다. %lld: 10진 long long형 정수를 출력할 떄 사용됩니다. %u: 10진 unsigned 정수를 출력할 때 사용됩니다. %lu: 10진 long형 unsigned 정수를 출력할 때 사용됩니다. %llu: 10진 long ..

브론즈Ⅰ https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 방법 피보나치 수열은 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다. 즉, 아래의 표처럼 진행된다. 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 8 13 21 34 피보나치 수열은 보통 재귀함수열을 이용해 풀지만, 재귀함수로 풀 경우 시간이 많이 걸린다. 따..

브론즈Ⅲ https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 풀이 방법 약수란 어떤 자연수를 나누어 떨어지게 하는 수이다. 즉 12의 약수는 1, 2, 3, 4, 6, 12이다. N의 약수들 중 K번째로 작은 수를 출력하는 문제이기 때문에 for문을 이용해 N을 1부터 2, 3, 4, ... N까지 나눈 나머지를 확인한 후, 나눈 나머지가 0일 때마다 cnt를 1씩 증가시키며 k번째로 작은 수를 찾아낸다. 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

브론즈Ⅲ https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 풀이 방법 -첫 번째 숫자가 두 번째 숫자의 약수일 경우 두 번째 숫자를 첫 번째 숫자로 나눈 나머지가 0이 될 것이다. -첫 번째 숫자가 두 번째 숫자의 배수일 경우 첫 번째 숫자를 두 번째 숫자로 나눈 나머지가 0이 될 것이다. 위의 두가지 사실을 이용해 문제를 풀 수 있다. 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #pragma ..

브론즈Ⅴ https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 방법 C언어로 표현할 수 있는 최대 정수는 자료형 unsigned long long을 이용한 18,446,744,073,709,551,615(약 10^19) 승이다. 하지만, 이 문제의 경우 A와 B의 최댓값이 10^10000-1이기 때문에 unsigned long long을 사용하기에는 부적절하다. 따라서 컴퓨터 내에서 실제로 덧셈을 하는 것이 아닌, 우리가 덧셈을 하는 과정을 이용해 실제 덧셈을 하는 것처럼 코드를 작성해야한다. 즉, 아래의 예시와 같은 과정을 직접 코드로 구현해 주어야 ..