DP만 보면 화가 나는 사람PS2023. 11. 8. 00:52
Table of Contents
이번주 동아리 PS 주제가 DP인데, 이놈의 DP는 1년 전에 할 때고 지금이고 보면 일단 화가 난다.
기왕 이렇게 된거 DP를 때려잡아보자.
이코테 DP부분을 읽다보니, 1학기 알고리즘 시간에 학습한 DP의 대원칙이 생각난다.
0. "완전탐색으로 풀면 ㅈ되겠는데?"
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
이러한 조건을 만족할 때, DP를 적용하는 것이었다.
DP 문제를 풀어나가는 방법은 다음과 같다. (https://stonejjun.tistory.com/23)
1. 문제를 잘 탐색해본다.(숫자를 때려넣어 보고, 패턴을 찾아보자...)
2. 점화식(DP식)을 세운다.
3. 검증해보고, 구현한다.
그리고, DP 문제를 해결할 때 메모이제이션 이라는 방법을 사용하기도 한다.
: 작은 문제의 실행 결과를 기록해 둘 무언가를 만들어서 기록해두고, 더 큰 문제를 풀 때 기록해둔 것을 참고한다.
그리고, 다음과 같은 일반적 특징이 있다.
- 일반적으로 Top-Down 방식(재귀함수) 보다는 Bottom-Up(반복문)을 이용한 DP가 성능이 더 좋다.
왜냐하면 재귀함수 호출 시 메모리 오버헤드가 발생할 수 있기 때문.
이제 문제를 풀어보자.
+추가
DP에서 Top-Down 방식을 구현하기 위해 재귀함수를 써야하는 경우,
import sys
sys.setrecursionlimit(10 ** 6)
를 상단에 써주어 재귀 깊이 제한을 늘려주자. 기본은 1000이다.
@찐빵1 :: 위기주도학습
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!