코틀린 코딩테스트 강좌, 트리의 부모 찾기

안녕하세요! 오늘은 코딩 테스트에서 자주 등장하는 자료구조 중 하나인 트리에 대해 알아보겠습니다. 특히, 트리에서 특정 노드의 부모 찾기 문제를 다룰 것입니다. 트리는 다양한 문제에서 기초 자료구조로 활용되며, 그 특징 때문에 다양한 알고리즘과 문제풀이 방법을 요구합니다.

문제 설명

주어진 트리에서 특정 노드의 부모 노드를 찾아 반환하는 프로그램을 작성하세요. 트리는 비어있지 않으며, 각 노드는 정수로 특별한 ID로 표현됩니다.

입력:

  • 트리의 노드 수 N (1 ≤ N ≤ 100,000)
  • 부모 노드 정보 (N-1 개의 정수로 이루어진 배열 P)
  • 부모를 찾아야 할 노드 X (1 ≤ X ≤ N)

출력:

노드 X의 부모 노드 ID를 출력합니다.

예시

입력:

    5
    1 1 2 2
    3

출력:

    1

여기서 노드 3의 부모 노드는 1입니다.

문제 풀이 과정

이 문제를 해결하기 위해서는 트리 구조를 이해하고, 부모를 선언하는 배열을 활용하는 것이 중요합니다. 트리에 대한 이해를 위해, 먼저 트리의 특징을 살펴보겠습니다.

트리의 특징

  • 트리는 계층 구조로, 각 노드는 하나의 부모를 가질 수 있습니다.
  • 루트 노드는 부모가 없습니다.
  • N개의 노드가 있을 때, 부모 정보를 배열로 쉽게 표현할 수 있습니다.
  • 부모와 자식 간의 관계를 쉽게 파악할 수 있도록 정보를 저장하는 것이 중요합니다.

접근 방법

  1. 부모 노드 정보 P를 이용해 각 노드의 부모를 찾는 방법으로 접근할 수 있습니다.
  2. 배열 P에서 인덱스를 통해 자식 노드의 부모를 쉽게 찾을 수 있습니다.
  3. 주어진 노드 X의 부모 노드를 찾기 위해, P[X-1]를 반환합니다.

코드 구현

이제 코틀린(Kotlin)으로 문제를 해결하는 코드를 실습해 보겠습니다.


fun findParent(n: Int, parentInfo: IntArray, x: Int): Int {
    return parentInfo[x - 1]  // X의 부모는 P[X-1]로 정의됨
}

fun main() {
    val n = 5
    val parentInfo = intArrayOf(1, 1, 2, 2)  // 부모 노드 정보
    val x = 3  // 찾고자 하는 노드
    println(findParent(n, parentInfo, x))  // 결과 출력
}

시간 복잡도

이 알고리즘은 O(1)의 시간 복잡도를 가집니다. 이유는 단순히 배열에서 인덱스에 접근하여 부모 노드를 찾기 때문입니다. 이와 같은 접근 방식은 대량의 노드가 있어도 빠르게 부모 노드를 찾을 수 있습니다.

테스트 케이스

여기서 몇 가지 추가 테스트 케이스를 살펴보겠습니다:

  • 테스트 케이스 1:
    •         입력: 
        4
        1 1 2 
        1
        출력:
        -1 (루트 노드는 부모가 없음)
  • 테스트 케이스 2:
    •         입력:
        10
        2 2 3 3 4 4 5 5
        6
        출력:
        4

결론

이번 포스팅에서는 트리의 부모 찾기 문제를 기반으로 코딩 테스트를 준비하는 방법에 대해 알아보았습니다. 트리 구조의 기본적인 이해가 중요한 만큼, 알고리즘 문제를 해결하기 전에 트리를 잘 학습하는 것이 필요합니다. 자주 사용하는 트리 관련 문제들을 통해서 더욱 발전된 알고리즘 실력을 기르길 바랍니다. 다음 포스팅에서는 다른 트리 관련 문제를 준비해 보겠습니다.

그럼 모두 수고하세요!