나의 개발일지

실버Ⅳ https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 3684 1168 1021 31.464% 문제 오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × ..

브론즈 Ⅲ https://www.acmicpc.net/problem/24266 24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 2063 1481 1432 74.428% 문제 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식..

브론즈 Ⅲ https://www.acmicpc.net/problem/24264 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 3093 1582 1520 52.522% 문제 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식..

브론즈Ⅳ https://www.acmicpc.net/problem/24263 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 2404 1997 1890 83.628% 문제 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으..

브론즈Ⅴ https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 4911 3803 3530 78.936% 문제 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으..

실버Ⅱ https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 82142 33746 25629 39.205% 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론..

브론즈Ⅰ https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 방법 소인수분해란 주어진 숫자를 소수로만 나누어 나타내는 것을 말한다. N을 입력 받고, for문의 i를 2부터 N까지 돌며 N의 가장 작은 소인수를 찾아 출력한 후, N을 그 소인수로 나눈 몫을 N에 대입한다. 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #pragma (disable:4996) #include int main() { int n, i; scanf("%d", &n); while (n > 1) { for (i = 2; i 1) ..

'에라토스테네스의 체' 란? '에라토스테네스의 체'란, 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..