백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-3584 가장 가까운 공통 조상 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/3584

반응형

---

솔루션 살펴보기!!

import sys

def find_lca(node1, node2, parent):
    """
    두 노드의 가장 가까운 공통 조상(LCA)을 찾는 함수.
    """
    ancestors = set()

    # node1의 모든 조상을 기록 (root까지)
    while node1 != -1:
        ancestors.add(node1)
        node1 = parent[node1]

    # node2의 조상을 추적하며 첫 번째로 만나는 공통 조상을 반환
    while node2 != -1:
        if node2 in ancestors:
            return node2
        node2 = parent[node2]

    return -1  # 문제 조건상 실행되지 않음

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0

    T = int(data[idx])  # 테스트 케이스 수
    idx += 1

    for _ in range(T):
        N = int(data[idx])  # 노드 수
        idx += 1

        # 각 노드의 부모 정보를 담을 리스트 (0번 인덱스는 사용하지 않음)
        parent = [-1] * (N + 1)

        # 트리 간선 정보 입력
        for _ in range(N - 1):
            A, B = int(data[idx]), int(data[idx + 1])
            parent[B] = A
            idx += 2

        # 두 노드 입력
        node1, node2 = int(data[idx]), int(data[idx + 1])
        idx += 2

        # LCA 찾기
        lca = find_lca(node1, node2, parent)
        print(lca)

if __name__ == "__main__":
    main()

---

풀이 전략

이 문제는 트리에서 두 노드의 가장 가까운 공통 조상(LCA, Lowest Common Ancestor)을 찾는 문제입니다. 트리는 루트 노드에서 시작하여 자식 노드들이 있는 계층 구조를 가지며, 각 노드는 부모가 한 명뿐인 특성을 가지고 있습니다.

주어진 트리에서 두 노드의 공통 조상을 찾기 위한 전략은 다음과 같습니다:

1. 트리 구성: 주어진 노드들로 트리의 간선을 형성하고 각 노드의 부모 정보를 저장합니다. 이 정보는 두 노드의 조상을 추적하는 데 필요합니다.
2. 조상 추적: 첫 번째 노드의 모든 조상(부모 노드)을 루트 노드까지 추적하여 저장한 후, 두 번째 노드의 조상을 하나씩 탐색합니다. 이때, 두 번째 노드의 조상 중 첫 번째 노드와 공통되는 가장 가까운 노드를 찾으면 그것이 두 노드의 공통 조상(LCA)입니다.
3. 효율적 탐색: 두 노드의 부모를 따로따로 추적하면서 겹치는 부모(공통 조상)를 만날 때까지 탐색합니다. 두 노드의 경로를 모두 탐색하지 않고 빠르게 공통되는 조상을 찾을 수 있는 구조입니다.

코드 주요 흐름 설명

1. 입력 처리 및 초기 설정

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    T = int(data[idx])  # 테스트 케이스 수
    idx += 1

• sys.stdin.read를 사용하여 모든 입력을 한꺼번에 받아옵니다. 이렇게 하면 반복적으로 input()을 호출할 필요 없이 한 번에 데이터를 처리할 수 있어 효율적입니다.
• 데이터를 공백 기준으로 나누어 data 리스트에 저장하고, idx를 사용해 입력 값을 차례로 처리합니다.
• T는 테스트 케이스의 수를 나타냅니다.

2. 부모 정보 저장

for _ in range(T):
    N = int(data[idx])  # 노드 수
    idx += 1

    # 각 노드의 부모 정보를 담을 리스트 (0번 인덱스는 사용하지 않음)
    parent = [-1] * (N + 1)

    # 트리 간선 정보 입력
    for _ in range(N - 1):
        A, B = int(data[idx]), int(data[idx + 1])
        parent[B] = A  # B의 부모는 A
        idx += 2

