본문 바로가기

Algorithm120

백준 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.
백준 10757번, 파이썬 - 큰 수 A + B https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net a, b = map(int, input().split()) print(a + b) # C언어의 경우, 자료형에 따른 메모리가 한정되어 있기 때문에 # 10757번 같은 문제를 풀기 어렵다. # 파이썬의 경우, 언어 자체적으로 BigInt를 지원하기 때문에 문제없이 연산이 가능하다. # 그렇다면 파이썬이 Integer로 표현할 수 있는 최대값은 몇일까? import sys max_num = sys.maxsize max_num2 = sys.maxsize + 1 print("max_num =", type(max.. 2021. 8. 11.
백준 2839번, 파이썬 - 설탕배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net # 최소 봉지 개수의 조합을 짜려면 우선 5단위로 끊어야 한다. # 5단위로 끊고 남은 나머지에 따라 조건문이 달라진다. # 5로 나누기 떄문에 1 ~ 4 까지의 나머지가 생길 수 있다. # case 0) 나머지가 없는 경우, 5로 나눈 몫을 그대로 가져간다. # case 1) 나머지가 1인 경우, 5로 나눈 몫을 1개(5) 줄이고 나머지 1 + 5를 3단위로 나눈다. # case 2) 나머지가 2인 경우,.. 2021. 8. 11.
파이썬 - filter와 lambda, map 사용방법 1. filter() 와 lambda, map() a) filter() 와 lambda - filter() 함수는 특정 조건에 걸러진 요소들을 iterator 객체로 만들어 반환한다. - 즉, list, set, tuple에 담아야 사용 및 출력할 수 있다는 것이다. - 여기서 특정 조건은 적용시킬 함수를 의미한다. 그래서 lambda를 많이 사용한다. - lambda는 다음과 같은 형태로 구성된다. lambda 인자 : 표현식 - 만약 a, b 두 수의 합을 반환하는 함수를 작성한다면 다음과 같이 작성할 수 있다. def plus(a, b): return a + b plus(10, 10) # 20을 반환한다. - 이를 람다로는 다음과 같이 작성할 수 있다. result = (lambda a, b : a.. 2021. 8. 6.

티스토리툴바