공hannah부

거듭제곱 기본 거듭제곱 음이 아닌 정수 a, x와 자연수 m에 대해 a^x(mod m) ← 모듈러 취하는 이유: integer overflow 때문! 거듭 제곱 정의대로 a를 x번 곱하면 된다. 시간 복잡도: O(x) 분할정복을 이용한 거듭제곱 (더 빠른 방법) x가 짝수일 때 a^x = a^(x/2) * a^(x/2) 로 구하기 x가 홀수일 때 a^x = a^(x/2) * a^(x/2) * a 로 구하기 시간 복잡도: O(logx) C++로 구현 반복문 int m; int fpow2(int a, int x) { int ret = 1; while (x) { if (x % 2) ret = ret * a % m; a = a * a % m; x /= 2; } return ret; } 재귀문 int m; int..

최대공약수와 최소공배수 최대공약수(gcd) a=b=0 이 아닌 정수 a,b에 대해, g | a, g | b (a가 g에 나누어 떨어지고, b가 g에 나누어 떨어짐) 을 만족하는 가장 큰 자연수 g 최소공배수(lcm) a | l, b | l 을 만족하는 가장 작은 자연수 l 둘 사이의 관계 0이 아닌 정수 a, b의 최대 공약수를 g, 최소 공배수를 l이라 할 때, a x b = g x l 유클리드 호제법 유클리드 호제법이란? 두 자연수 a, b의 최대공약수를 구하는 방법 시간복잡도: O(loga) 구하는 법 두 자연수 a, b (a >= b) 가 있고, a를 b로 나눈 나머지를 r이라고 할 때 gcd(a,b) = gcd(b,r) 이를 r이 0이 될 때까지 반복 r이 0일 때 나누는 수가 나누는 수가 a와..

선형 자료 구조 선형 자료구조: 하나의 데이터 뒤에 하나의 데이터만 올 수 있는 데이터 구조 ex) 배열 등 비선형 자료구조: 하나의 데이터 뒤에 여러 데이터가 올 수 있는 데이터 구조 ex) 트리, 그래프 등 배열 자료가 물리적으로 연속되어 저장되는 자료구조 시간복잡도 임의 위치 접근: O(1) 원소 삽입/삭제: O(N) std::vector, std::array 연결 리스트 자료가 논리적으로 연속되어 저장되는 자료구조 (메모리상에서 연속하지 않는다) 시간 복잡도 임의 위치 접근: O(N) 원소 삽입/삭제: O(1) std::list 각 자료를 노드라고 한다. 노드는 데이터와 자신과 인접한 노드의 주소를 저장한다. Singly Linked List: 다음 노드의 주소 또는 이전 노드의 주소만을 저장 D..

비교함수 bool compare(T a, T b); a가 b보다 무조건 앞에 나와야 한다면 true, 그렇지 않으면 false를 반환 비교함수는 Strick Weak Ordering을 만족해야 한다 Strick Weak Ordering 이항 관계 R(a, b)에 대해서 a가 b보다 반드시 앞에 나와야 한다면 참, 그렇지 않으면 거짓이라고 하자 비교성: a가 b보다 앞에 나와야 한다면 R(a,b)는 참, R(b,a)는 거짓이다. 이 경우 a와 b를 비교할 수 있다고 한다. 비비교성: a가 b와 동등하다면 R(a,b), R(b,a)는 둘 다 거짓이다. 이 경우 a와 b를 비교할 수 없다고 한다. 아래 조건을 모두 만족해야 한다. 비반사성: 모든 a에 대하여 R(a,a)는 거짓 비대칭성: 모든 a, b에 대하..

버블정렬 인접한 두 원소를 순서대로 보면서 정렬해 나가는 알고리즘 오름차순 예시 A[i]와 A[i+1]을 비교할 때 A[i] > A[i+1] 이면 A[i]와 A[i+1]를 교환(swap)한다. 위 과정을 i=1~N-1까지 순서대로 한번 수행 하는 것을 순회라고 한다. (N은 배열의 길이) 버블 정렬은 순회를 N-1번 반복한다. ex) [4, 5, 2, 3, 1] i=1) [4, 5, 2, 3, 1] i=2) [4, 2, 5, 3, 1] i=3) [4, 2, 3, 5, 1] i=4) [4, 2, 3, 1, 5] 첫 번째 과정을 수행하면 가장 큰 수 5가 맨 뒤에 위치 i=1) [2, 4, 3, 1, 5] i=2) [2, 3, 4, 1, 5] i=3) [2, 3, 1, 4, 5] 두 번째 과정을 수행하면 두..

Basic C++ 입출력 스타일 C 스타일과 C++ 스타일을 모두 지원한다. C 스타일 int a; scanf("%d", &a); printf("%d", a); C++ 스타일 int a; cin >> a; cout