• 각 테스트 케이스마다 노드의 수 N을 받아옵니다.
• parent 리스트는 각 노드의 부모를 기록하는 배열로, parent[i]는 i번 노드의 부모를 가리킵니다. 트리는 1부터 시작하므로, 0번 인덱스는 사용하지 않습니다.
• 주어진 트리의 간선 정보로 부모 노드를 설정합니다. 각 B 노드는 A를 부모로 가지며, 이를 parent[B] = A로 기록합니다.

3. 두 노드 입력 및 LCA 탐색

    # 두 노드 입력
    node1, node2 = int(data[idx]), int(data[idx + 1])
    idx += 2

    # LCA 찾기
    lca = find_lca(node1, node2, parent)
    print(lca)

• LCA를 구하고자 하는 두 노드를 입력받습니다.
• find_lca 함수는 이 두 노드의 가장 가까운 공통 조상을 찾아 반환합니다. 이를 출력합니다.

4. LCA 찾는 함수 (find_lca)

def find_lca(node1, node2, parent):
    """
    두 노드의 가장 가까운 공통 조상(LCA)을 찾는 함수.
    """
    ancestors = set()

    # node1의 모든 조상을 기록 (root까지)
    while node1 != -1:
        ancestors.add(node1)  # node1의 조상을 집합에 추가
        node1 = parent[node1]  # 부모로 이동

    # node2의 조상을 추적하며 첫 번째로 만나는 공통 조상을 반환
    while node2 != -1:
        if node2 in ancestors:  # node1의 조상 집합에 node2가 있으면
            return node2  # 공통 조상을 반환
        node2 = parent[node2]  # 부모로 이동

    return -1  # 문제 조건상 실행되지 않음

• find_lca 함수는 두 노드의 공통 조상을 찾는 핵심 함수입니다.

1. 첫 번째 노드의 모든 조상 기록:
   • node1의 모든 조상을 루트까지 추적하면서 집합 ancestors에 저장합니다. 이는 추후 node2의 조상들과 비교하기 위해 사용됩니다.
2. 두 번째 노드의 조상과 비교:
   • node2의 조상을 하나씩 추적하면서, 첫 번째 노드의 조상들과 겹치는 조상이 있는지 확인합니다. 가장 먼저 겹치는 조상이 발견되면 그것이 두 노드의 가장 가까운 공통 조상이므로 반환합니다.

이 방식은 트리의 높이에 비례한 시간 복잡도를 가지며, O(H)의 시간 복잡도를 갖습니다. H는 트리의 높이이며, 루트에서 리프까지의 최대 거리입니다.

---

728x90

코드 면접시 알아야할 주요 개념

1. 트리 (Tree) 자료구조

트리는 계층적인 구조를 가진 자료구조로, 다음과 같은 특성을 가지고 있습니다:

• 루트 노드 (Root Node): 트리의 최상위 노드로, 부모가 없는 유일한 노드입니다.
• 자식 노드 (Child Node): 다른 노드에서 간선을 통해 내려오는 노드입니다.
• 부모 노드 (Parent Node): 자식 노드를 연결하는 상위 노드입니다.
• 리프 노드 (Leaf Node): 자식이 없는 노드입니다.
• 서브트리 (Subtree): 트리의 일부로, 특정 노드와 그 자식 노드들로 구성됩니다.

면접에서 트리에 대한 질문이 나오면, 트리의 기본 개념과 용어들을 명확하게 설명할 수 있어야 하며, 트리의 다양한 응용에 대한 이해도 필요합니다.

2. LCA (Lowest Common Ancestor) 문제

LCA 문제는 주어진 두 노드 간의 가장 가까운 공통 조상을 찾는 문제입니다. 트리에서 두 노드의 부모들을 추적하여, 가장 가까운 조상을 찾는 방식으로 해결됩니다. 이 문제는 트리의 구조를 이해하고, 재귀적 탐색이나 부모 추적 등을 통해 풀 수 있는 문제로, 면접에서 자주 출제됩니다.

면접에서 중요한 것은 LCA 문제의 풀이 방법에 대해 설명할 수 있는 능력입니다:

