99클럽 코테 스터디 23일차 TIL DP

DP; Dynamic Programming 동적 계획법

• 크기가 크거나 복잡한 문제를 효율적으로 풀기 위해 작거나 간단한 여러 개의 문제로 나눠서 푸는 방법
• 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 입력 크기가 작은 부분 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계 기법
• 프로그램 성능의 향상을 기대할 수 있음

 

• DP 알고리즘 구현 방식
  • 1. recursive 방식
  • 함수의 호출을 이용한 재귀적 방법
  • 재귀적 구조는 엄청난 중복 호출이 발생할 수 있으므로 내부에 시스템 호출 스택을 사용하는 overhead가 발생할 수 있음
    
  • 2. iterative 방식
  • 반복문을 이용한 반복적 방법
  • Memoization을 반복적 구조에 사용하여 DP 알고리즘을 구현하는 것이 위의 재귀적 구조에 비해 실행 속도와 성능 면에서 보다 효율적

728x90

느낀 점

• DP를 사용하면 완전 탐색보다 훨씬 유리할 것으로 보인다.
• 완벽히 이해하고 예제를 많이 풀어봐야겠다.

다음에 학습할 것

• 메모이제이션에 대하여
• DP 예제 풀어보기

반응형

---

DP 동적계획법에 대해 알아보았다. 중요한 개념이므로 확실히 알고 넘어가자.