https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 이 문제는 시간복잡도가 아주 중요한 문제이다. 단순하게 생각하면 금방 풀 수 있지만, 그러면 대다수는 시간복잡도에 걸린다. 내가 처음으로 제출한 코드는 다음과 같다. static void pro() { int deltaX = 1; int deltaY = 1; while (t-- > 0) { if (p == w) deltaX = -1; if (p == 0) deltaX = 1; i..

www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다. 에라토스테네스의 체 1. 2부터 N까지 모든 수를 써 놓는다. 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 3. 그 수는 소수이다. 4. 이제 그 수의 배수를 모두 지운다. 이 문제를 해결하기 위해서는 배열이 필요하다. - 수를 지웠는지 아닌지 기록하는 배열 지움: True 지우지 않음: False import sys input=sys.st..

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수: 약수가 1과 자기 자신밖에 없는 수 소수를 구하는 법에는 크게 두 가지가 있다. 1. 소수의 정의 이용 - N이 소수인지 알아보기 위하여 2 부터 N-1까지 나머지 연산을 해본다. - 시간복잡도 $O(n)$ 2. 약수의 특징 이용 - N의 가장 작은 약수는 2이다. 약수는 $\sqrt{N}$을 기준으로 대칭이다. 2의 대칭인 수는 $2/N$이다. $2/N+1$부터 N-1까지 약수가 없어야 소수 이므로 2부터 $N/2$까지 나누어 떨어지는지 검사한다. - 시간복잡도 $O(n..

www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수(GCD): 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. 최소공배수(LCM): 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다. 최대공약수는 유클리드 호제법을 이용하여 구한다. - a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) = GCD(b, r) 이다. - r이 0이면 그 때 b가 최대 공약수이다. 최소공배수는 GCD를 응요해서 구할 수 있다. - 두 수 a, b의 최대공약수 g라고 했을 때..

17427 약수의 합2 문제와 매우 유사한 문제이다. 문제에서 요구하는 조건은 다음과 같다. - f(A) = A의 약수의 합 - g(N) = f(1) + f(2) + ... + f(N) - N이 주어졌을 때, g(N)을 구하는 문제 - 테스트 케이스의 갯수 약수의 합 2 문제에서 추가된 부분은 마지막 테스트 케이스의 개수이다. 우선 약수의 합 2 문제의 해결과 똑같이 풀면 다음과 같다. import sys input=sys.stdin.readline n = int(input()) for i in range(n): sum_ = 0 a = int(input()) for j in range(1, a+1): sum_ += (a//j)*j print(sum_) 그러나 이 코드는 바로 시간 초과가 뜬다. 그러므로,..

www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net - f(A) = A의 약수의 합 - g(N) = f(1) + f(2) + ... + f(N) - N이 주어졌을 때, g(N)을 구하는 문제 우선, 약수를 구하는 방법에는 두가지가 있다. 1. 자연수 N이 주어졌을 때, 1부터 N까지 나누어가면서 나머지가 0인 값을 구하는 방법 2. 자연수 N이 주어졌을 때, 약수는 서로 대칭구조를 이루고 있으므로 1부터..

www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net N의 진짜 약수 중 가장 작은 수와 큰 수를 곱하면 N이다. import sys input=sys.stdin.readline n=int(input()) # 리스트에 주어진 숫자를 입력 받는다. arr=list(map(int, input().split())) # 리스트에서 가장 큰 수를 구한다. max_=max(arr) # 리스트에서 가장 작은 수를 구한다. min_=min(arr) # 둘을 곱한 값을 출..