수학

(C++) 백준 1629번 - 곱셈

문제 링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 재귀를 활용하여 풀이하였다. "n의 k승을 알면, n의 2k승과 n의 2k+1승을 알 수 있다."는 사실과 "(a x b) % k = (a % k) x (b % k)"라는 사실을 활용하여 풀이를 진행하였다. #include using namespace std; using ll = long long; int power(ll a, ll b, ll c){ if(b == 0) return 1; // 모든 수의 0승은 1 if(b == 1) retur..

(Python) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 저번에 풀이했던 1978번과 같은 방식인 에라토스테네스의 체로 풀이를 했다. 다만 2부터 (자기 자신 - 1)을 모두 나눠보면 시간 초과가 발생하여 어떻게 해야 하는지 고민하던 중, 2부터 √자기자신 까지만 나눠도 된다는 사실을 알게 되어 그렇게 풀이해 보니 제한 시간 내에 통과할 수 있었다. import sys import math n, m = map(int, sys.stdin.readline().split..

(Python) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 처음엔 단순하게 에라토스테네스의 체 방식으로 풀어서는 시간 초과가 날 수 있을거 같았으나 문제 분류에 에라토스테네스의 체라고 적혀있어서 시도해보았더니 제한 시간 내에 통과할 수 있었다. n = int(input()) count = 0 # 소수가 아닐 경우를 count arr = list(map(int, input().split())) for num in arr: if num == 1: # 1은 소수가 아님 count += 1 # 소수가 아니면 c..