Leta Learns

1. Tree DP Tree : cycle이 없는 그래프 (서로 다른 두 노드를 잇는 길이 하나) => 그래프처럼 DP 기법 적용 가능 트리에서 DP는 서브트리에서 구한 해를 이용하여 전체 트리의 해를 구하는 방식으로 진행된다. 트리는 비선형 구조이므로 DP를 하기 전에 탐색 순서를 미리 정해주는 것이 일반적. => 보통 탐색 순서는 DFS를 돌면서 나오는 트리를 기준으로 함. 기본적으로 Top-down 방식으로 코드 작성. => 보통의 DFS처럼 leaf 노드까지 순회하고, leaf 노드의 값을 알아낸 뒤 상위 노드의 값들을 알아내는 방식. Tree DP 예제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 ..

문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 알고리즘 분류에 '누적합'이라고 나와있는데 누적합으로 안 푼 바보가 여기 있다.. 최대로 끌 수 있는 객차 수를 하나하나 계산해서 단순합으로 넣으려고 하니까 코드도 복잡해지고 안 풀린 거였다. 2021.07.10 - [HUFS/HUFS 모각코 캠프] - [모각코] 210710 Today I Learned (단순합으로 시도한 코드) 단순합으로 하면 예제는 풀리긴 하는데 최대로 끌 수..

짜증나서 돌아버릴 것 같다. DP는 익숙하지 않아서 어렵다.. 테이블에 들어갈 요소 생각하고 점화식만 잘 세우면 되는데 그 두 개가 왜 이리 어려울까.. 다 풀고 나서 제출 돌려보니 런타임 에러가 났는데 최대로 끌 수 있는 객차의 수가 달라질 때를 고려하지 않아서 그런 것 같다. 단순합(dp[0]) 부분을 수정해줘야 하는데 어떤 방식으로 해야할 지 생각이 나지 않는다. #런타임 에러 코드 import sys n = int(sys.stdin.readline()) #기관차가 끌고 가던 객차의 수 people = [0] + list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) #소형기관차가 최대로 끌 수 있는 객차의 수 dp = ..

1. 동적계획법 : 큰 문제를 여러 개의 작은 부분으로 분할하여 해결하는 기법. 2. DP vs. Divide & Conquer Dynamic Programming Divide & Conquer 공통점 큰 문제를 여러 개의 작은 문제로 나눠서 해결한다. 차이점 작은 문제에서 중복 O 작은 문제에서 중복 X 3. DP의 조건 1) 작은(부분) 문제들이 중복된다. -> 부분 문제 한 번만 계산한 후 그 해를 테이블에 저장. -> 그 부분 문제가 중복될 때마다 테이블에서 미리 저장해둔 해를 반환. 2) 최적 부분 구조를 가진다. -> 작은 문제의 해로부터 큰 문제의 해를 구할 수 있음. 4. How To Solve DP Top-Down / 재귀함수를 사용하는 방식 (Memoization) -> 시간복잡도 문제..