파이썬 코딩테스트 강좌, 트리의 부모 찾기

안녕하세요! 이번 포스트에서는 트리 구조의 데이터를 다루는 알고리즘 문제를 풀어보겠습니다. 우리는 “트리의 부모 찾기”라는 문제를 통해 트리를 이해하고, 이를 통해 파이썬 프로그래밍 능력을 향상시킬 수 있을 것입니다. 트리 구조는 컴퓨터 과학에서 아주 중요한 개념 중 하나이며, 이는 데이터베이스, 파일 시스템, 웹사이트의 구조 등 다양한 곳에 응용되고 있습니다.

문제 설명

문제: 주어진 정점의 부모 노드를 찾는 함수를 작성하세요. 트리는 노드와 엣지로 구성된 비선형 자료구조로, 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다. 입력으로는 노드의 수와 각 노드의 부모 노드 정보가 주어집니다. 우리는 특정 노드의 부모 노드를 반환하는 함수를 작성해야 합니다.

입력 형식:
– 첫 번째 줄에 노드의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.
– 그 다음 N-1 줄에 각 줄마다 두 개의 정수 A, B가 주어지며, 이는 A가 B의 부모임을 의미합니다.

출력 형식: 특정 노드의 부모 노드 번호를 출력합니다.

문제 해결 방안

이 문제를 해결하기 위해서는 먼저 주어진 정보를 바탕으로 트리 구조를 형성할 수 있어야 합니다. 다음 과정을 따라 문제를 해결하겠습니다.

1단계: 데이터 구조 선택

트리를 구현하기 위해 딕셔너리를 사용합니다. 각 노드의 번호를 키로 하고, 해당 노드의 부모 노드를 값으로 가지는 구조를 선택하겠습니다. 그러면 주어진 관계를 효율적으로 저장하고 빠르게 부모 노드를 찾을 수 있습니다.

2단계: 입력 데이터 처리

입력 데이터를 읽어서 트리 구조를 생성합니다. 노드의 수를 입력받고, N-1 줄에 걸쳐 부모-자식 관계를 추가합니다. 이를 통해 전체 트리를 구성할 수 있습니다.

3단계: 부모 노드 찾기

특정 노드의 부모 노드를 찾기 위해, 앞서 만든 딕셔너리에서 해당 노드의 부모를 바로 조회하면 됩니다. 이는 상수 시간 (`O(1)`)에 가능합니다.

4단계: 함수 작성

위에서 논의한 내용을 바탕으로 파이썬 함수를 작성해 보겠습니다. 다음은 문제 해결을 위한 코드입니다:


def find_parent(n, edges, query_node):
    # 부모 노드 정보를 담는 딕셔너리
    parent = {}
    
    # 입력으로 주어진 관계를 기반으로 딕셔너리 생성
    for a, b in edges:
        parent[b] = a
        
    # 특정 노드의 부모 노드를 요청받았을 때 반환
    return parent.get(query_node, None)

# 예시 입력
n = 7  # 노드 수
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]  # 부모-자식 관계
query_node = 4  # 부모를 찾고자 하는 노드

# 부모 노드 찾기
print(find_parent(n, edges, query_node))

전체 코드


def find_parent(n, edges, query_node):
    parent = {}
    
    # 관계를 딕셔너리로 저장
    for a, b in edges:
        parent[b] = a
    
    return parent.get(query_node, None)

if __name__ == "__main__":
    n = int(input("노드 수를 입력하세요: "))
    edges = []
    for _ in range(n - 1):
        a, b = map(int, input("부모와 자식 관계를 입력하세요 (예: 'A B'): ").split())
        edges.append((a, b))
    
    query_node = int(input("부모를 찾고자 하는 노드 번호를 입력하세요: "))
    result = find_parent(n, edges, query_node)
    
    if result is not None:
        print(f"노드 {query_node}의 부모 노드는 {result}입니다.")
    else:
        print(f"노드 {query_node}의 부모 노드를 찾을 수 없습니다.")

문제 해결 과정 분석

위 코드는 다음과 같은 구조로 문제를 해결합니다:

딕셔너리를 사용하여 부모 노드 정보를 효율적으로 저장합니다.
주어진 관계를 통해 트리 구조를 형성합니다.
특정 노드에 대해 부모 노드를 빠르게 조회할 수 있습니다.

복잡도 분석

– 시간 복잡도: `O(N)` \- 노드 수(N)에 비례하여 부모 노드 관계를 저장합니다.
– 공간 복잡도: `O(N)` \- 노드 정보를 저장하기 위해 딕셔너리를 사용합니다.

결론

이번 포스트에서는 “트리의 부모 찾기”라는 문제를 통해 트리 구조와 관련된 기본적인 알고리즘을 배웠습니다. 트리는 효율적인 데이터 탐색 및 데이터 저장 방식으로 요즘 데이터 과학과 소프트웨어 개발에서 많이 사용되는 자료형입니다. 이 문제를 통해 트리를 이해하는 데 훌륭한 기초가 되었으리라 생각합니다. 다음 포스트에서는 더 복잡한 트리 문제를 다루어 보겠습니다. 감사합니다!