컴퓨팅 사고력 - swkim0128/PARA GitHub Wiki

---

!Untitled 27.png

---

참과 거짓을 명확히 판별할 수 있는 문장.

대우

p → q 가 참이면 ~q → ~p도 참이다.

멍청이(pseuduo-proposition 논리)

→ 너가 경찰서장이면 난 대통령

틀린 명제를 참이라고 가정을 하면 어떤 명제도 참이 된다.

2가 홀수면 5는 짝수다.

---

---

짝수 2n(간혹 4n, 4n + 2)

홀수 2n + 1(간혹 4n + 1, 4n + 3)

정사각형 마방진 = 짝수 마방진 + 홀수 마방진 = 짝수(4n 마방진 + 4n + 2 마방진) + 2n + 1 홀수 마방진

n(n + 1)(n + 2) 또는 (n - 1)n(n + 1), 연속인 세수는 6의 배수다.

[n] 가우스 : n을 넘지 않는 최대 정수

9 % 2 = 9 - [9/2] * 2 = 1

완전수(자신을 제외한 약수의 합이 자신이 되는 수)

친화수(A 자신을 제외한 약수의 총합이 B가 되고, B자신을 제외한 약수의 총합이 A가 되는 수)

스미스(각 자리의 합이 소인수 분해 했을 때의 각 자리수의 합과 같은 수, 22 = 2 * 11 → 2 + 2 = 2 + 1 + 1, 소수제외)

약수, 제곱, 소수 (에라토스 테네스 체)

---

---

!Untitled 1 7.png

---

---

비트 연산을 이용한 행렬제곱, 페르마 소정리

---

n!과 소인수 분해(배열)

---

(i + 1) % 5

(i + 4) % 5

---

A[i / col][i % col] = B[i];

B[i * col + j] = A[i][j]

---

2배수 : 짝수

3의 배수

4의 배수 :

5의 배수 : 2, 5를 이용한 소인수 분해, 순환 소수

6의 배수 : (a - 1)a(a + 1)

7의 배수 : 요일(기준 요일 + 경과 일), 달력, 13일의 금요일

8의 배수 : 홀수의 제곱 % 8

---

1. 두 개의 서로 다른 (p, q) 소수를 고른다.
2. 두 수를 곱하여 N = pq를 찾는다.
3. phi(N) = (p - 1)(q - 1)를 구한다.
4. phi(N) 보단 작고, phi(N)와 서로소인 정수 e를 찾는다.
5. 확장된 유클리드 호제법을 이용하여 d*e를 phi(N)로 나누었을 때 나머지가 1인 정수 d를 구한다.

---

!Untitled 2 6.png

---

---

---

Convex Hull

주어진 점들 중 y좌표가 가장 작거나 혹은 가장 작은 점이 둘 이상이라면 x좌표가 가장 작은 점을 선택한다.

선태한 점을 기준으로 나머지 점들을 반시계 방향으로 정렬(각도 + 거리)

그라함 스캔 알고리즘 적용

Graham's Scan Alogorithm

제일 처음 선택한 점을 스택에 먼저 넣고 정렬된 점들을 차례대로 스택에 넣는다.

새로운 점을 스택에 push할 때, 만약 스택에 두 개 이상의 점이 있다면 가장 최근에 push된 두 점을 이은 직선을 기준으로 새로운 점이 왼쪽에 있다면 push, 오른쪽에 있다면 스택의 가장 위의 점을 pop.

---

!Untitled 3 6.png

!Untitled 4 4.png

---

---

---

F(n + 2) = F(n + 1) + F(n)

Golden Ratio = ${F(n)\over F(n + 1)}$

---

$C_n = \Sigma^{n - 1}{i=0}C_i * C{n-1-i}$

$C_n = {1 \over n + 1}{2n \choose n}$

---

등차

등비

계차

특성방정식

피보나치

카탈란

---