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

수강한 강의

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

Chapter 02 알고리즘
- 트리 (Tree)

학습 후기
트리: 그래프의 특수한 형태로 그래프 중에서 어떤 특정한 조건을 만족해야 한다.
1. 모두가 연결되어 있는 그래프 - 어떤 두 점을 골라도 간선을 타고 이동 가능
2. 사이클이 존재하지 않음
3. 정점 개수는 간선 개수 + 1이다
이 중 2개 이상의 조건을 만족하는 그래프를 트리라고 한다.

Rooted Tree
나무를 뒤집어 놓은 듯한 모양으로 다음과 같은 용어를 알아야 한다.
1. Node: 정점
2. Root: 최 상위 정점
3. Depth: Root를 0으로 자식으로 내려갈수록 +1, Root에서 얼마나 떨어져 있느냐로 볼 수 있다.
4. Parent: 부모 노드, Child: 자식 노드, Ancestor: 조상, 해당 노드로부터 Root 노드까지의 부모 노드들
Sibling: 같은 부모를 두고 있는 노드들
5. Leaf Node: 단말 노드로 자식이 없는 노드

트리 문제 키워드
1. 모든 두 정점 사이에 이들을 잇는 경로가 존재하며, 사이클이 존재하지 않는 경우
2. 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 모든 마을은 연결되어있다.
3. 대 놓고 문제에 트리라고 적혀 있을 경우

트리는 대부분 인접 리스트를 사용해서 푼다.
그래프를 저장하는 방법에 인접 행렬로 저장하는 방법과 인접 리스트로 저장하는 방법이 있는데 트리의 경우는 V(정점) = E(간선) + 1이라는 조건이 주어지게 된다. 이때 인접 행렬을 사용할 경우, 인접 행렬의 공간 복잡도는 O(V^2)인데 만약 V가 10만이면 공간 복잡도는 100억이 된다. 하지만 인접 리스트의 경우 공간 복잡도가 O(E)이고 V가 10만 일 때, 공간 복잡도는 O(99999)라는 걸 알 수 있기에 공간 복잡도 측면에서 이득이므로 트리에서 대부분 인접 리스트를 사용한다.

https://www.acmicpc.net/problem/1068

1068번: 트리

문제 접근 방법
1. 정점 제거 - 어떤 정점을 제거하면 해당 정점과 부모 노드를 잇는 간선을 삭제하여 부모 노드에서 해당 정점을 바라보지 않도록 한다.
2. 단말 노드 개수 세기 - 그래프 탐색 알고리즘 BFS or DFS를 사용하여 단말 노드를 찾을 수 있다.
Subtree - 트리에서 어떤 정점 X를 기준으로 X와 그 모든 자손들을 포함하는 트리를 Subtree라고 하며 이때 X가 새로운 Root가 된다.
큰 문제와 작은 문제 - 큰 문제: 트리 안에 있는 단말 노드가 개수, 작은 문제 Root의 자식 노드들의 subtree안에 있는 단말 노드의 개수
큰 문제의 정답을 작은 문제의 정답들을 이용해서 구하는 게 핵심
DFS를 사용하여 X의 subtree의 leaf 개수를 구하고 부모 노드로 돌아오면 부모 노드는 해당 자식의 leaf개수만 더하면 된다.

수강 인증샷

https://bit.ly/37BpXiC

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

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