백준 알고리즘 BaekJoon Online Judge 1085번 "직사각형에서 탈출" 문제입니다. import sys x, y, w, h = map(int, sys.stdin.readline().split()) print(min((abs(x-w), abs(x), abs(y-h), abs(y)))) 현재 (x, y) 좌표일 때, (0,0)으로 시작해서 (w,h) 좌표로 끝나는 직사각형의 테두리까지 가는 최소 거리를 구하는 문제다. 최소 거리이기 때문에 가로 혹은 세로 직선거리라고 추측할 수 있다. 가로로 따질 경우는 두 가지를 따져야 한다. w-x와 x-0 둘 중 작은 것을 골라야하고 세로로 따질 경우는 h-y와 y-0 둘 중 작은 것을 골라야한다. 결국 w-x, x-0, h-y, y-0 넷 중 가장 작은..

백준 알고리즘 BaekJoon Online Judge 9020번 "골드바흐의 추측" 문제입니다. n=10000 a = [False,False] + [True]*(n-1) primes=[] for i in range(2,n+1): if a[i]: primes.append(i) for j in range(2*i, n+1, i): a[j] = False TC = int(input()) for tc in range(TC): N = int(input()) K = 99999 N1, N2 = 0, 0 for i in range(2, N//2+1): if a[i] and a[N-i]: N1 = i N2 = N-i print(N1, N2) 에라스토테네스의 체를 활용하는 문제다. 그리고 이 문제는 소수리스트를 탐색하는 것..

백준 알고리즘 BaekJoon Online Judge 4948번 "베르트랑 공준" 문제입니다. n=250000 a = [False,False] + [True]*(n-1) primes=[] for i in range(2,n+1): if a[i]: primes.append(i) for j in range(2*i, n+1, i): a[j] = False while True: N = int(input()) if N == 0: break lst = [x for x in primes if N < x

백준 알고리즘 BaekJoon Online Judge 11653번 "소인수분해" 문제입니다. N = int(input()) i = 2 while N != 1: if N%i == 0: N //= i print(i) else: i += 1 단순하게 생각하면 쉬운 문제라고 생각한다. 소수의 시작은 2이므로 2부터 N을 나누기 시작한다. 나누어 떨어지면 출력하고 나누어 떨어지지 않으면 i를 증가시킨다.

백준 알고리즘 BaekJoon Online Judge 2581번 "소수" 문제입니다. A = int(input()) B = int(input()) a = [False,False] + [True]*(B-1) primes=[] for i in range(2,B+1): if a[i]: primes.append(i) for j in range(2*i, B+1, i): a[j] = False lst = [x for x in primes if x >= A] if len(lst) > 0: print(sum(lst)) print(lst[0]) else: print(-1) 이것도 역시 에라스토테네스의 체를 사용해야 하는 문제다. 수의 범위가 10000이하기 때문에 더욱 더 사용해야 한다. 그리고 만든 소수 리스트를 입력..

백준 알고리즘 BaekJoon Online Judge 1978번 "소수 찾기" 문제입니다. n=1000 a = [False,False] + [True]*(n-1) primes=[] for i in range(2,n+1): if a[i]: primes.append(i) for j in range(2*i, n+1, i): a[j] = False N = int(input()) lst = list(map(int, input().split())) cnt = 0 for ele in lst: if ele in primes: cnt += 1 print(cnt) 수들을 입력받고 그 중 소수의 개수를 찾는 문제다. 소수임을 판별하는 문제는 굉장히 많지만 소수를 판별하는 대상의 수가 1000정도가 된다면 나는 에라스토테네스..