ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • DP
    알고리즘 2020. 3. 16. 19:34

    DP (Dynamic Programming) 동적계획법

    • 개념 : 큰 문제를 작은 문제로 나누어서 푸는 문제
    • 작은 문제들을 계산한 값을 여러 번 사용하기 때문에 Memoization (메모이제이션)이 필요하다.

       Memoization?

       컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해,

       매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술

     

      → 즉, 계산된 결과를 배열에 저장한 뒤, 다음 계산에서 필요하면 저장된 값을 불러옴. 시간 복잡도가 훨씬 줄어든다.


    • 구현 방식 : Bottom-up 방식과 Top-down 방식
    1. Bottom-up 방식 : 작은 문제부터 계산해 나가는 방식, for문 이용해서 처음 값부터 다음 값을 계산해 나가는 방식
    2. Top-down 방식 : 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그 때 푸는 방식, 일반 재귀와 같은 방식
      Bottom-up Top-down
    장점 함수를 호출하지 않으므로, 시간과 메모리를 소량 절약할 수 있다. 점화식 그대로 호출되기에, 소스의 가독성이 좋다.
    단점 소스의 가독성이 저하된다. 작성하기에 조금 더 어렵다.

        문제에 따라 자신에게 맞는 방식으로 풀면 된다.

    '알고리즘' 카테고리의 다른 글

    Greedy Algorithm  (0) 2020.03.17
    Floyd-Warshall  (0) 2020.03.17
    Dijkstra  (0) 2020.03.17
    Binary Serach  (0) 2020.03.16
    DFS & BFS  (0) 2020.03.16

    댓글

Designed by Tistory.