꼭 알아야하는 코딩 테스트 유형: 12) #Trees

• 이번에는 코딩 테스트에서 중요한 유형인 'Trees(트리)'에 대해 알아보겠습니다. 트리는 계층적인 구조를 가지며, 여러 개의 노드가 연결된 자료 구조입니다. 이번 글에서는 트리의 개념과 코딩 테스트에서 트리 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세히 알아보겠습니다.

 

트리의 개념

 

• 트리는 그래프 이론의 일부로, 계층적인 구조를 가진 비선형 자료 구조입니다. 그래프와 마찬가지로 노드(Node)와 간선(Edge)으로 이루어져 있지만, 다음과 같은 조건을 만족합니다.

 

1. 사이클이 없다: 임의의 두 노드 사이를 연결하는 경로는 유일합니다.
2. 연결되어 있다: 임의의 두 노드 사이를 연결하는 경로가 항상 존재합니다.
3. 계층적 관계: 하나의 노드(루트)를 기준으로 다른 모든 노드들은 부모-자식 관계로 연결됩니다.

 

트리 문제 해결 전략

 

• 트리 문제를 해결하기 위해서는 아래와 같은 전략을 활용할 수 있습니다.

 

1. 문제 파악하기: 주어진 문제 상황과 요구사항을 정확히 파악합니다.
2. 트리 구성하기: 주어진 입력 데이터를 기반으로 필요한 데이터 구조인 '트리'를 구성합니다. 입력 데이터에 따라 특정 형태나 속성을 가진 특수한 종류의 트리 (예: 이진 트리, AVL 트리 등) 인 경우도 있습니다. 또한 주어진 입력 데이터로부터 각각의 노드와 간선들을 생성하여 서로 연결해주어야 합니다.
3. 탐색 알고리즘 선택하기: 트리 문제를 해결하기 위해 탐색 알고리즘을 선택하는 것은 매우 중요합니다. 주로 사용되는 탐색 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
4. 1) 재귀적 접근: 트리는 재귀적인 성질을 가지므로, 재귀 함수를 이용하여 문제에 접근할 수 있습니다. 각 노드에서 자식 노드로 내려가며 재귀 호출을 수행하면서 문제를 해결할 수 있습니다.
   2) 트리 순회: 트리의 모든 노드를 특정 순서대로 방문하는 것을 의미합니다. 대표적인 순회 방법으로는 전위(pre-order), 중위(in-order), 후위(post-order) 순회가 있으며, 각각의 순회 방법은 다른 결과와 사용 시점을 가지므로 적절한 방법을 선택해야 합니다.
   3) 메모이제이션(Memoization): 동일한 계산을 반복하지 않기 위해 결과 값을 저장해두는 기법입니다. 트리에서도 부분 문제의 결과 값을 저장해두고 필요할 때마다 활용하여 중복 계산을 줄일 수 있습니다.
5. 코드 작성 및 디버깅: 알고리즘에 따라 코드를 작성하고, 예시 입력과 출력에 맞게 동작하는지 확인합니다. 이 과정에서 가독성을 고려하여 변수명과 함수명을 명확하게 지정하고, 주석을 추가하여 코드의 의도를 설명하는 것이 좋습니다. 또한, 테스트 케이스를 활용하여 코드를 디버깅하고 예외 상황에 대비하는 것도 중요합니다.
6. 시간 복잡도 분석: 작성된 코드의 시간 복잡도와 공간 복잡도를 분석하여 성능 면에서 최적화할 수 있는 부분이 있는지 검토합니다. 이는 대량의 데이터나 큰 규모의 트리에서 실행 시간과 메모리 사용량을 예측하는 데 도움이 됩니다.

 

9372번: 상근이의 여행

  문제  
 

• 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.
• 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.
• 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.
• 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

 
  해결 방법  
 

• 이 문제에서 상근이가 모든 나라를 방문하기 위해 필요한 최소 비행기 갯수를 찾아야 합니다. 주어진 나라와 비행 경로 정보가 모두 연결되어 있으므로, 사실상 각 나라는 하나의 큰 트리 혹은 그래프 구조를 이룹니다.
• 그런데 우리가 원하는 것은 모든 나라들을 순회하는 최소 비용으로서, 사실상 MST(Minimum Spanning Tree)와 같은 개념입니다. 하지만 이 문제에서 모든 간선의 가중치가 동일하므로 (즉, 비용이 없음), 단순하게 국가 수 - 1 을 계산하면 됩니다 (MST에서 간선 수 = 정점 수 - 1). MST의 개념을 추후 포스팅에서 설명하겠습니다.

import sys; input=sys.stdin.readline

for _ in range(int(input())):
    N, M = map(int, input().split())
    for _ in range(M):
        a, b = map(int, input().split())
    print(N-1)

 

1068번: 트리

  문제  
 

• 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
• 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
• 예를 들어, 다음과 같은 트리가 있다고 하자.

• 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

• 이제 리프 노드의 개수는 1개이다.

 

  해결 방법  
 

• 이 문제에서는 트리가 주어졌을 때, 지정된 노드를 삭제했을 때의 리프 노드의 개수를 찾아야 합니다.
• 이 문제를 해결하기 위해선, 먼저 주어진 입력으로부터 트리 구조를 만들어야 합니다. 그 후, 삭제할 노드와 그 자식 노드들을 제거하고, 남은 트리에서 리프 노드의 개수를 셉니다.

import sys; input=sys.stdin.readline

def dfs(node):
    global count
    if not tree[node]:
        count += 1
        return
    for child in tree[node]:
        dfs(child)

N = int(input())
parents = list(map(int, input().split()))
delete_node = int(input())

tree = [[] for _ in range(N)]
root_node = 0

for i in range(N):
    if parents[i] == -1:
        root_node = i
        continue
    tree[parents[i]].append(i)

if delete_node == root_node: print(0); exit()
else:
    tree[parents[delete_node]].remove(delete_node)
    for i in range(N):
        if delete_node in tree[i]:
            tree[i].remove(delete_node)
    count = 0
    dfs(root_node)
    
print(count)

 

• 트리는 다양한 문제 유형에 활용되며, 코딩 테스트에서 자주 출제되는 주제 중 하나입니다. 따라서 트리의 개념과 탐색 알고리즘에 대한 이해와 적절한 접근 방법들은 코딩 테스트에서 좋은 성적을 거둘 수 있는 핵심 요소입니다.