[코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표

목표 : LCA(Lowest Common Ancestor) 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해본다.

 

실습은 총 4문제로 알고리즘 수업 시간이 진행되었던 실습 문제이다.

 

1. root 찾기

이진 트리의 노드의 개수가 주어지고, 노드의 key와 자식들이 주어졌을 때 해당 트리의 root를 찾으시오.

[입력 값]

6 # N

D . . # 간선의 정보 N개

E . .

F . .

C F .

B D E

A B C

 

[예상 출력]

A

 

2. 트리 순회

이진 트리의 노드의 개수가 주어지고, 노드의 key와 자식들이 주어졌을 때 해당 트리의 Preorder/ Inorder / Postorder 순으로 순회하고 출력하시오.

[입력 값]

6 # N

D . . # 간선의 정보 N개

E . .

F . .

C F .

B D E

A B C

 

[예상 출력]

A B D E C F

D B E A F C

D E B F C A

 

3. 최소 공통 조상 노드

이진 트리의 노드의 개수가 주어지고, 노드의 key와 자식들이 주어졌을 때 해당 트리를 구축하고, 질의 노드의 최소 공통 조상 노드를 출력하시오.

[입력 값]

5 # N개

4 . . # 간선의 정보 N개

3 . .

2 4 5

1 2 3

5 . .

3 4 # 질의 노드

 

[예상 출력]

1

 

4. 이후 백준에서 LCA과 관련된 문제를 풀어본다.

www.acmicpc.net/problem/11437 (11437번 - LCA)

11437번: LCA