Dynamic programming

'''
DP(동적 계획법): 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여, 다시 계산하지 않도록 함
일반적으로 TOP DOWN(하향식)/BOTTOM UP(상향식-전형적임) 방법이 있음

동적: 프로그램이 실행되는 도중에~

조건
1. 최적 부분 구조(OPTIMAL SUBSTRUCTURE): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
2. 중복되는 부분 문제(OVERLAPPING SUBPROBLEM): 동일한 작은문제를 반복적으로 해결해야함 ex) 피보나치의 f(5)일때, f(2)가 2번 불러지는 것을 알 수 있음
'''

# 피보나치
# 수열 = SEQUENCE
def fibonachi(x):
    if x==1 or x == 2:
        return 1
    return fibonachi(x-1) + fibonachi(x-2)

'''
* memoization (하향식) - 재귀함수를 호출함
- 한번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면, 메모했던 결과를 그대로 가져옴
- 값을 기록해 놓는다는 점에서 "캐싱"이라고도 함
- 따라서 배열의 이름을 비슷하게, cache, dp, d, table, memo
- 값을 기록만 하고, 굳이 쓰지 않아도 dp라고함
'''

# TOPDOWN (하향식)
# memo - 한 번 계산된 결과 모아놓는 리스트
d = [0] * 100
def fibo(x):
    # 재귀함수 필수: 종료 조건
    if x == 1 or x ==2:
        return 1

    # 이미 계산되어 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]

    # 계산되어 있지 않다면, 피보나치 결과 반환
    d[x]  = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(10))
print(d)

# BOTTOM UP - 반복문 사용
# 모든 피보나치의 수를 사용옴
# 각각의 항의 값을 먼저 해결해 놓은 문제들을 조합해서 큰 문제를 품
d = [0] * 100

d[1] = 1
d[2] = 1
n=10
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])

'''
동작 분석
분할정복 ex) quick 정렬 (small < pivot < big)
- 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않습니다.
(pivot 은 다시 새롭게 정해져서, dp가 아님)

# tip
- dp 문제인지 먼저 파악하는 게 필요함!
- 그리디/구현/완전탐색 아이디어로 문제를 해결할 수 있는지 검토
- 작은 문제 -> 큰 문제풀 수 있을지 문제 접근
- 완전 탐색 프로그램을 작성한 뒤, 작은 문제에서 답이 큰 문제에서 다시 사용될 수 있으면 코드 개선!
- 일반적으로, 기본 유형으로 다이내믹 프로그래밍 문제가 출제되는 경우가 많음
- 오프라인에서는 쉬운 문제로 나옴
'''