강의 자료(https://www.slideshare.net/InseoPark1/dynamic-programming-step-by-step)

1. Dynamic Programming이란?

  • 한국어로는 동적 계획법
  • 사실 그냥 멋있어서 붙인 이름
  • 문제를 작은 문제로 나누는 것에서 출발

2. 문제

  • 문제를 푸는법
    • 문제를 나눈다.
    • 문제를 푼다.
    • 결과를 합친다.
      => Divide And Conquer (분할 정복)
    • Memoization : 동일한 계산을 반복해야 할 때, 이전 계산 값을 저장함으로써 빠르게 계산하는 방법
      • Dynamic Programming 에서 핵심이 되는 기술
    • 예시
      • 피보나치 함수 ( f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1 )
      • 기본 정의에 의한 Fibonacci 구현

        => 중복이 많이 발생
        => 중복에 대한 결과를 미리 저장한다면
        => Memoization(메모이제이션)!

  • 이항계수

  • 구간합 구하기
  • 2차원 구간합

3. 실제 문제 풀이

  • 백준 2748 - 피보나치 수 2              풀어보세요
  • 백준 11051 - 이항계수                    풀어보세요
  • 백준 11659 - 구간합 구하기 4         풀어보세요
  • 백준 11660 - 구간합 구하기 5         풀어보세요
Retrieved from http://wiki.zeropage.org/wiki.php/데블스캠프2017/DynamicProgramming:StepByStep
last modified 2021-02-07 05:29:18