태브로의 개발위키

에라토스테네스의 체소수를 판별하는 알고리즘.소수를 대량으로 빠르고 정확하게 구하는 방법.실제로 코테 문제를 푸는데 시간초과에 늪에 빠져서 이 방법으로 해결한다.에라토스테네스의 체 원리2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.2를 빼줘서 저장하면서 시작그 다음 모든 2의 배수를 제거 해준다.다음으로 3을 빼주면서 3에 대한 모든 배수를 제거해준다.4는 3번과정에서 지웠으므로 넘어가준다.5부터는 다시 5의 배수를 제거해준다.코드코드를 보기전에 간략하게 과정을 다시 설명하겠다.우리가 해야하는건 한가지 숫자를 정하고 그 숫자에 대한 배수를 모두 지워가면서 거르고 거르는 것이다.64로 예를 들면 루트 64인 8까지 배수들을 다 빼주면 64밑의 소수만 남게된다.그래서 검사를 제곱급까지만 해도 알아서 ..

출처 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이: n = int(input()) for i in range(2,n+1): while 1: if n % i == 0: n = n // i print(i) else : break 나름 신박하게 잘 했다 생각했는데 다 비슷하게 푼거 같다... 계속 머리속에 있던 생각은 for 문을 써서 그 안에서 계속 루프를 돌려야한다 ! 를 생각했다. 그래서 while 을 항상 설정해주고 계속 i로 나누고 나누면 나눈 i를 출력했다. 그리고 나눠지지않으면 멈춰서 다음 i 로 넘어가서 정답에 도달했따.

출처 : https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 : # 시간 초과 a = int(input()) b = int(input()) prime = [] for i in range(a,b+1): cnt = 0 if i ==1 : continue for j in range(2,b+1): if i % j == 0: cnt += 1 if cnt == 1 : prime.append(i) if prime == []: print(-1) else: print(..

출처: https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net n = int(input()) a = list(map(int, input().split())) prime = 0 for i in a: cnt = 0 if i==1 : continue for j in range(2,1001): if i % j == 0 : cnt += 1 if cnt == 1: prime += 1 print(prime) 풀이 : 입출력은 늘 하던 대로 받아와준다. 그리고 정답을 출력할 prime = 0 으로 지정해준다. 이제 코드를 보면 for..

출처 : 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) 어찌보면 틀렸고어찌보면 맞았다... 이틀전 들었던 자바 수업시간에 저렇게 큰 수는 출력하는데 %를 써야한다던지 범위를 바꿔야한다던지 해서 조금 헷갈렸다. 결론적으로 ! 다른 언어는 좀 까다로울 수 있는데 우리 python은 저정도 아주 쉽게 연산한다고 한다. python이 연산력이 좋다고 봤는데 그래서 딥러닝에 많이 쓰이나?

출처 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이: n = int(input()) cnt =0 while n >= 0 : if n%5 == 0: cnt += n//5 print(cnt) break n -= 3 cnt += 1 else : print(-1) 틀렸다~~~ 케이스 계속 나누면서 if 에 if를 넣고 삼항연사자 넣고 또 if elif 넣으면 어거지로 풀리기는 할텐데 하다가 아니다 싶어서 풀이를 봤다. 문제 자체에서 요구하는건 일단 5..

출처 https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net t = int(input()) for _ in range(t): k = int(input()) n = int(input()) ppl = [i for i in range(1,n+1)] for x in range(k): for y in range(1,n): ppl[y] = ppl[y] + ppl[y-1] print(ppl[-1]) 1. 입출력은 늘 하던거라 생략한당 2. 문제를 뜯어 보면 이해가 좀 어려웠는데 좀 더 친절하게 써줄 필요..

https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이 : t = int(input()) for _ in range(t): h, w, n = map(int, input().split()) if n % h == 0: front = h back = int(n/h) else : front = n % h back = int(n/h +1) print(front * 100 + back) 일단 2번 틀렸는데 n % h =0 이되면 층수가 0층이 ..

출처 : https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net a,b,v = map(int, input().split()) dis = v - a if dis % (a-b) == 0 : t = int(dis/(a-b)) else : t = int(dis/(a-b)+1) print(t + 1) 풀이 : while 로 풀면 시간초과가 나온다. 우리가 푸는 수학방식을 선호하지말자. 다음은 어떻게 풀었냐면 직관적으로 해석 해도 된다 . 일단 쉽게 설명하면 거속시이다. 도착한 날 전날이 아주 중요하다. 그래서 도착 전..

출처 : https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net x = int(input()) cnt = 0 sum_cnt = 0 while sum_cnt < x: cnt += 1 sum_cnt += cnt if cnt % 2 == 1: a = sum_cnt - x + 1 b = cnt -sum_cnt + x else : a = cnt - sum_cnt + x b = sum_cnt -x + 1 print(f'{a}/{b}') 풀이 : 분자 부분을 보면 1 12 321 1234 54321 구조를 갖고 있고 분모를 보면 1 21 123 4321 12345 이런 구조를 갖고 있다. 따라서..