[컴퓨팅사고력] 알고리즘에 필요하거나 도움될 수 있는 것들

- 대우

p->q  가 참이면  ~q -> ~p 도 참이다.

---

- 멍청이 논리

틀린 명제를 참이라고 가정을 하면 어떤 명제도 참이 된다.  (= F->()는 참이다! )

ex) "2가 홀수이면 5는 짝수다." 라고 했을 때

2가 홀수이면 5가 짝수 -> True

2가 홀수이면 5가 홀수 -> True    : 2가 짝수인데 홀수라고 했으니 5를 홀수라고 우길 수 있다.

2가 짝수이면 5가 짝수 -> False

2가 짝수이면 5가 홀수 -> True

 

Q) 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다. -> true : 0이 홀수라고 거짓말했으니 뒤는 무조건 참

---

- 귀납법

기본형태 : P(1)이 참이고, P(n) -> P(n+1) 이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

강한형태 : P(1)이 참이고, P(1)^P(2)^...^P(n) -> P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

 

ex)

F(n) = F(n-1) + n, F(0)=0 (경계/시작점 반드시 줘야함)

1) F(1)=F(0)+1 참. 1+2+3+4+...+n 에서 F(1)=1 참

2) F(n)=F(n-1)+n 가정

3) F(n+1)=F(n)+(n+1) 증명. 왼쪽 혹은 오른쪽 중 하나를 정의대로 표현해보면,

    3)의 왼쪽은 1+2+3+4+...+n+(n+1) 정의대로 1부터 n+1까지의 합이니까

    3)의 오른쪽 F(n) = 1+2+3+4+...+n 이므로 F(n)+(n+1)=1+2+3+4+...+n+(n+1) 그러므로 왼쪽과 오른쪽 같음

 

---

문제

 

1. n 이 짝이면 3n+5 는 홀수임을 증명하라.

n = 2k 라 하면 3n+5는 3(2k)+5 => 2(3k) + (4+1) => 2(3k+2) + 1 이므로 홀수이다.

 

2. n이 홀수이면 n^2+n은 짝수임을 증명하라.

n = 2k+1 이라 하면 (2k+1)^2+(2k+1) => 4k^2+4k+1+2k+1 => 4k^2+6k+2 이므로 짝수이다.

 

3. n^2이 3의 배수이면 n은 3의 배수임을 증명하라. => 대우 이용

n이 3의 배수가 아니면 n^2가 3의 배수가 아니다를 증명

n=3k+1 이라고 하면 (3k+1)^2 => 9k^2+6k+1 = 3(3k^2+2k)+1 이므로 3의 배수가 아니다.

 

4. n이 홀수이면 n^2을 8로 나눈 나머지는 1임을 증명하라

(힌트: n을 4로 나눈 나머지가 1인 경우와 3인 경우로 나누어 보자)

(2k+1)^2 % 8 => (4k^2 + 4k + 1) % 8

 

n이 홀수인데, 4로 나눈 나머지가 1인 경우 n = 4k+1

n^2 = 16k^2+8k+1 = 4(4k^2+2k)+1 => %8 은 1 !!

 

n이 홀수인데, 4로 나눈 나머지가 3인 경우 n = 4k+3

n^2 = 16k^2+24k+9 = 4(4k^2+6k)+(4*2+1) = 4(4k^2+6k+2)+1 => %8 은 1 !!

 

참이다~!

 

5. 유리수와 무리수의 합은 무리수임을 증명하라.

-> 귀류법 : 가정을 하고 가정을 뒤엎는 하나를 찾아서 증명

유리수 + 무리수가 유리수라고 가정한다.

1+ 루트2가 유리수라면 1+루트2+ -1 가 유리수니까 루트2 가 유리수라는 말인데 말이 안 됨! -> 거짓.

 

6. 루트2는 무리수임을 증명하라.

자연수 p, q 로 p/q가 유리수라 가정한다. ( 유리수는 기약분수로 표현 가능하다. )

p/q = 루트 2  -> 제곱하면 p^2 = 2q^2 이다. 홀수제곱은 홀수고 짝수제곱은 짝수이므로

p 는 짝수인 것을 알 수 있고 이것은 다른 수로 나눌 수 있다.

즉 기약분수가 아닌 것이 증명되므로 무리수이다.

 

7. 1 + 2 + 3 + ... + n = n(n+1)/2 임을 증명하라.

-> 수학적 귀납법

 

