2023년 9월 7일 알고리즘 문제풀이 문제 1 백준 2748 문제 링크 1차 시도 나의 생각 기본적인 다이나믹 프로그래밍 문제였다. 재귀를 이용하면 시간초과가 되니 정의한 함수를 저장하는 배열을 만들어서 이를 참조하자. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n+1)] dp[1] = 1 def fibo(x): if x == 0: return dp[0] elif x == 1: return dp[1] else: if dp[x]: return dp[x] else: dp[x] = fibo(x-1) + fibo(x-2) return dp[x] print(fibo(n)) 문제 2 백준 1904 문제 링크 ...
개발 진행 및 완료 상황 3주차 python algorithm 난이도 중 이하 문제 풀이 완료 CSAPP 3.3 까지 공부 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 9084 동전(https://www.acmicpc.net/problem/9084) 풀이 과정 : j원을 만들 수 있는 경우의 수를 dp[j]라 한다면 동전의 한 종류인 i원을 더한 j+i원을 만드는 경우의 수도 dp[j+i]를 더함으로서 구할 수 있다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys ans = [] t = int(sys.stdin.readline()) for _ in range(t): n = int(sys.stdin.readline()) coin = list(map(int,sys.stdin.readline().split())) m = int(sys.stdin.readline()) dp = [0] * 10001 dp[0] = 1 for i in coin: for j in range(1,m+1): if j-i >= 0: dp[j] += dp[j-i] ans.append(dp[m]) print(*ans, sep='\n') 출처 : ...