트리 알고리즘 (1 - 개요)

 

 

○들어가는 글

     우선 이번 시간에는 알고리즘 중, 우리에게 흔히 배낭 문제라고 알려진 knapsack 알고리즘의 대해서 다뤄보려고 하였습니다. 나중에 글을 쓰겠지만 트리를 이용해서 모든 노드를 순회하는 알고리즘과, 이를 greedy 알고리즘으로 개선해서 좀 더 효율적으로 노드를 순회하는 2가지 방법에 대해서 알아보려고 했습니다.

     하지만 우선, 그 전에 재귀 알고리즘으로 트리를 구성하고, 또 순회의 방법에 대해서 다룰 수 있고, 이가 한 파트가 될 수 있겠다 싶어서 가장 먼저 다루게 되었습니다.

 

 

○ 트리

     트리의 가장 큰 특징이라고 한다면 루트 노드로부터 뻗어져 나오는 그래프의 모양일 것입니다. 특히 저는 트리라고 한다면 이진 트리가 가장 먼저 떠오릅니다. 아마 가장 간단한 형식이고, 눈에도 쉽게 들어오기 때문일 것입니다. 우선 이진 트리를 기준으로 설명해 보겠습니다.

     이진 트리는 다음과 같습니다. 0과 1이라는 2가지 조건이 있을 때, 한 노드에서 각 조건의 경우의 따라 간선으로 타고 새로운 노드로 이어집니다. 그리고 또 그 한 노드에서 다른 노드로 간선을 타고 노드로... 또다시 노드로...

즉 우리는 트리가 노드를 기준으로 재귀적인 형태를 띠고 있음을 알 수 있습니다. 즉 우리는 이를 재귀 알고리즘으로 구현할 수 있을 것입니다.

 

 

○ 트리의 구성요소

     아직 직접 구현해 본 적은 없지만, 재귀적인 형태 말고도, 스택을 이용해서 구현 할 수 있는 것으로 알고 있습니다. 우선 이번 글에서는 재귀적인 방법으로 구현해 보도록 하겠습니다.

     우리가 가장 먼저 해야 하는 것은 관찰입니다. 한번 노드를 잘 관찰합시다. 우선 이진 트리에서 노드 하나만 보자면 2가지로 이루어져 있는 것을 알 수 있습니다.

 

1. 노드(Node) 자기 자신은 1개

2. 2갈래로 뻗어 나가는 간선(Edge) 2개

 

     이러한 구성요소를 가지기 때문에 이진 트리를 재귀적인 형태로 구현할 때 우리에게 필요한 것은 크게 2가지입니다.

 

1. 재귀의 형태를 가지는 함수

2. 노드에서 2가지로 뻗어 나가는 2가지 조건

 

그림으로 표현한다면 다음과 같을 것입니다.

 

 

○ 이진 트리의 구현

     구성요소를 알았으면 한번 트리를 구현해봅시다. 위에서 설명했듯이 이진 트리는 분기가 되는 형태라는 점을 알려드렸습니다. 또한 재귀적인 형태라는 점도 알려드렸습니다. 이러한 점을 비추어 볼 때 이진 트리는 결국 함수 내에서 자기 자신을 2번 호출하는 것으로 구현할 수 있음을 알 수 있습니다.

그림을 보면서 한번 알아봅시다.

 

 

 

○ 이진 트리의 예제

한번 이러한 조건을 가지는 이진 트리를 구현해 보도록 하겠습니다.

 

변수 N 이 0일 때, 노드의 한쪽은 N을 1 증가시키고, 노드의 다른 한쪽은 그냥 통과한다.

 

     한번 그림으로 그려보도록 하겠습니다. 만약 그려본다면 트리의 처음(Root)부터 트리의 마지막(Leaf)까지는 다음과 같을 것입니다. (트리가 너무 깊으면 노드가 많아지니, 트리의 높이는 한 3 정도로 해봅시다.

 

 

우리가 위에서 배운 것을 활용한다면 이를 다음과 같이 구현할 수 있을 것입니다. 한번 실행하고 결과를 출력해 봅시다.

언어는 kotlin으로 작성하였으며 아래 주소로 들어가시면 코드가 돌아가는 것을 확인 할 수 있을 것입니다.

Kotlin Playground: Edit, Run, Share Kotlin Code Online

fun main() {
    
    val n = 3
    
    tree(0,n,0)
    
}

fun tree(num : Int, h : Int, idx : Int) {
    
    if(h==idx) {
     	print("$num ")
       	return    
    }
    
    tree(num+1,h,idx+1)
	tree(num,h,idx+1)  
   
}

위 코드는 tree라는 재귀함수를 만들었으며, 높이가 4인 트리를 만들고 있습니다.  결과는 다음과 같습니다. 출력의 순서가 위와 동일 하다는 것을 알 수 있습니다. 

 

 

○ 활용

     사실 눈치가 빠르신 분이라면 알겠지만, 이를 이진 트리에만 적용할 필요는 없습니다. 이진 트리는 노드에서 2개로 뻗어 나가는 트리이지만, 트리는 3개 4개의 노드로 뻗어 나갈 수 있음을 알 수 있습니다. 그렇다면 이러한 트리를 만들기 위해서는 나뉘는 노드의 수만큼, 함수 내에서 재귀 함수를 호출하는 방법으로 트리를 구현 할 수 있을 것입니다.

 

 

○ 더 나아가서

     이번 글에서는 트리의 구성요소와 이를 통해 트리를 구현하는 것에 대해서 알아보았습니다. 다음 시간에는 트리의 노드 간의 순회에 대해서 방법이 있고, 이를 어떻게 순회하는지에 대해서 알아보려고 합니다. 다음 시간에 뵙겠습니다. 감사합니다.