다이나믹 프로그래밍(DP) 을 배웠다.

Top-down 으로 피보나치 수열을 보통 가장 기본적인 예시로 들어, Bottom-up 방식과 함께 기본 틀을 익혔다.

DP 는 하위 부분에서 최적의 풀이가 합쳐져서 최종 큰 단위의 최적의 답으로 연결되는 점에 현업과 그래도 가장 밀접한 알고리즘 풀이 방식에 가깝다고 한다.

dp table 로 접근하는 구조로 코드 짜는 연습도 계속 필요하고, 완전 탐색과 비슷한 느낌이라 DP 를 명확히 정의하기도 애매한 부분이 있다고 한다. 결국 케이스를 많이 익히기💡

Top-down vs Bottom-up

# Top-down
# 1) 재귀적인 방법 2) 메모리를 사용함(딕셔너리에 저장해 나감)으로써 시간복잡도를 낮춤
# (저장한 key 가 있으면 패쓰~ 없는 경우 추가하면서 진행하니까)

memo = {}
def fibo(n):
    if n == 1 or n == 2:
        return 1
    if n not in memo:
        memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

print(fibo(5)) # 5
print(fibo(10)) # 55
print(memo) # n=10 -> {3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55}

# 시간복잡도 : O(n)

# Bottom-up
# base case 부터 시작해서 반복문(for) 을 통해 돌면서 계산해 나가는 형식

memo = {1: 1, 2: 1} # base case
def fibo(n):
    for i in range(3, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

항해99

#개발자포트폴리오 #개발자이력서 #개발자취업 #개발자취준 #코딩테스트 #항해99 #취리코 #취업리부트코스