알고리즘/동적프로그래밍(DP)42

• 

  [Python] 백준 9461번: 파도반 수열 풀이 소스코드 T = int(input()) P = [0 for i in range(101)] P[1] = 1 P[2] = 1 P[3] = 1 P[4] = 2 P[5] = 2 for i in range(T) : n = int(input()) for j in range(6,n+1) : P[j] = P[j-1] + P[j-5] print(P[n]) 주어진 그림을 보면, 3 = 2 + 1 4 = 3 + 1 5 = 4 + 1 7 = 5 + 2 9 = 7 + 2 임을 알 수 있다. 즉, P[6]번 째부터 P[n] = P[n-1] + P[n-5] 가 성립함을 알 수 있다. 알고리즘/동적프로그래밍(DP) 2021. 2. 3.

• 

  [Python] 백준 2133번: 타일 채우기 풀이 소스코드 n = int(input()) dp = [0 for _ in range(31)] dp[2] = 3 for i in range(4,n+1) : if i%2 == 0 : dp[i] = dp[i-2] * 3 + sum(dp[:i-2]) * 2 + 2 else : dp[i] = 0 print(dp[n]) 이전에 풀었던 타일 문제보다 어려워서 꽤 고생한 문제이다. 풀이는 위와 같다. 1) n에 대해서 n-2 까지의 dp 값에 가로길이 2 짜리 타일로 만들수 있는 3가지 경우를 곱한 경우 -> dp[n-2] * 3 2) n에 대해서 0 ~ n-4 까지의 타일 뒤에 자신을 붙혀서 만들 수 있는 2가지 경우를 곱한 경우 -> ( dp[0] + dp[2] + ... dp[n-4] ) * 2 3) n에 대해서 가.. 알고리즘/동적프로그래밍(DP) 2021. 1. 26.

• 

  [Python] 백준 1699번: 제곱수의 합 풀이 소스코드 n = int(input()) dp = [x for x in range (n+1)] for i in range(1,n+1): for j in range(1,i): if j*j > i : break if dp[i] > dp[i-j*j] + 1 : dp[i] = dp[i-j*j] + 1 print(dp[n]) dp값을 1부터 n까지 하나씩 갱신해가는 방법이다. 즉 작은 방법부터 해결해 나가는 전형적인 DP문제이다. i로 1부터 n까지 돌면서, j는 1부터 i-1까지의 수 중 제곱한 값이 i보다 크지 않아야 한다. dp[i] > dp[i-j*j] + 1 이 수식은 제곱수로 표현할 때 가장 항의 개수가 작은 j 를 찾는 것이다. *즉, 예를 들어 dp[6] = dp[6 - 2*2] + 1 = dp[2].. 알고리즘/동적프로그래밍(DP) 2021. 1. 26.

• 

  [Python] 백준 2579번: 계단 오르기 풀이 소스코드 1 n = int(input()) A = [[0] for _ in range(n)] dp = [[0]* 3 for _ in range (n)] for k in range(n): A[k] = int(input()) dp[0][1] = A[0] for i in range(1,n) : dp[i][0] = max(dp[i-1][1],dp[i-1][2]) dp[i][1] = dp[i-1][0] + A[i] dp[i][2] = dp[i-1][1] + A[i] print(max(dp[n-1][1], dp[n-1][2])) 저번에 풀었던 와인 문제와 비슷한 원리이다. 각 계단에 대해서 연속으로 0번 밟았을 때, 연속 1번 밟았을 때, 연속 2번 밟았을 때 총 3가지 경우로 나눠보았다. 이렇게 2차원 배열을 이.. 알고리즘/동적프로그래밍(DP) 2021. 1. 25.

• 

  [Python] 백준 1912번: 연속합 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [x for x in A] for i in range(1,n): dp[i] = max(dp[i-1] + A[i], dp[i]) print(max(dp)) 처음에는 이중 for 문으로 풀었는데, 시간 초과가 나와서 '아 이렇게 푸는게 아니구나' 하는 생각에 싹 갈아엎었다. 다시 생각해보니 매우 간단했다. 그냥 한 칸 이전의 dp값이랑 자신의 수랑 더하는게 큰지, 그냥 안더하고 놔두는게 큰지 비교하기만 하면 된다. 그래서 시간복잡도가 O(n) 으로 매우 간단하다. 알고리즘/동적프로그래밍(DP) 2021. 1. 25.

• 

  [Python] 백준 11054번: 가장 긴 바이토닉 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) increase = [1] * n decrease = [1] * n result = [0] * n #increase for i in range(n): for j in range(i): if A[i] > A[j] : increase[i] = max(increase[i], increase[j]+1) #decrease for i in range(n-1,-1, -1): for j in range(i+1,n): if A[i] > A[j] : decrease[i] = max(decrease[i], decrease[j]+1) result[i] = increase[i] + decrease[i] - 1 print(ma.. 알고리즘/동적프로그래밍(DP) 2021. 1. 25.

