https://www.acmicpc.net/problem/1135  문제 풀이깊이 우선 탐색과 DP를 활용하여 문제를  풀어주었습니다.DFS방식을 사용하여 리프 노드에 도달한 뒤, 리프 노드에서부터 오름차순으로 걸리는 시간을 계산해줍니다. 코드# 1135번 뉴스 전하기num = int(input())order = list(map(int, input().split()))tree = [[] for _ in range(num)]for idx, manager in enumerate(order): if idx != 0: tree[manager].append(idx)dp = [0 for _ in range(num)]def dfs(node): node_to_sub = [] for sub ..

문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 문제를 풀기 위해서 다음과 같은 점화식이 필요하다. 주어진 화폐 단위 별로 해당하는 금액을 완성할 수 있는 동전을 구성하는 개수를 찾아준다. 1. dp[0]을 1로 초기화합니다. 이는 금액 0을 만드는 방법이 하나밖에 없음을 의미합니다(아무 동전도 사용하지 않는 경우). 2. 모든 동전 단위 coin[i]에 대해 반복합니다. 3. 각 coin[i]에 대해 금액 coin[..

https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 통해서 문제를 풀어주었습니다. 코드 # 1788번 피보나치 수의 확장 n = int(input()) dp = [0, 1, 1] for i in range(3, abs(n)+1): dp.append((dp[i-2] + dp[i-1])%1000000000) if n > 0: print(1, dp[-1], sep="\n") elif n < 0:..

https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 피보나치 수를 구해주었습니다. 코드 # 10826번 피보나치 수 4 n = int(input()) dp = [0, 1] for i in range(2, n+1): dp.append(dp[i-2] + dp[i-1]) print(dp[n]) 출력결과

https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 풀이 피보나치의 함수가 얼마나 호출되는지에 대한 계산을 요구한다. 그래서 dp테이블을 만들어서 n이 0~2까지의 함수 호출 횟수를 넣어준 뒤 다이나믹 프로그래밍을 통해서 n이 원하는 답을 구해주었습니다. 코드 # 17175번 피보나치는 지겨웡~ n = int(input()) dp = [1,1,3] for i in range(3, n+1): dp.append((dp[i-1] + dp[i-2] + 1..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 배낭 알고리즘을 이용해서 풀어줄 수 있는 문제이다. solved.ac 기준으로 class5를 달성하기 위해서 거쳐가야하는 문제 중 하나이다. 참고로 배낭 알고리즘은 Dp 알고리즘이기에 이 문제를 풀기 이전에 간단한 Dp문제를 풀고 오기를 바란다. 이 문제는 새로운 B앱을 활성화하기 위해 M메모리만큼 비활성화해야하는 앱들의 집합의 cost 최솟값을 찾는 문제이다. 따라서 기존의 배낭 알고리즘 문제에서..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 배낭 알고리즘이라 불리는 다이내믹 프로그래밍 알고리즘의 일종. 1행과 1열의 원소값들은 0값으로 고정해준다. 행은 배낭의 무게를 뜻하고, 열은 물건의 번호를 뜻한다. i번째 물건을 가방 안에 넣을 수 없는 경우 -> 이전까지 최댓값을 저장해준다. i번째 물건을 가방 안에 넣을 수 있다면 -> dp에서 i번째 물건과 같이 넣을 ..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 누적합을 구하는 문제이고, 시간을 최소화하기 위해 다이내믹 프로그래밍을 사용할 예정이다. 다음과 같은 문제는 LIS알고리즘을 사용하여 풀 수 있다. 그러나 DP로 문제를 풀어보았습니다. 가장 큰 증가수열을 구하기 위해서 다음과 같이 고려된다. 1) 이전 누적합의 마지막 숫자보다 큰 숫자를 더해서 증가수열을 만든다. 2) 이전 누적합..