[Python] 파이썬 다이나믹(동적) 프로그래밍 구현, 관련 문제 모음

🚜 Dynamic Programming을 사용하는 문제

Dynamic Programming은 입력 크기가 작은 부분 문제 해결 후, 해당 부분의 해를 이용해서 보다 큰 문제를 해결하는 방법입니다. memorization 기법(이전 실행에서 구한 해를 저장해둠)을 사용합니다. 아래는 가장 기본적인 dp 문제 리스트 입니다.

• 평범한 배낭 (백준 12865)
• 가장 긴 증가하는 부분 수열 (백준 11053)
• LCS, 두 수열에서 공통된 가장 긴 수열의 길이 구하기 (백준 9251)
• 기타리스트 (백준 1495)
• 가장 높은 탑 쌓기 (백준 2655)
• 프로그래머스 level2. 가장 큰 정사각형 찾기

 

🚚 풀이 방법 특징

✅ 사용되는 문제 유형 : 작은 값부터 구할 수 있는 문제. 즉, 값을 하나하나 쌓거나 채워가는 문제

• dp라는 일차원 배열 또는 이차원 배열에 순차적으로 실행한 값들을 채워 넣으면서 진행한다.
• 사용할 dp의 크기와 시간 복잡도가 한정적이다
• 사용할 dp를 미리 일차원 배열 또는 이차원 배열로 정의해 두고 시작한다.
• 2중 for문을 사용한다.
• 대부분 겉 for문은 차례대로 받은 값(i), 속 for문은 내가 이전에 구한 해 중 해당 값(j)를 의미한다.
• max(,) 비교가 필요한 경우가 있다. (대부분 이전 시행해와 새롭게 구한 해를 비교할 때 사용한다)
• dp의 크기가 한정적이지 않다면 메모리 초과할 가능성이 크다 -> 모든 경우에 대하여 T/F로 나타내는 등의 다른 방식을 생각해보자
• dp에 저장되는 값은 구하려는 해이다.