# 분할정복을 이용한 거듭제곱 - C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다. - 아래 코드에서 fpow함수가 그 방법이다. - n이 1이면 그냥 C의 1제곱이므로 return C를 해준다. - n이 2이상일 때, C의 n제곱은 다음과 같다. - n이 짝수이면 윗줄의 식을 만족하고, n이 홀수이면 아래줄의 식을 만족한다. 코드로 짜면 다음과 같다. 1. 재귀사용 def fpow(C, n): if n == 1: return C else: x = fpow(C, n//2) if n % 2 == 0: return x * x else: return x * x * C 2. 반복문 사용 - n & 1은 n이 짝수이면 0이므로 False이고, n이..
STL(Standard Template Library) * 표준 C++ 라이브러리 * 구성요소 : Container, Iterator, Function Object, Algorithm 등 컨테이너 : 객체를 저장하는 객체, 자료구조 - 순차 컨테이너(sequence container) : array, vector, list, deque 등 * 자료를 입력한 순서대로 저장하기 때문에 저장, 검색 알고리즘에 불리 -> 많지 않은 양의 자료, 검색속도 중요하지 않은 경우 사용 - 연관 컨테이너(associative container) : set, multiset, map, multimap 등 * 이진탐색트리 기반 * 일정규칙에 따라 자료를 조직화하여 저장 * 자료를 정렬하여 저장하기 때문에 검색 유리 -> 많..
백준 1929번 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net * prime함수 : n을 매개변수로 넘겨받아 1부터 n-1까지 n%i = 0이면 a에 1을 더해줘서 최종적으로 a가 1이면 (모든 수는 1로 나누어지므로 모든 수의 a는 최소1이다) 소수 -> True 반환 * a,b를 입력받아 list1에 소수인 것들만 append해줬다. * a와 b가 100만까지 들어오다보니 이 방법으로는 시간초과가 발생하였다. * 따라서 새로운 방법인 '에라토스테네스의 체'를 사용해보았다. import math def get_primes(a,b..
모르는 사이에 조금씩 조금씩..
