DP

각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 인접한 집들이 같은 색이 되지 않도록 하면서 모든 집을 칠하는 최소 비용을 구하는 문제-> DP 테이블을 2차원 리스트로 정의하여 풀 수 있다. 풀이동적 프로그래밍 테이블 정의:dp[i][j]: i번째 집을 j색으로 칠하는 최소 비용 (j = 0: 빨강, 1: 초록, 2: 파랑)점화식 설정:dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]) (i번째 집을 빨강으로 칠하는 경우)dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]) (i번째 집을 초록으로 칠하는 경우)dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]) (i번째 ..

문제 설명자연수 ( n )이 주어질 때, ( n )을 최소 개수의 제곱수 합으로 표현하는 방법을 찾는 프로그램을 작성하는 문제이다. 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 예를 들어, 26은 ( 5^2 + 1^2 )로 표현할 수 있고, ( 4^2 + 3^2 + 1^2 )로도 표현할 수 있다. 이 문제에서는 ( n )을 최소 개수의 제곱수 합으로 표현할 때 그 최소 개수를 구해야 한다. 풀이 설명이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있다. def min_squares(n): # dp[i]는 i를 최소 개수의 제곱수 합으로 표현하는 방법의 개수를 저장 dp = [float('inf')] *..

주어진 삼각형 그림을 보면, 작은 삼각형의 합으로 다음 삼각형이 채워진다.-> DP 주어진 그림을 그려보며 생각해보면, 점화식을 어렵지 않게 찾을 수 있다.N12345678P(N)11122345P(8) = P(7) + P(3)P(7) = P(6) + P(2)P(6) = P(5) + P(1-> P(N) = P(N-1) + P(N-5)이다. 풀이dp = [0] * 101dp[1] = dp[2] = dp[3] = 1dp[4] = dp[5] = 2for i in range(6, 101): dp[i] = dp[i-1] + dp[i-5]t = int(input()) # 테스트 케이스 개수for _ in range(t): n = int(input()) print(dp[n])

문제 요약각 계단에는 일정한 점수가 쓰여 있음 - 그 점수 얻음1. 한 계단 / 두 계단씩 오를 수 있다2. 연속된 세 개의 계단은 모두 밟아서는 안 된다3. 마지막 도착 계단은 반드시 밟아야 한다각 계단에 쓰여 있는 점수가 주어질 때 총 점수의 최댓값  풀이DP로 풀 수 있다. '마지막 도착 계단은 반드시 밟아야 한다' 라는 조건 -> 도착지부터 생각하는 접근이 더 쉽다. n번째 계단에 올라오기 위해서는 두 가지 경우가 있다.1. n-1번째 계단에서 오는 경우dp[n] = dp[n-3] + stairs[n-1] + stairs[n]2. n-2번째 계단에서 오는 경우dp[n] = dp[n-2] + stairs[n]-> 이 중에서 더 큰 수가 dp[n]이 된다. dp[n-3]이 있기 때문에 1, 2, 3번..

2×n 크기의 직사각형을 채우는 방법의 수 n이 1일 때는 1, n이 2일 때는 가로 두개, 세로 두개로 2가지 ( =, || )n이 3일 때는 n이 2일 때 + n이 1일 때n이 4일 때는 n이 3일 때 + n이 2일 때-> 점화식 : 직사각형 가로의 길이가 N인 경우는 n-1 경우의 수 + n-2 경우의 수를 더한 값 n = int(input())def tiling(n): if n == 1: return 1 if n == 2: return 2 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2]) % 10007 ..

동적 프로그래밍(Dynamic Programming)을 사용하여 0과 1로 이루어진 특정 수열을 생성하고, 주어진 수열의 각 숫자들 중 0과 1의 개수를 구할 수 있다. 피보나치 n에서 0 호출횟수 = (피보나치 n-1에서 0 호출횟수) + (피보나치 n-2에서 0 호출 횟수)피보나치 n에서 1 호출횟수 = (피보나치 n-1에서 1 호출횟수) + (피보나치 n-2에서 1 호출 횟수)이므로  점화식count_zero[i] = count_zero[i-1] + count_zero[i-2]count_one[i] = count_one[i-1] + count_one[i-2]이런 점화식을 생각할 수 있다. t = int(input()) # 테스트 케이스의 수 입력def count_ways(n): count_z..

풀이 1: DP이 문제를 위한 가장 효율적인 방법은 DP를 사용하는 것이다.  초기값초기값 dp[1] = 1, dp[2] = 2, dp[3] = 4(dp[2]는 1+1, 2로 2가지, p[3]은 1+1+1, 1+2, 2+1, 3으로 4가지) 점화식4일 때 dp[3]+1, dp[2]+2, dp[1]+3와 같이 구할 수 있다. --> n은 dp[n-1]+3, dp[n-2]+2, dp[n-3]+3--> 방법의 수 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 1, 2, 3의 합으로 나타내는 방법의 수에서 한 번 계산한 값을 재사용함으로써 중복 계산을 방지하고, 시간 복잡도를 줄일 수 있다.def count_ways(n): # n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장..

subproblem 중복, 반복연산 많음 -> DP 풀이1 (Bottom-up)n = int(input())dp = [0] * (n+1)for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i//3]+1, dp[i]) if i % 2 == 0: dp[i] = min(dp[i//2]+1, dp[i]) print(i, ": ", dp[i])if n  풀이2 (Top-Down) - Recursion Errordef min_operations(n, dp): if n 0: # 이미 계산된 값이 있다면 그 값을 반환 return dp[n] dp[n] = mi..

겹치는 하위 문제(Subproblem)를 해결하고 그 결과를 저장해 나가는 방식으로 최적화 문제들 특징1. 작은 하위문제들이 반복적으로 발생하며, 이들의 해결 결과가 재활용될 수 있을 때 2. Optimal Substructure(최적부분구조)을 갖춘 문제. 큰 문제의 최적해가 작은 문제의 최적해를 통해 구할 수 있을 때 3. 중복된 계산을 최소화할 수 있는 구조. 같은 하위 문제를 반복해서 해결해야 할 때 하위문제가 독립적, 줄여가면서 해결 -> Divide & Conquer 하위문제가 중첩됨, 반복해야 함 -> Dynamic Programming DP로 해결하는 대표적인 문제들longest common subsequenceKnapsack problemRod cutting problemshortest ..