백준/DP 다이나믹 프로그래밍
-
2186 문자판백준/DP 다이나믹 프로그래밍 2024. 8. 27. 22:18
dp 와 dfs 를 이용한다. 거꾸로 찾아나가는 방식이다.BREAK 이 문자를 찾아나가야 할 때, dp[1][2][3] = 위치(1,2) 에서 시작된 문자로 BREAK 문자열의 3번째 부터 끝 문자열까지 완성할 수 있는 경우의 수이다.즉, AK 를 완성할 수 있는 경우의 수로, KAKT XEAS YRWU ZBQP 위치 (1,2) 의 문자열 = A인데,여기에서 좌,우,위, 아래로 움직여서 K가 있는 경우를 찾아보면 한 가지 경우를 찾을 수 있다.때문에 dp[1][2][3] = 1 이다. (1) 코드 설명 KAKT XEAS YRWU ZBQP 1) BREAK에서 맨 처음 문자 B가 있는 위치(3,1)에서 dfs가 시작한다. =============================== KAKTXEASYRWU..
-
1135 뉴스 전하기백준/DP 다이나믹 프로그래밍 2024. 8. 23. 13:18
예제를 가지고 설명하자면, 5-1 0 0 2 2 다음과 같은 상황을 생각할 수 있다.즉 민식이가 (루트 노트 0) 부하직원에게 연락을 하는데(단, 직원들에게 동시에 연락할 수 없음) 1초 : 0번 노드 -> 2번 노드 직원2초 : 0번 노드 -> 1번 노드 직원, 2번 노드 -> 3번 노드 3초 : 2번 노드 -> 4번 노드 위의 경우는 위에서 아래로 내려오며 시간 계산한 경우를 설명한 것이고, 문제 풀이는 아래에서 위로 시간 계산을 한다. 일단 트리 구조에 본인과 연결된 노드를 저장한다tree[0] = 1,2tree[1] = 없음tree[2] = 3,4tree[3] = 없음tree[4] = 없음 dfs를 이용하는데,0번 노드부터 시작한다. 그러면 0번 노드에서 시작해서,..
-
2156 포도주 시식백준/DP 다이나믹 프로그래밍 2024. 8. 9. 22:29
입력값을 wine 배열에 받는다고 하면, dp[1] = wine[1]dp[2] = dp[1] + wine[2] 이다. 그 이후부터는, dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i] , dp[i-3] + wine[i-1] + wine[i])) 즉, dp[5] 를 구하고 싶으면, 1) dp[4]2) dp[3] + wine[5]3) dp[2] + wine[4] + wine[5] 중에서 제일 큰 값을 고르면 된다. 1) dp[4] 를 구한다는 것은,연속으로 놓여 있는 3잔을 모두 마실 수 없다고 했으므로,이미 3,4 번째 포도주를 마셨다는 뜻이 된다. 그래서 5번째 포도주를 마실 수 없다. 2) dp[3] + wine[5] 를 구한다는 것은,3번째까지 마..
-
10844 쉬운 계단 수백준/DP 다이나믹 프로그래밍 2024. 8. 7. 21:39
아래 표에서,dp[i][j] : j가 맨 뒤에 올 때의 계단수 개수i = 1 일 때 계단수는,j0123456789계단수 x123456789dp[1][j]0111111111 i = 2 일 때 계단수는, j0123456789계단수 1021123223433454456556766787789889dp[2][j]1122222221 dp[2][4] 에서 j = 4 이고,이때의 계단수인 34, 54는 (j-1) 4 , (j+1)4 이므로,dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다.즉, dp[2][4] = dp[1][3] + dp[1][5] = 1 + 1 = 2 이다.즉,길이가 2인 맨 끝에 4가 올 때의 계단수 개수= 길이가 1인 맨 끝에 3이 올 때의 계단수 개수 + 길이가 1인..
-
1788 피보나치 수의 확장백준/DP 다이나믹 프로그래밍 2024. 7. 9. 22:50
양수, 음수를 나누어서 풀었는데, 일단 f(0) = 0f(1) = 1 1) n : 양수f(n) = f(n-1) + f(n-2) 이므로, f(2) = f(1) + f(0) f(3) = f(2) + f(1) f(4) = f(3) + f(2) 여기에서, dp[i] = dp[i-1] + dp[i-2] 임을 알 수 있다. 2) n : 음수 f(n-2) = f(n) - f(n-1) 이므로f(-1) = f(1) - f(0)f(-2) = f(0) - f(-1)f(-3) = f(-1) - f(-2) 이 경우, 절댓값으로 숫자 따지면,dp[i] = dp[i-2] - dp[i-1] 이 된다. 그래서 양수의 경우는 dp_plus 배열로, 음수의 경우는 dp_minus 배열로 따로 만들었고,음수의 경우에는 -1 일 경우,..
-
1915 가장 큰 정사각형백준/DP 다이나믹 프로그래밍 2024. 6. 26. 17:48
입력값을 input 배열에 넣고,만약 i,j 위치 값이 1일 경우 (아래 그림에서 input[i][j] = 1)dp[i][j] => dp[i-1][j-1], dp[i-1][j-1], dp[i][j-1] 중 최소값 + 1하면 된다. dp[1][1] = input[0][1], input[0][0], input[1][0] 중 최소값 + 1 하면 되는데,=> input[0][1] = 1, input[0][0] = 0, input[1][0] = 0 이므로이 중 최소값은 0 이고dp[1][1] = 0 + 1 = 1 이 된다. 그래서 dp배열을 완성하면 아래와 같다. 0100011111200010 규칙 1dp를 만들 때, 첫 행, 첫 열은input행렬의 첫 행, 첫 열 값을 그대로 입력하면 된다. 규칙 2 ..
-
10164 격자상의 경로백준/DP 다이나믹 프로그래밍 2022. 5. 22. 20:15
1. 풀이 문제에 주어진 예시를 가지고 설명하겠다. 3 5 8 이러한 값이 주어졌기 때문에 격자는 이와 같다. map[i][j] 배열에 위와 같이 입력한다. dp[i][j] 배열은 처음 위치(0,0) 에서 ((i,j) 위치까지 이동하는 서로 다른 경로의 수를 입력할 것이다. 그러면 8의 위치를 변수 a,b 에 저장한다. 즉, 8의 위치는 (1,2) 이다. a = 1, b = 2 1) dp[0][1] ~ dp[0][b] = 1 => dp[0][1] = 1 인건, (0,0) 에서 출발해서 (0,1) 까지 이동가능한 방법은 오른쪽으로 이동하는 경우 1가지 있다. => dp[0][2] = 1 인건, (0,0) 에서 출발해서 (0,2) 까지 이동가능한 방법이 오른쪽으로 이동하는 경우 1가지 있기 때문이다. dp[..
-
11060 점프 점프백준/DP 다이나믹 프로그래밍 2022. 5. 22. 15:17
1. 풀이 문제에서 주어진 예시를 가지고 설명하겠다. 10 1 2 0 1 3 2 1 5 4 2 input 배열에 입력값을 입력한다. 1 2 0 1 3 2 1 5 4 2 => input 배열에 입력 dp[i] 배열값은 첫번째 위치에서 i 번째까지 점프한 횟수이다. 1) i = 0 dp[0] = 0 첫번째 칸은 시작 칸으로 이동이 없으므로 0으로 초기화된다. input[0] = 1 이므로, 오른쪽으로 한 칸 점프 가능하다. => i = 1 위치까지 점프 2) i = 1 dp[0] 에서 점프가 1번 더해졌으므로 dp[1] = dp[0] + 1 =1 input[1] = 2이므로, 오른쪽으로 한 칸, 두 칸까지 이동 가능하다. => i = 2, 3까지 이동 3) i = 2 dp[2] = dp[1] + 1 = 2 ..