목록다이나믹 프로그래밍 (11)

몸과 마음이 건전한 SW 개발자

백준 GOLD 5 [9251번] LCS {언어 : Python} [다시 풀어 보기]

문제 링크https://www.acmicpc.net/problem/9251정답 코드 1a = input()b = input()lenA = len(a)lenB = len(b)dp = [[0] * (lenA+1) for _ in range(lenB+1)]maxLength = 0for i in range(lenB): alphaB = b[i] for j in range(lenA): alphaA = a[j] if alphaA == alphaB: dp[i][j] += dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) maxLength = max(maxLen..
알고리즘/다시 풀어 보기 2025. 2. 13. 13:38
백준 GOLD 5 [2565번] 전깃줄 {언어 : Python} [다시 풀어 보기]

문제 링크https://www.acmicpc.net/problem/2565정답 코드import sysinput = sys.stdin.readlinen = int(input())lines = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[1])dp = [1] * nfor i in range(1, n): si, ti = lines[i] for j in range(i): sj, tj = lines[j] if sj 풀이 방법 입력 처리 및 정렬(시작점, 끝점)을 입력받고 끝나는 지점 기준으로 정렬한다.정렬은 그리디 + DP 조합을 활용하기 위한 사전 작업이다.DP 배열 정의 및 초기화dp[..
알고리즘/다시 풀어 보기 2025. 2. 10. 16:23
백준 GOLD 5 [12865번] 평범한 배낭 {언어 : Python} [다시 풀어 보기]

문제 링크https://www.acmicpc.net/problem/12865정답 코드import sysinput = sys.stdin.readlinen, k = map(int, input().split())dp = [[0] * (k+1) for _ in range(n+1)]for i in range(1, n+1): w, v = map(int, input().split()) for j in range(1, k+1): if j >= w: dp[i][j] = max(v+dp[i-1][j-w], dp[i-1][j]) else: dp[i][j] = dp[i-1][j]print(dp[n][k])풀이 방법DP 배열의 의미:dp[i][j]dp[..
알고리즘/다시 풀어 보기 2025. 1. 24. 15:13
프로그래머스 [Lv. 4] 올바른 괄호의 갯수 {언어 : Python} [다시 풀어 보기]

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr정답 코드def solution(n): if n == 1: return 1 dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 dp[2] = 2 for i in range(3, n+1): for j in range(1, i+1): dp[i] += dp[j-1] * dp[i-j] answer = dp[-1] return answer풀이 방..
알고리즘/다시 풀어 보기 2024. 11. 26. 16:27
프로그래머스 [Lv. 3] 에어컨 {언어 : JavaScript} [다시 풀어 보기]

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/214289 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr정답 코드function solution(temperature, t1, t2, a, b, onboard) { // 계산을 편리하게 하기 위해서 -10 Array(51).fill(Infinity)); dp[0][t] = 0; const isValid = (i, temp) => !onboard[i] || (t1 t ? ht-1 : ht; if (isValid(i+1, te..
알고리즘/다시 풀어 보기 2024. 11. 11. 22:21
Softeer [Level 3] 나무 수확 {언어 : JavaScript} [다시 풀어 보기]

문제 링크https://softeer.ai/practice/7369 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai정답 코드const readline = require('readline');const rl = readline.createInterface({ input: process.stdin, output: process.stdout,});const inputData = [];rl.on('line', (line) => { inputData.push(line.split(" ").map((e) => Number(e)));}).on('close', () => { const n = inputData[0][0]; const field = inputData.slic..
알고리즘/다시 풀어 보기 2024. 11. 5. 17:42
이전 Prev 1 2 Next 다음