DP

이 문제는 이것이 코딩테스트다 223페이지 문제이다. 아래는 나의 코드이다. import sys N= int(sys.stdin.readline().rstrip()) dp=[0]*1001 dp[0]=0 dp[1]=1 dp[2]=3 for i in range(3,N+1): dp[i]=dp[i-1]+ 2*dp[i-2] print(dp[N]%796796) 아래는 예시코드이다. # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[..

다이나믹프로그래밍의 정의 및 장단점 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. '기억하며 풀기'라고 부르기도 한다. DP를 쓰는 이유 왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번..

이것이 코딩테스트다. 220페이지 문제이다. 스키장 3,5,7일권 최저가 구하기 문제와 비슷하다. 다이나믹프로그래밍의 정석 문제 같다. 다이나믹 프로그래밍은 보통 min(나올수있는 경우들) 또는 max(나올 수 있는 경우들)을 이용한다. 이 문제는 바텀업방식문제이다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) food = list(map(int,sys.stdin.readline().split())) dp=[0]*N dp[0]=food[0] dp[1]=max(food[0],food[1]) for i in range(2,N): dp[i] = max(dp[i-2]+food[i],dp[i-1]) print(dp) print(dp[N-1]) 아래는..

이 문제는 이것이 코딩테스트다. 217페이지 문제이다. 문제 난이도는 높지 않았다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) dp=[0]*(N+1) dp[1]=0 dp[2]=1 for i in range(2,N+1): temp = [N] * 4 if i%5 == 0: temp[0] = dp[i//5] + 1 if i%3 == 0: temp[1] = dp[i//3] + 1 if i%2 == 0: temp[2] = dp[i//2] + 1 temp[3]=dp[i-1]+1 dp[i]=min(temp) print(dp[N]) 아래는 예시코드 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 ..