동적계획법

[프로그래머스] 도둑질 (DP)

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 2023.07.15 - [Algorithm PS/Programmers] - 스티커모으기 (DP) 스티커모으기 (DP) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 인 karla.tistory.com 풀이 def solution(mone..

[1231] 주식왕 동호 (냅색 알고리즘)

1231번: 주식왕 동호 첫 줄에는 주식의 개수 C(1 ≤ C ≤ 50)과 주식 매입 및 매각을 할 기간 D(2 ≤ D ≤ 10), 초기 자금 M(1 ≤ M ≤ 200,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 C+1번째 줄까지 각 줄에는 각각 주 www.acmicpc.net 분석 [12865] 평범한 배낭 (냅색 알고리즘) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 karla.tistory.com 풀이 import sys input=sys.stdin.readline c,d,m=map(int..

[2294] 동전 2 (동전 개수 최소값)

2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 분석 동전 교환 (DP) 분석 더보기 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 ..

[2293] 동전 1 (경우의 수 구하기)

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 분석 [2624] 동전 바꿔주기 (DP) 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각..

[14501번] 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i+s[i][0], n+1): if dp[j] < dp[i] + s[i][1]: dp[j] = dp[i] + s[i][1] print(dp[-1]) top down n = int(input()) dp = [0]*(n+2) # 오늘부터 퇴사일까지 벌수있는 최대수입 (점화식 테이블) t=[0]*(n+1) # 상담에 필요한 일수 p=[0]*(n+1)..

[9252번] 최장 공통 부분 수열 찾기(LCS)

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS Longest Common Subsequence 분석 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) a=list(input()) a.pop() b=list(input()) b.pop() # 점화식 테이블 d=[[0 for j in range(len(b)+1)] for i in range(len(a)+1)] # LCS 저장 리스트 re..