1) S1 = 1  참이다.

2) Sn = 1+2+ ... + n = n(n+1)/2  라고 가정한다.

3) Sn+1 = 1+2+...+n+(n+1) = n(n+1)/2 + n+1 => ( n+1 )( (n+2)/2 )  이 되는데 참이므로

 

1 + 2 + 3 + ... + n = n(n+1)/2 은 참이다.

 

 

8. r != 1 일 때 시그마 i가 0부터 n 까지 r^i = ( r^(n+1)-1 ) / (r-1) 임을 증명하라.(등비수열)

 

9. 2 이상의 모든 자연수 n에 대해 n^3 -n 은 6으로 나누어 떨어짐을 증명하라.

n^3-n = n(n^2-1) = n(n-1)(n+1) => (n-1)n(n+1)

연속 세 수를 곱하면 무조건 6의 배수이다....?

 

---

스미스수 : 각 자리 합이 소인수 분해 했을 때의 각 자리수의 합과 같은 수

ex) 22 = 2*11 => 2+2 = 2+1+1 (소수제외)

---

에라토스테네스 체 : 소수 구하기

2, 3 ,5 가 소수인 걸 아니까

2,3,4, ... , 25 까지 2의배수, 3의배수, 5의배수 제외시키면 남은 수들이 다 소수이다.

즉 n이 소수인 것을 알면 n^2까지 소수들을 알 수 있다~

---

유클리드 호제 = 최대공약수(GCD) 구하기

두 수의 약수를 계속 모듈러 해서 한 쪽 수가 0이 될 때까지 계산하여 구한다.

-> gcd(A,B) = (A%B, B) => (0, B')

 

 

+ GCD 와 LCM

120 = 2^3 * 3 * 5,  150 = 2 * 3 * 5^2

GCD = 2 ^ ( min(3,1) ) * 3 ^ ( min(1,1) ) * 5 ^ ( min(1,2) )

LCM = 2 ^ ( max(3,1) ) * 3 ^ ( max(1,1) ) * 5 ^ ( max(1,2) )

 

GCD = 2 * 3 * 5 = 30

LCM = 8 * 3 * 25 = 600

 

120 * 150 = GCD * LCM = 18000

 

---

배열차원변환 : 1차원배열을 2차원배열로, 2차원배열을 1차원배열로!

 

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

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

---

배수 특징

 

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

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

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

              ex) 2020년 1월 1일이 수요일이면

                  수 = 3 이라고 하면

                   2020년 1월 13일은 12일 경과이므로     (3+12) % 7 = 1 이니까 월요일!

 

8의 배수 : 홀수의 제곱 % 8 = 1!!!!!

---

mod 특징

 

(a+b) mod n = ( a mod n + b mod n ) mod n

(a-b) mod n = ( a mod n - b mod n ) mod n

(a*b) mod n = ( a mod n * b mod n ) mod n

---

페르마의 소정리

 

a^p Ξ a (mod p)

a^(p-1) Ξ 1 (mod p)

a^(p-2) Ξ 1/a (mod p)

 

ex1 ) 5C3 (mod 7) ??

5! / 2!3! = 5*4/2 = 10 Ξ 3 (mod 7)

 

ex2) 35C33 (mod 7) = 35! / 33!2!

33!2! 를 a라고 하면

35! / a = 35! * (33!2!)^5     (mod p)          => 분수식을 만나면 이렇게 정수식으로 고칠 수 있다!!

 

---

함수

 

일대일함수(단사) : 하나의 x는 하나의 y에만 대응됨. 이때 y에 대응되지 않은 값이 있어도 됨

일대일대응(전단사) : 하나의 x는 하나의 y에만 대응되고 모든 y가 대응되어야 함

전사 : 하나의 y에 여러 x가 대응될 수 있다.

---

등차수열

A2 - A1 = d

 

An = Ak + (n-k)d

 

 

등비수열

A2 = A1 * r

 

An / A1 = r^(n-1)   => An = A1 * r^(n-1)

 

Sn = A1 + A1r + A1r^2 + ... + A1r(n-1) 이라 하면

(1-r)Sn = A1 - A1  *r^n      =>      Sn = A1(1-r^n) / (1-r)

 

 

계차수열

1 2 4 7 11  ...

 

An = A1 + Σk=1~n-1  Bk

 

 

 

 

+ 참고   

Σ k(k+1)(k+2) = n(n+1)(n+2)(n+3) / 4