※뱀표_코딩※

dynamic programming

• [Python][백준] 2579번 계단 오르기 풀이 | DP는 정말 어려워

  Algorithm/백준 2022. 3. 24. 10:00

  점화식 유도 dp는 점화식 유도하는게 제일 머리 아프다 난 머리가 나빠서 이런 문제 하나 걸리면 정말 스트레스 받는다 하지만 풀면 그만큼 통쾌한것도 없다 dp[1] = step[1] dp[2] = step[1] + step[2] for x in range(3, m+1): dp[x] = max(dp[x-2], dp[x-3] + step[x-1]) + step[x] 굳

  Read More
• [Python][백준] 백준 1463번 1로 만들기 풀이 | DP와 Divide and conquer

  Algorithm/백준 2022. 2. 25. 19:51

  DP(Dynamic Programming) 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. Divide and conquer와는 다르다! Divide and conquer는 큰 문제를 작은 단위로 나누어 해결한 다음 합치는 알고리즘이다. (예시 merge sort) 오늘은 DP를 이용하여 푸는 백준 1463번의 코드를 공유하겠다. # DP를 이용한 풀이 n = int(input()) dp = [0] * max(4, n+1) dp[2], dp[3] = 1, 1 for i in range(4, n+1): temp1 = dp[i//3] if i % 3 == 0 else float("inf") temp2 = dp[i//2] if i % 2 == 0 else float("inf") dp[i] = min(temp..

  Read More