Algorithm/알고리즘 문제풀이92 백준 3009 파이썬 - 네 번째 점 1. 문제 링크 https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 2. 나는 어떻게 생각했는가? # 내가 생각한 풀이 # 사각형의 4개의 좌표는 다음과 같은 조합을 이룬다 # min x, min y # min x, max y # max x, min y # max x, max y # 이 조합을 이용하면 max x와 min x, max y와 min y는 각각 2개씩을 갖는다. # 만약 1개씩 부족한 조합이 있다면, 비어있는 좌표가 정답이 된다. x_list = [] y_list = [] for _ in range(3): x, y .. 2021. 8. 17. 백준 1085 파이썬 - 직사각형에서 탈출 1. 문제 링크 https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 2. 나는 어떻게 생각했는가? x, y, w, h = map(int, input().split()) right_distance = w - x left_distance = x top_distance = h - y down_distance = y result_x = 0 result_y = 0 if right_distance >= left_distance: resul.. 2021. 8. 17. 백준 9020 파이썬 - 골드바흐의 추측 1. 문제 링크 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 2. 나는 어떻게 생각했는가? def prime(n): #에라토스테네스의 체 a = [True] * n sqrt = int(n ** 0.5) for i in range(2, sqrt + 1): if a[i]: for j in range(i + i, n, i): a[j] = False return [i for i in range(2, n) if a[i] == Tr.. 2021. 8. 14. 백준 4948 파이썬 - 베르트랑 공준 1. 문제 링크 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 2. 나는 어떻게 생각했는가? def check_sosu(n): two_n = 2 * n a = [False, False] + [True] * (two_n - 1) primes = [] for i in range(2, two_n + 1): if a[i]: primes.append(i) for j in range(2 * i, two_n + 1, i): a[j] = False .. 2021. 8. 14. 백준 1929 파이썬 - 소수 구하기 1. 문제 링크 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 2. 나는 어떻게 생각했는가? m, n = map(int, input().split()) for i in range(m, n + 1): count = 0 for j in range(2, i + 1): if i % j == 0: count += 1 if count > 1: break if count == 1: print(i) - 우선 단순 무식하게 접근해보았다. - 역시나 시간초과가 발생했다. - 그래서 이전에 배.. 2021. 8. 13. 백준 11653 파이썬 - 소인수분해 1. 문제 링크 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 2. 나는 어떻게 생각했는가? n = int(input()) case = [] devider = 2 while n > 1: if n % devider == 0: case.append(devider) n = n / devider else: devider += 1 if devider > n: break for i in range(len(case)): print(case[i]) 3. 코드 개선 - 맞았지만 시간이 오래 걸린다. - 백준에서는 언어마다 보너스 시간이 있기 때문에 맞았다고 나왔지만, 2초이상 .. 2021. 8. 12. 백준 2581번 파이썬 - 소수 1. 문제 링크 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 2. 나는 어떻게 생각했는가? - 앞서 풀이를 올려놓은 1978번을 풀었다면, 무난하게 풀 수 있는 문제다. - 약간의 생각만 더 하면 되는데, 그 부분이 시간초과에 관련된 부분이다. - 이중 FOR문을 사용하기 때문에 시간복잡도가 O(n제곱) 만큼 걸리기에, - 이를 최소화 해야 하는 방법을 생각해야 한다. - 입력값 m과 n이 커질수록, 시간초과가 발생할 확률이 높아진다. - 그러므로 소.. 2021. 8. 12. 백준 1978번 파이썬 - 소수 찾기 1. 문제 링크 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 2. 나는 어떻게 생각했는가? # 소수란 1과 자신으로만 나눠지는 수 # 즉, 약수가 1과 자신밖에 없는 것 # 어떤 수 n에 대한 약수는 n보다 작다. # 즉, 약수 2021. 8. 12. 백준 1011번, 파이썬 - Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net # 최고속도를 찍는 지점을 찾는다. 이 경우, 세가지 경우가 발생한다. # case 1) 최고속도를 찍은 지점까지의 거리와 남은 거리(a, 알파)가 동일한 경우 # case 2) 최고 속도를 찍은 지점까지의 거리 < 남은 거리(a, 알파)의 경우 # case 2-1) 0 < a 2021. 8. 11. 이전 1 ··· 5 6 7 8 9 10 11 다음