• 

  [Python] 백준 11722번: 가장 긴 감소하는 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(i): if A[i] < A[j] : dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) 가장 긴 증가하는 수열과 같은 논리의 문제라서 쉽게 풀었다. dp는 1로 초기화해놓고, 이중 for문을 이용해 i번째(현재 위치) 수와 0부터 i-1까지의 수(j) 를 비교하면서 만약 앞에 있는 수가 i보다 더 클 때, 그 때의 dp값은 j의 dp보다 1 큰 값이 될 수 있다. 알고리즘/동적프로그래밍(DP) 2021. 1. 25.

• 

  [Python] 백준 11055번: 가장 큰 증가 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [x for x in A] for i in range(n): for j in range(i): if A[i] > A[j]: dp[i] = max(dp[i], dp[j] + A[i]) print(max(dp)) 휴.. 풀이를 시작하기 전에 한 가지만 짚고 가자... 파이썬 문법을 제대로 알지 않고 무작정 알고리즘을 풀다 보니 오늘 그 쓴맛을 제대로 느꼈다.... dp = A 이렇게 하면 dp가 A를 참고하게 되어, 서로의 값에 영향을 주고 받는 다는 것을 몰랐던 나는 수십번 코드를 고쳤다 말았다 난리를 쳤다......... 휴!!! 그래도 새로운 거 알았으니 됐다.ㅎㅎㅎㅎ 앞으로 파이썬에서 li.. 알고리즘/동적프로그래밍(DP) 2021. 1. 23.

• 

  [Python] 백준 11053번: 가장 긴 증가하는 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [1] * n for i in range(1,n): for j in range(i): if A[i] > A[j]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) DP를 이용하면 나름 쉽게 풀 수 있는 문제이다. 주어진 수열이 있을 때 예) 1 100 2 3 4 200 300 400 500 6 가장 긴 부분 수열을 찾으면 된다. 이중 for문을 이용해 j는 0~i-1까지 돌면서 A[i] 랑 A[j] 를 비교하는 것이다. 즉, i보다 앞에 있는 수 중에 A[i] 보다 작다면, dp값을 비교한다. 만약 지금 i가 200에 있다고 하자. dp[4] = 1 2 3 4 로 .. 알고리즘/동적프로그래밍(DP) 2021. 1. 23.

• 

  [Python] 백준 2156번: 포도주 시식 풀이 소스코드 n = int(input()) wine = [] dp = [[0] * 3 for _ in range(n)] for i in range(n): wine.append(int(input())) dp[0][1] = wine[0] for i in range(1,n): dp[i][0] = max(dp[i-1]) dp[i][1] = dp[i-1][0] + wine[i] dp[i][2] = dp[i-1][1] + wine[i] print(max(dp[n-1])) n 이 1일때를 고려해주지 않아 계속 런타임 에러가 난 문제... 휴! 연속으로 와인 3잔을 먹지 못하는 것을 힌트로 문제를 풀어나가면 된다. dp[i][j] 는 i번째 와인을 먹을 때, 최대로 마실 수 있는 포도주의 양을 저장한 것이다. i는 0부터.. 알고리즘/동적프로그래밍(DP) 2021. 1. 22.

• 

  [Python] 백준 9465번: 스티커 풀이 소스코드 T = int(input()) for _ in range(T): n = int(input()) dp = [list(map(int, input().split())) for _ in range(2)] dp[0][1] += dp[1][0] dp[1][1] += dp[0][0] for i in range(2,n): dp[0][i] += max(dp[1][i-1], dp[1][i-2]) dp[1][i] += max(dp[0][i-1], dp[0][i-2]) print(max(dp[0][n-1], dp[1][n-1])) 그림으로 예를 들겠다. dp[0][3] 이 최대가 되려면 dp[1][2] 를 선택하거나 dp[1][1] 을 선택해야 한다. dp[1][1] 을 선택시 그 오른쪽옆인 dp[1][2] 는 당연.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 2193번: 이친수 풀이 소스코드 n = int(input()) # dp 초기화 #dp[i][j] 에서 i는 자리수, j는 끝에 오는 수 dp = [[0]*2 for _ in range(n+1)] dp[1][1] = 1 for i in range(2, n+1): dp[i][0] = sum(dp[i-1]) dp[i][1] = dp[i-1][0] print(sum(dp[n])) 1자리 -> 1 (1가지) 2자리 -> 10 (1가지) 3자리 -> 101, 100 (2가지) 이번 문제도 마찬가지로 수의 끝자리에 따라 케이스를 나눌 수 있다. dp[i][0] 은 i자리수에서 0으로 끝나는 이친수의 개수이다. dp[i][1] 은 i자리수에서 1로 끝나는 이친수의 개수이다. dp[i] 는 dp[i][0] + dp[i][1] 로 정의할 수 있.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.