Kyo's Blog

Math Algorithm(Overview)

2025/10/19

Math Algorithm - 수학

01. 홀수와 짝수

홀수 정의
- odd number
- 2로 나누어 떨어지지 않는 정수
짝수 정의
- even number
- 2로 나누어 떨어지는 정수

홀수와 짝수 판단

const num

if(num % 2 == 0) return "짝수"
if(num % 2 == 1) return "홀수"

02. 2진수, 8진수, 16진수

2진수를 8진수로 변환하기
- 2진수의 수를 뒷자리부터 3자리씩 끊어내고, 각 자리에 4,2,1을 곱하면 8진수를 구할 수 있다. (처음 3개에 4,2,1을 곱하면, 다음 3개에는 32,16,8을 곱해야 할 것 같지만, 이미 자신의 자리 자체가 8이 곱해졌음을 의미하기에 4,2,1을 곱한다.)
- [2진수]100 111 101 = 1(4)0(2)0(1) 1(4)1(2)1(1) 1(4)0(2)1(1) = [8진수]4 7 5

03. 소수

정의
- 1과 자기 자신 이외의 자연수로는 나누어 떨어지지 않는 자연수
- 1은 소수가 아닌 유일한 자연수이다.
에라토스테네스의 체
- 소수를 찾는 방법
- 100 이하의 소수를 구한다고 하면 1~100을 적고, 2부터 100까지 반복한다. (0, 1은 소수 아님)
- 지워지지 않는 수 중에서 가장 작은 수는 2이다. 2는 소수이고, 2의 배수는 모두 소수가 아니므로 모두 지운다.
- 그 다음 지워지지 않은 수 중에서 가장 작은 수는 3이고, 3도 소수이다. (소수가 아니였다면 이전에 지워졌어야 한다.) 3의 배수도 모두 지운다.
- 위의 과정을 반복하며, 소수가 아닌 수는 모두 지운다.
```
// 소수 찾기
const isPrime = Array(N + 1).fill(true); // N까지의 소수를 찾는다.
isPrime[0] = isPrime[1] = false; // 0, 1은 소수 아님

for (let i = 2; i <= N; i++) {
	if (!isPrime[i]) continue;

	// 2+2, 2+2+2, 2+2+2+2 -> i의 배수 모두 지우기
	for (let j = i + i; j <= N; j += i) {
		isPrime[j] = false;
	}
}
```

04. 약수

정의
- 어떤 수를 나누어떨어지게 하는 수
특징
- 순서대로 나열된 약수들을 가지고 가운데를 기준으로 서로 곱하면 원래의 수가 된다.
- 12 (1, 2, 3, 4, 6, 12)
- 1 * 12 = 12
- 2 * 6 = 12
- 3 * 4 = 12

05. 최대공약수와 최소공배수

최대공약수 정의
- GCD (Greatest Common Divisor)
- 두 수, 혹은 그 이상의 여러 수의 공통된 약수 중 가장 큰 것
최소공배수 정의
- LCM (Least Common Multiple)
- 두 수, 혹은 그 이상의 수들의 공통인 배수 중 가장 작은 것
유클리드 호제법
- 최대공약수를 찾는 방법
- 두 양의 정수 a 와 b (a > b) 에 대하여, a % b = r 이라 하면, a 와 b 의 최대공약수는 b 와 r 의 최대공약수와 같다.
- 즉, a % b = r 이라고 했을 때, GCD(a, b) = GCD(b, r)과 같고, r = 0 일때 b 가 최대공약수 이다.
```
const GCD = (a, b) => {
	if (a % b == 0) return b;
	else return GCD(b, a % b);
};
```
최대공약수(유클리드 호제법)를 이용해 최소공배수 찾기
- 두 수와 최대공약수, 최소공배수 사이에는 아래와 같은 공식이 성립한다.
- 두 수의 곱은 최대공약수와 최소공배수의 곱과 같다.
- 즉, a * b = gcd * lcm
- lcm = (a * b) / gcd
```
const a, b = [6, 18];

const gcd = GCD(a, b);
const lcm = (a * b) / gcd
```

06. 수열

정의
- 수 또는 다른 대상의 순서 있는 나열
풀이법
- 값이 커지더라도 하나씩 나열하면서 그 안의 규칙을 찾아야 한다.
- 초기에는 규칙이 없다가 나중에 규칙이 생기는 경우도 있어서, 값이 커진 후에 규칙을 찾는 것이 더욱 도움이 될 수 있다.

07. 피보나치 수

정의
- 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞의 두 항의 합인 수열이다.
규칙
- 1, 1, 2, 3, 5, 8
- f(n) = f(n - 1) + f(n - 2)

999. 원

BOJ 1002 토대로 작성 예정