백준/다이나믹 프로그래밍
-
백준 1937 python백준/다이나믹 프로그래밍 2023. 5. 1. 14:45
문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 DFS 알고리즘을 이용한다. 시간 초과를 피하기 위해 방문했던 V 배열은 기존의 순회 정보를 이용한다. (다이나믹 프로그래밍) import sys sys.setrecursionlimit(10**6) [n],*I=[list(map(int, x.split())) for x in [*open(0)]] V=[[0]*n for _ in range(n)] def dfs(x,y): if ..
-
백준 5582 nodejs백준/다이나믹 프로그래밍 2023. 2. 16. 12:15
문제 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 2차원 dp를 이용한다. 0행과 0열을 초기화한다. A[i] == B[j] 일 때, dp[i][j] = dp[i -1][j - 1] + 1임을 이용한다. let [A, B] = `${require('fs').readFileSync(0)}`.trim().split`\n` let [a, b] = [A.length, B.length] const dp = [...Array(a)].m..
-
백준 7579 nodejs백준/다이나믹 프로그래밍 2023. 2. 12. 16:00
문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용한다. 비용을 기준으로 dp 배열을 만들고, 최댓값을 구한다. let [[N, M], m, c] = `${require('fs').readFileSync(0)}`.trim().split`\n`.map(e => e.split` `.map(Number)) let dp = Array(10001).fill(0) for (let i = 0; i < N; i++) for (let..
-
백준 1256 nodejs백준/다이나믹 프로그래밍 2023. 2. 8. 14:25
문제 https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용한다. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (맨 앞에 a를 넣은 경우 + 맨 앞에 z를 넣은 경우) ex) K = 2 x = 2, y = 2, dp[x][y] = 6 => K K > 1이므로 맨 앞에 z를 추가하고 y--, K에서 dp[i - 1][j]인 1을 빼준다. x = 1, y = 1, dp[x][y] = 2 => K Array(M..
-
백준 2098 nodejs백준/다이나믹 프로그래밍 2023. 2. 6. 17:14
문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 dp를 이용해 dp[i][j](i = 현재 위치, j = 지난 점 정보 - 비트마스킹)에 최단 거리를 저장한다. dfs를 이용해 0에서부터 모든 점을 순회하되, dp 배열을 활용해 값이 작아지는 경우에만 순회한다. let [[N], ...I] = require('fs').readFileSync('/dev/stdin').toString().trim()..
-
백준 1014 nodejs백준/다이나믹 프로그래밍 2023. 2. 3. 11:40
문제 https://www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 풀이 각각의 테스트케이스에서 .은 1, x는 0으로 바꾸고, 줄 단위로 10진수로 치환한다. (예 : ..x => 110 => 6) 이차원 dp를 초기화한다. 이때 앞의 것이 줄 번호, 뒤의 것이 10진수로 바꾼 배치 상태가 된다. dp[row][pos] shift 연산을 이용해 문제의 조건에 맞는 경우에만 dp[0]를 dp[0][pos]에서 pos의 1의 개수로 초기화한다. 이때 A[0]부터 1씩 숫자를 ..
-
백준 2096 Kotlin백준/다이나믹 프로그래밍 2023. 2. 2. 13:56
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용해 최대 점수와 최소 점수를 각각 구한다. fun main() { val N = readln().toInt() val I = Array(N) { readln().split(' ').map({ it.toInt() }) } val dp1 = intArrayOf(0, 0, 0) val dp2 = intArrayOf(0, 0, 0) for(i in I) { val A = maxOf(..
-
백준 2631 nodejs백준/다이나믹 프로그래밍 2023. 1. 24. 13:25
문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 풀이 dp로 가장 긴 증가하는 부분수열을 구하고, N에서 빼준다. let [N, ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number) const dp = Array(N).fill(1) for (let i = 0; i < N; i++) for (let j = 0; j < i; j++) if (..