[이코테] chapter08 다이나믹 프로그래밍

오랜만에 백준 하나 풀려고 했더니 다이나믹 프로그래밍 문제이길래..! 돌아왔답니당

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

 

다이나믹 프로그래밍

: 효큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘.

(1) 다이나믹 프로그래밍 문제?

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

• 메모이제이션(Memoization): 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 그대로 가져오는 기법.
• 시간 복잡도: O(N)

(2) 다이나믹 프로그래밍 풀이 방식

▶️ Top-Down 방식

: 큰 문제를 해결하기 위해 작은 문제를 호출하는 문제

 

▶️ Bottom-Up 방식 (더 추천!)

: 작은 문제부터 차근차근 답을 도출하는 문제