1. 유클리드 호제법유클리드 호제법(또는 유클리드 알고리즘, Euclidean Algorithm)은 두 양의 정수의 최대공약수를 구하는 방법 중 하나이다.여기서 호제라는 말은 서로 나눈다는 것을 의미한다. 2. 최대공약수의 정의최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 정수의 공통 약수 중 가장 큰 양의 정수이다.또한 최대공약수가 $1$인 두 정수를 서로소(coprime)라고 한다. ($0$과 어떤 정수 $a$의 최대공약수는 $a$로 정의할 수 있다. $0$은 모든 정수의 배수이기 때문이다.) 3. 최대공약수의 특징두 정수 $a$와 $b$의 최대공약수 $\gcd(a, b)$에 대해, $ax + by = \gcd(a, b)$를 만족하는 정수 $x$, $y$가 존재한다...
Algorithm
1. 버블 정렬이란?서로 인접한 두 원소를 비교하고, swap 연산을 수행하면서 정렬하는 방식이다.가장 큰 값이 배열의 끝으로 이동하는 과정이 물방울이 수면으로 떠오르는 듯한 모습을 보이기 때문에 버블 정렬이라는 이름이 붙었다. 2. 버블 정렬의 동작 과정배열의 처음부터 끝까지 순회하면서 인접한 두 원소를 차례대로 선택한다.인접한 두 원소를 비교하여 정렬 순서와 맞지 않다면, 서로 자리를 교환한다.배열의 끝에 가장 큰 값이 정렬되면, 다음 반복에서는 그 값을 제외하고 정렬한다.배열이 완전히 정렬될 때까지 1~3 과정을 반복한다. 3. 버블 정렬의 구현 코드아래는 버블 정렬을 구현한 코드이다.void bubble_sort(vector &nums) { int n = nums.size(); for ..
2의 거듭제곱을 외우고 있다고 말하면 그걸 왜 외우냐는 질문이 가장 많이 들어온다.어릴 적에 심심해서 외웠던 게 시작이었던 것 같다. 어릴 적에 10제곱까지 외웠다가 20제곱까지 늘렸던 기억이 난다.대학교 와서 27제곱까지 외웠던 것 같다.뇌 용량의 한계로 더 이상 외우려고 하지 않았는데,최근에 알고리즘 공부하고 코드 짜다보니 그 유명한 2^31 - 1 = 2147483647을 자주 접하게 되었다.그래서 내친김에 32제곱까지 외워버렸다. 2^1 = 22^2 = 42^3 = 82^4 = 162^5 = 32 2^6 = 642^7 = 1282^8 = 2562^9 = 5122^10 = 1024 2^11 = 20482^12 = 40962^13 = 81922^14 = 163842^15 = 32768 2^16 = 6..
