Dynamic Programming (동적 계획법)

동적 계획법은 하나의 문제를 여러 개의 작은 부분 문제로 나누어 부분 문제의 답을 통해 원래 문제의 해답을 도출해내는 프로그래밍 기법이다. (큰 의미에서 분할정복과 비슷)

중복되는 연산의 수를 줄이면 시간 및 공간 복잡도를 줄일 수 있다

위의 아이디어가 동적 계획법의 핵심 아이디어이다.

주로 배열과 리스트를 통해 구현한다.

 

DP에서 부분 문제를 푸는 키포인트가 되는 것은 점화식이다.

 

점화식: 인접한 항들 사이의 관계식

 

※ DP 사용조건

   DP는 아무때나 사용할 수 있는 것이 아니고 아래와 같은 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다. (문제들의 답이 서로 영향을 미친다는 것이 분할정복과의 차이점)

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

 

 ※ DP 사용방법

    DP 사용방법에는 탑다운 방식과 보텀업 방식 두가지가 있다.

 

  1. 탑다운 방식(Top-Down) - 큰 문제를 해결하기 위해 작은 문제 호출

• 재귀함수를 통해 구현
• 하향식
• 메모이제이션 사용 

메모이제이션: 한 번 구한 결과를 저장했다가 같은 식을 다시 호출했을 때 저장된 값을 가져와서 사용하는 기법

 

  2. 보텀업 방식(Bottom-Up) - 작은 문제부터 차근차근 답을 도출 

• 반복문을 통해 구현
• 상향식
• DP 테이블 사용

"이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)"를 보고 정리한 내용

 

출처| 이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)