[SCCC] 수학적 귀납법, 분할 정복

손시연·2022년 6월 20일
0

SCCC

목록 보기
15/18

수학적 귀납법

  • 자연수에 대한 명제 P(n)이 모든 자연수에 대해 성립함을 증명

    • (base case) P(n0)이 성립함을 증명
    • (inductive step) P(k)가 성립하면 P(k+1)이 성립함을 증명
    • (conclusion) n>=n0인 모든 정수 n에 대해 P(n)이 성립
  • 강한 수학적 귀납법

    • (base case) P(n0)이 성립
    • (inductive step) n<=k인 모든 n에 대해 P(n)이 성립하면 P(k+1)도 성립
    • (conclusion) n>=n0인 모든 정수 n에 대해 P(n)이 성립

분할 정복(Divide And Conquer)

큰 문제를 여러 개의 작은 문제로 쪼갠 다음(분할)
작은 문제들의 답을 이용해 큰 문제의 답을 구함(정복)

  • 동적 계획법(DP)와 차이점?
  • 분할 정복
    • 문제의 크기가 충분히 작은 경우 직접 해결
    • 문제의 크기가 큰 경우 k>=1개의 부분 문제로 쪼개서 각각 해결
  • 분할 정복의 시간 복잡도
    • T(N) = D(N) + sum T(i) + C(N)
    • N : 입력의 크기
    • T(N) : 입력의 크기가 N인 문제를 풀 때 걸리는 시간
    • D(N) : 크기가 N인 문제를 부분 문제로 분할할 때 걸리는 시간
    • C(N) : 크기가 N인 문제에서 부분 문제의 답을 합칠 때 걸리는 시간
  • 분할 정복의 예 : 병합 정렬
profile
Server Engineer

0개의 댓글