DP

👉🏻 2294번: 동전 2n, k = map(int, input().split())money = [int(input()) for _ in range(n)]dp = [float('inf')] * (k+1)dp[0] = 0for i in range(1, k+1): for coin in money: if i - coin >= 0: dp[i] = min(dp[i], dp[i-coin] + 1)print(-1 if dp[k] == float('inf') else dp[k]) 🤔 왜 이렇게 풀었을까?전형적인 DP 문제입니다. 사실 처음에는 아래처럼 '거스름돈 문제다!!' 생각해서 냅다 그리디로 풀어봤는데, 당연하게도 시간이 초과했습니다.n, k = map(int, inpu..

👉🏻 24417번: 알고리즘 수업 - 피보나치 수 2mod = int(1e9) + 7n = int(input())ans = n-2prev, cur = 1, 1for _ in range(ans): nv = (prev + cur) % mod prev, cur = cur, nvprint(cur, ans)왜 이렇게 풀었을까?해당 문제는 제목만 봐도 파악할 수 있듯, 피보나치 수에 관한 내용을 다루고 있습니다. 피보나치 수를 알고리즘으로 구하기 위해서는 대표적으로 재귀, DP의 2가지 방법을 사용할 수 있는데, 문제에서는 두 개를 모두 요구하고 있습니다.fib(n) { if (n = 1 or n = 2) then return 1; # 코드1  else return (fib(n - 1..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krdef solution(N, number): answer = 0 dp = [set() for _ in range(9)] if N == number: return (answer := 1) for i in range(1, 9): dp[i].add(int(str(N) * i)) for j in range(1, i): for num1 in dp[j]: for num2 in dp[i-j]: dp[i].add(num1..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krdef solution(board): answer = 0 rows = len(board) cols = len(board[0]) dp = [[0] * cols for _ in range(rows)] for i in range(rows): dp[i][0] = board[i][0] answer = max(answer, dp[i][0]) for j in range(cols): dp[0][j] = board[0][j] ..

👉🏻 9184번: 신나는 함수 실행import sys; input=sys.stdin.readlinedef w(a, b, c): if a 20 or b > 20 or c > 20: return w(20, 20, 20) if (a, b, c) in dp: return dp[(a, b, c)] if a pseudo code로 작성되어 있는 재귀 문제를 dp 형식으로 변환하는 문제였습니다.저는 w(20, 20, 20)까지의 결과값을 미리 계산하여 dp로 처리하는 방식을 사용하였습니다.

👉🏻 19621번: 회의실 배정 2  회의실 배정2 DP 0 40 80 120 160 200 회의 1 (80명) 회의 2 (60명) 회의 3 (70명) 회의 4 (100명) 회의 5 (40명) 회의 6 (50명) DP 과정: 초기화: parts = [80, 60, 70, 100, 40, 50] Step 1: parts = [80, 60, 70, 100, 40, 50] (변화 없음) Step 2: ..

배낭 문제(Knapsack Problem)의 개념 배낭 문제란, 제한된 용량을 가진 배낭에 최대 가치를 담을 수 있는 물건들의 조합을 찾는 문제입니다. 각각의 물건은 가치와 부피(또는 무게)를 가지고 있으며, 우리의 목표는 주어진 용량 내에서 최대 가치를 얻을 수 있는 조합을 찾는 것입니다. 0/1 배낭 문제: 가장 기본적인 형태인 0/1 배낭 문제에서는 각각의 물건은 단 하나씩만 선택할 수 있습니다. 즉, 해당 물건을 전부 넣거나 아예 넣지 않거나 둘 중 하나만 선택할 수 있습니다. 코딩 테스트에서의 배낭 문제 접근 방법 일반적으로 0/1 배낭 문제를 해결하기 위해서 아래 일련의 단계를 거치는 다이나믹 프로그래밍(DP) 기법을 사용합니다. DP 테이블 초기화: DP 테이블은 (물건 개수+1) x (배낭..

이번에는 코딩 테스트에서 중요한 유형인 'Dynamic Programming(다이나믹 프로그래밍)'에 대해 알아보겠습니다. 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법으로, 중복되는 계산을 피하면서 효율적으로 문제를 해결합니다. 다이나믹 프로그래밍은 많은 종류의 문제에서 사용되며, 최적화와 관련된 문제에 자주 활용됩니다. Dynamic Programming이란?다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 작은 부분 문제의 결과를 저장하고 활용하여 전체 문제의 해답을 도출합니다. 이 때, 중복되는 부분 문제가 있을 경우 해당 결과를 메모리에 저장하여 중복 계산을 피할 수 있습니다.다이나믹 프로그래밍은 최적 부분 구조(Optimal Substruc..