알고리즘(2) - 비선형 자료구조, 재귀(Recursion)

안녕하세요.

 

오늘은 어제 배웠던 선형 자료구조에 이어서 비선형 자료구조인 트리구조와 재귀(Recursion)에 대해서 알아보려고 합니다.

 

 

비선형 자료구조

 

트리(Tree)

 

1. 트리의 용어

• 루트(Root) : 가장 위쪽에 있는 노드, 트리별 하나만 있습니다.
• 서브트리 : 자식노드이면서 부모노드역할을 하는 노드가 있는 트리, 그림상에 (5,3,6노드를 하나의 서브트리로 볼 수 있습니다.)
• 차수 : 노드가 갖고 있는 최대 자식노드 수
• 리프(Leaf) : 레벨별로 가장 마지막에 있는 노드, 단말노드(terminal node), 외부노드(external node)라고도 합니다. 리프는 트리별로 여러 개가 있을 수 있습니다.
• 레벨(Level): 루트노드에서 얼마나 멀리 떨어져 있는지 각각 나타냅니다.
• 높이(Depth) : 루트에서 가장 멀리 떨어진 리프노드까지의 거리이며, 리프 레벨의 최대값을 높이라고 합니다.
• sibling(형제) 노드 : 부모가 같은 두 개의 노드

 

2. 이진트리(Binary Tree)의 종류

 

이진 트리란?

 

 - 여러 트리종류 중에서 가장 기본이 되면서 많이 활용되는 트리입니다.

 - 각 노드별로, 최대 2개의 서브노드를 가지고 있는 트리입니다.

 - 자식노드가 꼭 값을 가져야 하지는 않습니다.

 

 

1. 완전 이진 트리(Full binary tree)

 - 서브트리의 노드가 반드시 채워져 있어야 하는 것은 아니지만 왼쪽으로부터 순차적으로 채워져 있어야 합니다.

 - (A)는 완전 이진 트리라고 할 수 있지만 (B)는 완전 이진 트리라고 할 수 없습니다.

 

 

2. 포화 이진 트리(Perfect binary tree)

 - 모든 리프노드들이 동일한 레벨을 가지고 있어야 합니다.

 

 

3. 이진 검색 트리(Binary search tree)

 

 - 노드들이 정확하게 왼쪽에서부터 오른쪽으로, 작은 수부터 큰 수로 정렬되어 있어야 합니다.

 - 중복값을 가지고 있으면 안됩니다.

 - 위의 조건을 ' 값 크기 조건 ' 이라고 하고 이렇게 구조가 정해져 있는 이유는 왼쪽부터 오른쪽으로 검색을 하는 구조를 갖추기 위해서입니다.

 

<이진 검색 트리 구현>

class node:
    def __init__(self, value):
        """
        bst에서 사용할 수 있는 node 클래스를 작성
        """
        self.value = value
        self.left = None
        self.right = None
        
class binary_search_tree:
    def __init__(self, head):
        """
        문제 2.
        bst의 생성자 메소드를 작성
        """
        self.head = head

# 노드를 추가하는 함수
    def insert_node(self, value):
    
		self.base_node = self.head
        
        while True:
            if self.base_node.value > value:
                if self.base_node.right != None:
                    self.base_node = self.base_node.right
                else:
                    self.base_node.rignt = node(value)
                    break
            else:
                if self.base_node.left != None:
                    self.base_node = self.base_node.left
                else:
                    self.base_node.left= node(value)
                    break
        
# 노드값을 찾는 함수
    def search_node(self, value):
    
        self.base_node = self.head
        
        while self.base_node:
            if self.base_node.value == value:
                return True
            else:
                if self.base_node.value > value:
                    if self.base_node.left != None :
                        self.base_node = self.base_node.left
                    else:
                        return False
                else:
                    if self.base_node.right != None:
                        self.base_node = self.base_node.right
                    else:
                        return False

❄️ 위의 코드를 하나하나씩 실행하면서 머리 속으로 그림을 그려보세요.

예를들어 if self.head.right != None : (루트노드에 오른쪽에 있는 자식노드의 값이 None이 아니면), self.head = self.head.right(포인터를 오른쪽으로 옮기겠다.) 와 같이요.

 

 

재귀(Recursion)

 

재귀란?

• 자기자신을 호출하는 방식
• 종료조건(break, etc)이 있어야 재귀함수가 정상 작동합니다.(무한반복 금지)
• 반복문과 스택 구조가 결합된 방식입니다.

#스택이 쓰이는 지 확인하기

def countdown(num):
  if num==0:
    print('발사')
  else:
    countdown(num-1)
    print(num)
    
# 과연 결과값이 어떻게 출력될까요?
countdown(3)
#3,2,1,발사 vs 발사,1,2,3

 

 

재귀함수의 장점

• 코드가 간결해집니다.
• 반복문을 따로 사용하지 않아도 됩니다.

 

재귀함수의 단점

• 유지보수가 어렵습니다. -> 이해하는 사람이 적습니다.
• 메모리를 많이 사용합니다.(파이썬에서는 사용가능한 재귀호출 수가 정해져 있어 그 수를 넘으면 stack over flow가 됩니다.)

 

 

재귀방식은 실무에서는 잘 사용되지 않는다고 합니다. 그럼에도 취직을 위한 코딩테스트에서는 필요한 부분이니 프로그래머스나 백준을 통해 충분히 학습을 해야할 거 같습니다.