[python] Computation Thinking

Computation Thinking

1. 기초 수식

1.1 문제 풀이

2. 재귀

  • 재귀란 자기 자신을 호출하는 함수, 그럼 끝날 수가 있는가?
  • 함수는 입력이 있으며, 자기 자신의 입력과 동일한 입력으로 자기 자신을 호출하면 당연히 끝나지않음
  • 하지만, 다른 입력으로 호출하면 끝날 수 있음

2.1 피보나치 수열

def fibo(n):
    if n <= 2:
        return 1
    return fibo(n-1) + fibo(n-2)

2.2 Merge Sort

크기 n인 배열을 입력으로 받아, 배열을 절반으로 두개로 나눈 후,

각 작은 배열을 재귀적으로 정렬하고,

그 결과를 Merge 한다.

2.3 소팅 성공 증명

Stupid (A[0..n-1])
{
    if n=2 and A[0] > A[1]
        then swap A[0] and A[1]
    else
        m = ceiling(2n/3)
        Stupid(A[0..m-1])
        Stupid(A[n-m..n-1])
        Stupid(A[0..m-1])
}

3. 동적 프로그래밍 (DP)

Dynamic Programming (동적계획법)이란?

  • 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말
  • 문제의 최적해를 구하거나, 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계기법
  • ex) 피보나치 수열

재귀 함수에서 동일한 입력의 함수 호출이 반복적으로 일어날 때 그 결과 값을 저장해 두고 불러 쓰는 것이다.

(Memoization)

최초 입력에서 파생되는 모든 가능한 입력에 대한 답을 모두 젖아할 수 있는 메모리가 있어야 한다.

단순히 재귀에서 저장된 값을 찾아보는 것으로도 가능하지만, 결과 값을 순서를 정해서 계산할 수도 있다. (동적계획법)

재귀, 메모이제이션, 동적계획법

3가지 방법중에

동적계획법 이 실행시간이 가장 빠르다.