[백준/Python] 12865. 평범한 배낭
·
CODING_TEST
※ 문제https://www.acmicpc.net/problem/12865  ※ 문제 유형다이나믹 프로그래밍, 배낭 문제(GOLD_5) ※ 나의 풀이DP를 이용하여 문제 해결역순으로 DP값을 max로 비교 계산import sysN, K = map(int, sys.stdin.readline().split())dp = [0] * (K + 1)items = []for _ in range(N): items.append(list(map(int, sys.stdin.readline().split())))for W, V in items: # 역순으로 계산 for i in range(K, W - 1, -1): dp[i] = max(dp[i], dp[i-W] + V) print(d..
[백준/Python] 1003. 피보나치 함수
·
CODING_TEST
※ 문제https://www.acmicpc.net/problem/21318 ※ 문제 유형다아니믹 프로그래밍 (SILVER_3)※ 나의 풀이다아니믹 프로그래밍 풀이2차원 DP각 피보나치 숫자를 구하는 과정에서 0 호출 횟수 와 1 호출 횟수를 저장피보나치 공식인 fibo(x) = fibo(x -2) + fibo(x - 1)를 이용해 호출 횟수를 누적 계산 DP 배열 구조 :  dp[i]  =  [0 호출 횟수, 1호출 횟수]import sysT = int(sys.stdin.readline())cases = []for _ in range(T): cases.append(int(sys.stdin.readline()))# dp = [[0, 0]] * (40 + 1) X # -> 가변 객체를 담을 경우 같은 ..
[백준/Python] 14916. 거스름돈
·
CODING_TEST
※ 문제https://www.acmicpc.net/problem/14916※ 문제 유형수학, 다이나믹 프로그래밍, 그리디 알고리즘(SILVER_5)※ 나의 풀이DP로 문제 해결import sys N = int(sys.stdin.readline())dp = [-1] * (N + 1)if N >= 2: dp[2] = 1if N >= 4: dp[4] = 2if N >= 5: dp[5] = 1# DP 계산for i in range(6, N + 1): if dp[i - 2] != -1: # 2원을 추가할 수 있는 경우 dp[i] = dp[i - 2] + 1 if dp[i - 5] != -1: # 5원을 추가할 수 있는 경우 if dp[i] == -1:..
[백준/Python] 9095. 1, 2, 3 더하기
·
CODING_TEST
※ 문제https://www.acmicpc.net/problem/9095※ 문제 유형다이나믹 프로그래밍 (SILVER_3)※ 나의 풀이DP로 문제 해결4를 1, 2, 3으로 표현하는 방법 7가지1 + 1 + 1 + 11 + 1 + 21 + 2 + 12 + 1 + 12 + 21 + 33 + 15를 1, 2, 3으로 표현하는 방법4에서 1을 더하는 방법(7가지)3에서 2를 더하는방법2에서 3을 더하는 방법6을 1, 2, 3으로 표현하는 방법5에서 1을 더하는 방법4에서 2를 더하는 방법3에서 3을 더하는 방법dp[N] = dp[N-1] + dp[N-2] + dp[N-3]import sysT = int(sys.stdin.readline())case = []for i in range(T): case.app..
[백준/Python] 1463. 1로 만들기
·
CODING_TEST
※ 문제https://www.acmicpc.net/problem/1463※ 문제 유형다이나믹 프로그래밍 (SILVER_3)※ 나의 풀이DP로 문제 해결import sysN = int(sys.stdin.readline())dp = [0] * (N + 1)dp[1] = 0for i in range(2, N + 1): # 이전 index의 값 + 1(1을 뺀다는 규칙)으로 저장 dp[i] = 1 + dp[i - 1] # 3으로 나누어 떨어지면 3으로 나누고, dp[i] 중 최솟값으로 저장 if i % 3 == 0: dp[i] = min(dp[i], 1 + dp[i // 3]) # 2으로 나누어 떨어지면 2으로 나누고, dp[i] 중 최솟값으로 저장 if i % 2 ..
[프로그래머스/Python] 피보나치 수
·
CODING_TEST
※ 문제https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  ※ 문제 설명피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1F(3) = F(1) + F(2) = 1 + 1 = 2F(4) = F(2) + F(3) = 1 + 2 = 3F(5) = F(3) + F(4) = 2 + 3 = 5와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번..