DP

[python] SWEA - 3282. 0/1 Knapsack

🤔문제 해결 D3 | DP( Knapsack ) 💨 냅색알고리즘 💨 각 아이템에 대해서 가방의 크기를 0부터 1씩 최대무게까지 늘려가며 계산. 💨 가방의 크기가 해당 아이템의 무게보다 작으면 아이템을 넣지 못한다. 이전까지의 무게와 가치 적용 💨 가방의 크기가 해당 아이템의 무게보다 크면 아이템을 넣을지 말지 선택한다. 💨💨 이전까지의 무게와 가치 vs (이전까지의 무게 - 현재 아이템의 무게)의 가치 + 현재 아이템의 가치 💻소스 코드 # 입력 T = int(input()) Ns = [] for tc in range(T): N, K = map(int, input().split()) items = [list(map(int, input().split())) for _ in range(N)] Ns.appen..

[python] 백준 - 14501. 퇴사

🤔문제 해결 S4 | 완전탐색 or DP 난이도가 S4인 만큼 완전탐색으로 해결해도 된다. 하지만 저번에 한번 풀어봤으므로 이번에는 DP로 해결해봤다. 일하는 날을 맨 뒤에서부터 계산해보자 7일을 선택하면 근무시간 초과로 이익 0 6일도 마찬가지 5일을 선택하면 이익 15 4일을 선택하면 이익은 20에, 5일에도 일할 수 있으므로 +15 해서 35 3일을 선택하면 이익은 10에 4일에도 일할 수 있으므로 (4일에 일하면 위에서 확인했듯이 5일도 일한다) +35 이므로 45 2일을 선택하면 이익은 20 1일을 선택하면 이익은 10에 4일부터 일할 수 있으므로 ( 아까 그 35 를 더한다) +35 이므로 45 결과적으로 1,4,5 일하면 45 또는 3,4,5 일하면 45 이 두가지의 경우가 최대이다. 한가지..

[python] 백준 - 12865. 평범한 배낭

🤔문제 해결 G5 | DP, 냅색 알고리즘(배낭 알고리즘) 딱 봐도 너무 복잡해 보이는 DP... 2차원 배열로 풀어야할 것 같다. 행은 각 아이템, 열은 현재 무게(?) 아이템 하나를 고른다. 가방의 버틸 수 있는 무게를 0부터 M까지 올려본다. 해당 무게별로 최대로 채울 수 있는 가장 큰 값을 채운다. 사실 그렇게 딱!!! 완전히 이해는 하지 못했다... 역시 DP는 어려움 나중에 비슷한 문제를 한번 더 풀면 이해가 가지 않을까... 💻소스 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) # 물품 수, 최대 무게 items = [tuple(map(int, input().split())) for _ in range(N)..

[python] 백준 - 1965. 상자 넣기

🤔문제 해결 S2 | DP [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com 위의 문제와 살짝 비슷한 느낌이다. 값이 1로 셋팅된 길이가 n 인 dp 리스트를 만든다. dp = [1, 1, 1, ... ] 각각의 값은 현재 포함한 상자의 갯수이다. 맨앞의 상자부터 하나씩 뒤로가며 앞의 상자를 몇개나 담을 수 있는 지 체크한다. 만약 내앞의 상자가 나보다 작고 그 상자가 담고 있는 상자의 갯수(본인포함)가 5개라면 지금 나의 상자는 앞의 상자까지 담을 수 있으..

[python] 백준 - 1890. 점프

🤔문제 해결 S2 | DP DFS로 해봤지만 역시나 시간초과!! 시간복잡도가 O(N^2) 인 DP로 풀어봤다. dp에는 현재 위치까지 올 수 있는 경우의 수를 담아서 해결함. 💻소스 코드 N = int(input()) field = [list(map(int, input().split())) for _ in range(N)] answer = 0 dp = [[0] * N for _ in range(N)] # i,j까지 올 수 있는 경우의 수를 저장 dp[0][0] = 1 for i in range(N): for j in range(N): if i == N - 1 and j == N - 1: # 끝에 도달했을 때 print(dp[i][j]) break cur_cnt = field[i][j] # 오른쪽으로 가기..

[python] 백준 - 2133. 타일 채우기

🤔문제 해결 S2 | DP 이런문제는 역시 단골 DP문제 일단 손으로 구해봤다. i == 0, 2, 4, 6 ( 홀수 일 경우는 제외함 ) 경우의수 == 1, 3, 11, 41 점화식 dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2 i경우의수 = 이전의 경우의 수 * 3 + 이전의 경우의 수 들 * 2 + i만 만드는 경우 💻소스 코드 N = int(input()) if N % 2: print(0) else: dp = [0] * (N + 1) dp[0], dp[2] = 1, 3 for i in range(4, N + 1, 2): dp[i] = dp[i - 2] * 3 + 2 for j in range(2, i - 2, 2): dp[i] += dp[j] * 2 prin..