코딩테스트 - 패스트캠퍼스 챌린지 39일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 동적 프로그래밍 (Dynamic Programming) - 3

학습 후기
동적 프로그래밍 그 3번째 시간이다. 여러 동적 프로그래밍 문제를 풀며 동적 프로그래밍의 대표적인 문제 유형을 강의에서 정리해주었다.
1. 문제 크기 N을 변수로 만들어서 표기하는 경우
ex) i를 1, 2, 3의 합으로 표현하는 경우의 수
2. 문제 크기 N과 마지막 상태를 함께 기록해줘야 하는 경우
ex) 계단 오르기
1) Dy[i][0]: i - 1번째 계단을 밟지 않고, i 번째 계단에 도착하며 얻는 최대 점수
2) Dy[i][1]: i - 1번째 계단을 밟고, i 번째 계단에 도착하며 얻는 최대 점수
3. 구간 L ~ R에 대한 문제를 해결할 때
4. 2차원 격자 배열에서 문제를 해결할 때
5. 트리 구조에서 문제를 해결할 때

저번 강의까지 1번, 2번에 대한 문제를 풀어 보았고 이번에는 5번 문제 유형에 대해서 풀어본다.
https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

Rooted Tree에서 정점이 주어질 때마다, 정점에 대한 subtree에 속한 정점의 개수를 계산하라.
동적 프로그래밍: 작은 문제 > 큰 문제
1) 풀고 싶은 가짜 문제 정의: Dy[i]는 i를 root로 하는 subtree의 정점 개수
2) 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?: Dy[n]로 subtree에 속한 정점의 개수를 구할 수 있다.
3) 초기값: 단말 노드는 정점이 하나뿐이라 초기 값이 1이다.
4) 점화식: 부모 노드의 정점은 자식 노드의 정점의 합 + 1이다.
Rooted Tree를 DP로 풀 경우 대부분 DFS 한 번에 문제를 해결할 수 있다. 따라서 DFS의 시간 복잡도인 O(V+E)=O(N)만에 문제를 해결할 수 있다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.