Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 코테
- aws
- java
- GDSC
- 자바
- baekjoon
- softeer
- DART
- VSCode
- 코틀린
- Flutter
- programers
- SWIFT
- 파이썬
- Python
- kotlin
- MVVM
- 백준
- 다트
- 소프티어
- 아마존 웹 서비스
- 알고리즘
- 머신러닝
- 스위프트
- Android
- 프로그래머스
- 플러터
- 안드로이드
- 현대sw
- 개발
Archives
- Today
- Total
조준장 개발자 생존기
[baekjoon] 백준 3584번(파이썬): 가장 가까운 공통 조상 본문
문제
3584번: 가장 가까운 공통 조상
루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두
www.acmicpc.net
알고리즘
- 각 노드의 부모 노드를 저장한다.
- 공통 조상을 구하려는 두 노드는 따로 저장하여 두 노드의 부모 노드들을 찾는다.
- 두 노드의 부모 노드를 레벨별로 비교하여 제일 마지막에 같았던 부모 노드를 구한다.
- 제일 마지막에 같았던 부모 노드가 가장 가까운 공통 조상 노드가 된다.
코드
import sys
t = int(sys.stdin.readline())
# 테스트 케이스만큼 반복
for _ in range(t):
n = int(sys.stdin.readline())
parent = [0] * (n + 1) # 각 노드의 부모 노드
# 각 노드의 부모 노드를 저장
for _ in range(n - 1):
a, b = map(int, sys.stdin.readline().split())
parent[b] = a
# 구하려는 두 노드를 저장
a, b = map(int, sys.stdin.readline().split())
target_a = [a]
target_b = [b]
# 구하려는 두 노드의 부모 노드들을 저장
while parent[a]:
target_a.append(parent[a])
a = parent[a]
while parent[b]:
target_b.append(parent[b])
b = parent[b]
# 두 노드의 루트 노드부터 확인하기 위해 레벨을 맞춘다.
target_a_level = len(target_a) - 1
target_b_level = len(target_b) - 1
# 두 노드의 공통 조상을 찾는다.
# 두 노드의 루트 노드가 다를 때까지 반복
while target_a[target_a_level] == target_b[target_b_level]:
target_a_level -= 1
target_b_level -= 1
# 이전 레벨의 노드가 공통 조상 노드
print(target_a[target_a_level + 1])
github
GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법
내가 푼 코딩 테스트 문제와 해결법. Contribute to junjange/CodingTest development by creating an account on GitHub.
github.com
'CodingTest > Baekjoon' 카테고리의 다른 글
[baekjoon] 백준 13116번(파이썬): 30번 (0) | 2021.11.03 |
---|---|
[baekjoon] 백준 2108번(파이썬): 통계학 (0) | 2021.11.02 |
[baekjoon] 백준 2263번(파이썬): 트리의 순회 (0) | 2021.11.01 |
[baekjoon] 백준 9934번(파이썬): 완전 이진 트리 (0) | 2021.10.31 |
[baekjoon] 백준 1167번(파이썬): 트리의 지름 (0) | 2021.10.30 |