Skip to content

Latest commit

 

History

History
194 lines (137 loc) · 4.28 KB

Computation Thinking.md

File metadata and controls

194 lines (137 loc) · 4.28 KB
Raw

이산수학 이론들

  • 논리적으로 정확하게 확인하는 과정 연습의 필요성
  • 프로그램 코딩 전, 정확도와 속도 예측 가능해야

0. 서론 - 프로그래밍과 논리/수학

프로그래밍

  • 프로그래밍 언어 논법 & 라이브러리 사용
  • 논리 (Hard Logic)

카드 문제

  • 숫자 / 알파벳
  • 한쪽이 D이면 반대쪽은 3이다.
  • 문제: D F 3 7 > 정답: D, 7

맥주집 문제

  • 20세 이하인 사람은 맥주 마실 수 없다.
  • 문제: 17 31 콜라 맥주 > 정답: 17, 맥주

용어

  • 명제: 참이나 거짓을 알 수 있는 식, 문장

  • 진릿값: 참이나 거짓 표현

연산

  • 부정 NOT : -
  • 논리곱 AND : ^
  • 논리합 OR : V
  • 배타적논리합 XOR:

합성

  • 우선순위 : NOT > AND, OR > →,↔

  • 항진명제 : 진릿값이 항상 참

  • 모순명제 : 진릿값이 항상 거짓

  • 사건명제 : 항진명제나 모순명제가 아닌 명제

조건명제

  • p, q가 명제일때, p가 조건(원인), q가 결론(결과)로 제시되는 명제
  • p → q
  • p가 False이면 조건명제는 True == T → F 일때만 False

쌍방조건명제

  • p,q가 명제일 때, 명제 p와 q가 모두 조건이면서 결론인 명제
  • p ↔ q
  • p,q 모두 True이거나 Flase이면 쌍방조건명제는 True

조건명제의 역, 이, 대우

p q p → q q → p -p → -q -q → -p
T T T T T T
T F F T T F
F T T F F T
F T T T T T

논리연습

  1. 0은 홀수 → 미국 2080

    True : p가 F

  2. xx 가 Prime Number → 2는 짝수

    True : 대우 명제식 -q가 F

증명

  • 정확한 명제식으로 표현 가능해야함
  • p → q 와 p ↔ q를 혼동하는 대에서 오해 발생

수학적 귀납법

  • P(1)이 True AND P(n)→P(n+1)이 True이면 P(n)은 모든 자연수에 대해서 True

2. 수와표현

logn

  • 2의 몇 승이 n이 되는지

  • n을 표현하는데 필요한 비트수

  • 1로 시작해 몇 번 두배로 곱하면 n이 되는지

  • n을 2로 몇 번 나누면 거의 1이 되는지

  • 32비트 컴퓨터 2^32 = 40억개 주소

  • ∑(n/2^k) = nlogn

    • k = logn

  • n + n/2 + ... + 1 = 2n

  • 두 항의 개수는 log n개

3. 집합과 조화론

집합

  • A가 B의 부분집합 == A의 임의의 원소가 B에 포함됨
  • A와 B가 같다 = A가 B의 부분집합 AND B가 A의 부분집합

조화론

  • 경우의수
  • 조합 C
  • 순열 P

증명

  • 귀납법 : P(1), P(n)->p(n+1)임을 이용
  • 귀류법 : 명제 부정을 가정이 거짓임을 이용

DP

  1. T(n) = T(n-1) + 1

    • T(n-k) +k
    • T(0) + n
    • 1 + n
    • O(n)

  2. T(n) = T(n-1) + n

    • T(n-k) + (n-k+1) + .... + n
    • T(0) + 1 + ... + n
    • {n(n+1)+2}/2
    • O(n^2)

  3. T(n) = T(n-1) + logn

    • T(n-k) + log(n-k+1) + ... + logn
    • T(0) + log n!
    • T(0) + logn + ... + logn
    • T(0) + log(n^n)
    • O(nlogn)

  4. T(n) = T(n/2) + 1

    • T(n/4) + 1 + 1
    • logn
    • O(logn)

  5. T(n) = T(n/2) + n

    • T(n/4) + n/2 + n
    • T(1) + 2 + ... + n/2 + n
    • (1-2^(logn)/1-2
    • n-1
    • O(n)

  6. T(n) = 2T(n/2) + n

    • n + nlogn
    • O(nlogn)

  7. T(n) = 3T(n/2) + n

    • 3(3T(n/4) + n/2) + n
    • 9T(n/4) + 3n/2 + n
    • 27T(n/8) + n(9/4 + 3/2 + 1)
    • 3^logn + 2n{ ((3/2)^logn - 1) }
    • 3^logn + 2*3^logn -2n
    • n^log3 + 2*n^log3 - 2n
    • 3*n^log3 - 2n
    • O(n^log3)

  8. T(n) = T(n-1) + 1/n

    • T(n-2) + 1/n-1 + 1/n
    • T(n-k) + 1/n-k+1 + 1/n
    • T(0) + 1 + ... + 1/n <= T(0) + log n
    • O(logn)

5. 재귀

  • 재귀 : 자기 자신을 호출하는 함수

  • 다른 입력으로 호출하기에 다른 결과 출력

  • 귀납법 증명

    • P(0), P(n-1) > P(N) 두가지 사실이면 모든 n에 대해 sol

  • 크기가 더 작은 입력을 통해 문제 해결

  1. F(n) = F(n-1) + F(n-2), F(1)=F(2)=1
    • T(n) = T(n-1) + T(n-2) < 2T(n-1)
    • lognT(2)
    • O(logn)
  2. Merge Sort
    • T(n) = 2T(n/2) + n
    • lognT(1) + nlogn
    • O(nlogn)
  3. T(n) = T(2n/3) + T(1n/3) + T(2n/3) + 1
    • O(n^log(3/2)^3)

6. 동적프로그래밍

  • 동일 입력 함수 호출 반복될때, 그 값을 저장해놓고 쓰는 것 (Memoization)
  • 결과값을 순서를 정해서 계산할 수도 있다. (DP)