다이나믹프로그래밍

[python] 프로그래머스 - 도둑질

🤔문제 해결 Lv4 | DP "인접한 집은 털 수 없다" 까지는 크게 어려운 문제가 아니지만 "마을이 원형으로 되어 있다" 에서 한번 더 생각하게 하는 문제!! -> 0번째 집을 터는 경우( 마지막 집을 털지 못한다 )와 0번째 집을 안터는 경우 두가지로 나눌 수 있다. 먼저 0번집을 털 경우! 0번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 0번집을 턴다. dp[0] = money[0] 1번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 1번집을 터는 경우지만 우리는 1번집을 반드시 털었다고 가정했으므로 인접한 2번집은 털 수 없다. dp[1] = 0 2번집에 들렀을 때: 인접한 1번집이 아닌 0번집 또는 -1번집(2번일 때는 없다) 중 돈을 많이 가져왔던 집에서 온다. dp[2] = money[i..

[python] 백준 - 11052. 카드 구매하기 / 16194. 카드 구매하기 2

🤔문제 해결 S1 | 다이나믹 프로그래밍 dp 리스트를 만든다. dp[i]: 카드 i장을 구매하기 위한 지불 금액의 최솟값 dp[0] = float('inf') (파이썬에서의 최댓값) dp[i-j] + dp[j]: 카드를 j장 구매하기 위한 최솟값과 카드를 i-j장 구매하기 위한 최솟값의 합 ex) dp[2] + dp[3]: 카드를 2장 구매하고 3장구매할 때의 최솟값 dp[i-j] + dp[j] 와 dp[i] 의 값을 비교하여 더 작은 값을 dp에 저장 테스트케이스 1번 예시 dp[0] = float('inf') dp[1] = 1 dp[2] = 5 | dp[2] = min(dp[2], dp[1]+dp[1]) | dp[2] = 2 dp[3] = 6 | dp[3] = min(dp[3], dp[2]+dp[1..

[python] 백준 - 2240. 자두나무

🤔문제 해결 S1 | 다이나믹프로그래밍 1. 답은 X초에 Y번 움직여서 먹은 최대의 자두 갯수! 변수가 2개이니 2차원 리스트를 만든다. 다른 분들의 답을 보면 자두(사람 헷갈림)의 위치까지 저장하여 3차원으로 만든다. 하지만 이동 횟수에 따라 자두(사람)의 위치는 저절로 정해진다. 홀수번 움직이면 2번 나무에, 짝수번 움직이면 1번 나무에 있다. 2. 행을 초(0~자두갯수) 열을 움직일 수 있는 횟수(0~W) 만큼 2차원 리스트를 만든다. dp의 0번째 행은 0초때, 0번째 열은 움직이지 않았을 때 3. %중요% (1) 받아 먹는 조건: a. i초에 자두가 1번에서 떨어지고 이동 횟수가 짝수(j % 2 == 0, 1번 나무에 위치)하면 b. i초에 자두가 2번에서 떨어지고 이동 횟수가 홀수(j % 2 ..

[python] 백준 - 9084. 동전

🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하여 만들 수 있으면 카운트를 세어준다. 4. 위의 표 처럼 각 동전을 꺼냈을 때 미리 만들어진 금액(인덱스)에 꺼낸 동전을 더해서 값을 쌓는다. 💨 다이나믹프로그래밍은 한번 해결한 문제는 다시 해결하지 않는다. 그리고 작은 문제를 해결하여 큰 문제를 해결한다는 의미!!!!!!!!! DP는 항상 어렵다.... 💻소스 코드 def _dp(): dp = [0] * (target + 1) # 경우의 수를 업데이트 할 리스트 dp[0] = 1 for coin in coins: # print('꺼낸 동전: ',c..

[python] 백준 - 11048. 이동하기

🤔문제 해결 1. DP | silver1 2. 주어진 2차원 배열보다 한칸씩 더 큰 0으로 채워진 배열을 만든다. (한칸씩 더 많은 이유는 가장 윗줄과 가장 왼쪽줄도 비교해주기 위해서) 3. 현재 지점의 값(maze)과 그 점 이전의 값들(왼쪽, 왼쪽위, 위)중 큰 값(dp)을 더해서 (dp에) 값을 계속 쌓아 준다. 💨 다이나믹프로그래밍 문제. BFS로도 간단히 풀 수 있지만 시간초과가 난다. 💻소스 코드 N, M = map(int, input().split()) maze = [list(map(int, input().split())) for _ in range(N)] # 가장 윗줄과 가장 왼쪽줄도 비교를 해줘야 하기 때문에 한칸씩 더해서 만들어준다. dp = [[0] * (M + 1) for _ in ..