💪 Today I Learned

BOJ

이것이 취업을 위한 코딩테스트다

Dynamic Programming

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

  • Top-down
    • memoization 기법
    • 한 번 구한 결과를 메모리 공간에 저장해두고, 같은 식을 다시 호출할 때 저장해둔 결과를 그대로 가져온다.
  • Bottom-up
    • DP-table 사용
    • 작은 문제부터 답을 도출해나간다.

🏃 한마디

DP 문제는 점화식을 잘 세워서 풀어야 하는데 그 과정이 생각보다 까다롭다.