• DFS (Depth First Search) 또는 BFS (Breadth First Search) 를 통해 부모 관계를 구축하고,
• 각 노드의 부모를 역으로 추적하며 조상을 탐색합니다.
• 더 효율적인 LCA 알고리즘으로는 희소 테이블(Sparse Table), 바이너리 리프팅(Binary Lifting) 등의 기법이 있습니다.

3. 시간 복잡도

LCA 문제는 일반적으로 트리의 높이에 비례하여 시간이 걸립니다. 이 코드에서 두 노드의 조상을 추적하는 방식은 트리의 높이(H)에 비례하는 시간 복잡도를 가지며, O(H)의 시간 복잡도를 가집니다. 이와 관련하여 시간 복잡도 분석을 할 수 있어야 합니다.

면접 시 설명할 수 있어야 하는 시간 복잡도 내용:

• 트리에서 두 노드의 부모를 추적하는 경우, 루트에서 리프까지의 경로를 탐색해야 하므로 높이에 비례하는 탐색을 해야 합니다.
• 따라서 이 방식의 시간 복잡도는 O(H)이며, 여기서 H는 트리의 높이입니다.

4. 자료구조 선택 및 활용

이 코드에서 사용된 자료구조는 리스트와 **집합(set)**입니다.

• 리스트: 부모 정보를 저장하는 데 사용됩니다. 각 노드의 부모를 추적하기 위한 배열로 사용되며, 리스트의 인덱스를 사용해 빠르게 부모 노드를 찾을 수 있습니다.
• 집합 (set): 첫 번째 노드의 모든 조상을 저장하고, 두 번째 노드의 조상과 빠르게 비교하기 위해 사용됩니다. set 자료구조는 평균적으로 O(1)의 탐색 시간 복잡도를 가지므로, 효율적인 조상 비교가 가능합니다.

자료구조 선택에 대한 질문이 나올 경우, 왜 set을 사용했는지와 리스트 대신 다른 자료구조를 사용할 수 있는지에 대해 논의할 수 있어야 합니다.

5. 재귀 vs 반복적 접근

이 코드는 반복적인 방식으로 두 노드의 조상을 추적합니다. LCA 문제는 재귀적으로도 풀 수 있는데, 면접에서는 재귀적 접근 방식과 반복적 접근 방식의 장단점에 대해 묻는 경우가 있습니다.

• 반복적 접근: 명시적인 스택을 사용하지 않고 루프를 통해 부모를 추적하며, 메모리 사용량이 적고 함수 호출이 필요하지 않습니다.
• 재귀적 접근: 함수 호출을 통해 간단하고 직관적인 코드를 작성할 수 있지만, 트리의 깊이가 깊을 경우 스택 오버플로우 위험이 있습니다.

이 부분에 대해서도 대비할 필요가 있습니다.

6. 트리의 구성 및 구현 방법

트리 문제에서 트리의 구성을 어떻게 다룰지 묻는 질문이 나올 수 있습니다. 트리는 여러 가지 방식으로 표현될 수 있으며, 이 문제에서는 간선을 통해 트리의 부모 관계를 배열에 저장하는 방식으로 구현되었습니다. 다른 방식으로는 인접 리스트, 인접 행렬 등을 사용한 그래프 표현 방법이 있습니다.

면접에서는 트리 구성 방법에 대한 이해를 물을 수 있으므로, 이와 관련된 다양한 구현 방식과 그 장단점을 설명할 수 있어야 합니다.

7. 특정 트리 구조를 가정한 최적화 기법

면접에서 추가적인 질문으로 트리가 특정 구조일 때 (예: 이진 트리, 완전 이진 트리 등) 문제를 더 효율적으로 해결하는 방법을 물을 수 있습니다. 예를 들어, 이진 트리에서 바이너리 리프팅(Binary Lifting) 기법을 사용하면 LCA 문제를 O(log N)에 해결할 수 있습니다. 이런 최적화 기법에 대한 이해도도 중요합니다.