데이터과학 유망주의 매일 글쓰기 — 77일차

재귀, 검색, 순회

# 재귀, #검색, #순회

이제부터 본격적인 알고리즘의 세계에 들어간다. Are you ready?

오늘 한일:

오늘은 어제 배운 연결리스트에 기반해 조금 더 심화된 데이터 구조인 트리(Tree)와, 반복문을 사용하지 않고도 더 효율적으로 일을 할 수 있는 재귀(Recursion)알고리즘에 대해 배웠다. 이제 본격적인 데이터 구조와 알고리즘의 세계로 온 것이다.

그렇다면 내가 오늘 배웠던 재귀, 검색, 순회의 개념들은 무엇일까? 나만의 언어로 요약해보았다.

검색(Searching) (1)

데이터를 여려 다양한 구조에 저장했을 때, 이들로부터 원하는 값을 찾기에 유용한 알고리즘이다. 가장 단순한 방법은 아무래도 데이터 구조에 속한 모든 구성원들을 돌면서 찾으려는 값에 매칭되는 값을 리턴받는 것이다. 이는 선형검색(Linear Search)이라고도 하는데 매우 비효율적이고 요즘엔 거의 사용되지 않지만, 조금 더 심화된 알고리즘을 생성하는데 있어 기반이된다는 면에서 학습할 가치가 있다.

Linear Search

이 검색에서는 시퀀스성 검색(sequential search)이 이루어지는데, 모든 아이템을 하나씩 조회하는 방식이다. 그러므로 모든 아이템을 체크하며, 찾으려는 값과 매칭된 값을 리턴받게된다. 만약 찾으려는 값이 없다고 해도, 데이터내 모든 아이템을 체크한다.

아래 프로그램은 찾으려는 값이 있는지 없는지를 True/False로 확인해주는 단순선형검색 프로그램이다. 찾으려는 값의 개수(values)를 지정해주고, 찾으려는 값(search_for)를 입력하면된다. 실제 검색 알고리즘은 이러한 선형검색이외에도 이진검색(Binary Search), Interpolation Search, 등등 다양한 알고리즘이 존재한다.

# 선형검색 함수 설정
def linear_search(values, search_for):
  search_at = 0
  search_res = False
  # 찾으려는 값(value)과 데이터내 모든 값을 매칭해보기
  while search_at < len(values) and search_res is False:
    if values[search_at] == search_for:
      # 매칭되면 아이템이 존재한다는 사실을 알림
      search_res = True
    else:
      # 매칭되지 않으면 해당 아이템의 다음 아이템 조회
      search_at = search_at + 1
  return search_res
# 샘플 데이터
l = [64, 34, 25, 12, 22, 11, 90]
# 찾으려는 값의 개수와 찾으려는 값 입력
print("해당 값이 존재하는가?: ",linear_search(l, 12))
print("해당 값이 존재하는가?: ",linear_search(l, 91))
>>
해당 값이 존재하는가?:  True 
해당 값이 존재하는가?:  False

재귀(Recursion)(2)

재귀란 정의된 함수가 스스로를 재호출한다는 의미다. 재귀는 가장 널리 활용되는 수학적인 개념이면서도 프로그래밍 알고리즘이다. 정의된 함수내에서 특정한 데이터를 계속 재호출 함으로써, 반복문을 활용하지 않고도 데이터내 복수의 아이템들을 조회할 수 있다는 장점이있다. 다만 함수안에서 함수 스스로를 재호출하는 방식이기 때문에, 종료 조건이 확실하게 정의되어 있지 않다면 무한한 반복에 빠질 수 있으니 사용시 매우 주의해야한다. 현실에서는 사용할 수 있는 메모리의 양과 프로세서의 전력이 한정되어 있기 때문이다. 그러나, 재귀는 적절히 사용한다면 매우 효율적이면서 수학적으로도 아름다운 프로그래밍 알고리즘이 될 수 있다.

아래 예제는 재귀 함수 tri_recursion()을 정의한 것인데, 6에서 1까지의 값을 더한 것을 리턴하고 다음 수인 5부터 1까지의 값을 더한 것을 리턴하면서, k-1에서 1까지의 값을 리턴하는 프로그램이라 할 수 있다. 다르게 보면, 1부터 값을 3, 6, 10, .. 등으로 모든 수가 k개수의 범위에 닿을때까지 k+1만큼 증가시키는 프로그램이다. 함수가 재호출 될때마다 k-1의 형태로 1씩 값이 줄어든다. 재귀함수는 k가 0이 될때 즉, 더 이상 1씩 줄어들 값이 없을 때 종료된다.

# 재귀함수 tri_recursion 정의
def tri_recursion(k):
  # 종료 조건: k = 0
  if(k>0):
    # 재귀함수를 k-1씩 감소시키며 재호출한다.
    result = k+tri_recursion(k-1) # k + k-1 + k-2 ... + 1
    # 결과를 표시하기
    print("1부터 {}까지의 합:{}".format(k, result))
  else:
    # 종료 조건일때는 0을 리턴
    result = 0
    return result

# 함수 호출 및 결과 출력
print("프로그램: 1부터 K범위의 값들의 합을 1에서 K만큼 출력하기")
tri_recursion(6)

>>

프로그램: 1부터 K범위의 값들의 합을 1에서 K만큼 출력하기
1부터 1까지의 합:1
1부터 2까지의 합:3
1부터 3까지의 합:6
1부터 4까지의 합:10
1부터 5까지의 합:15
1부터 6까지의 합:21
21

순회(Traversal)(3)

순회란 트리 데이터 구조에서 모든 노드를 조회하는 알고리즘을 말한다. 모든 데이터를 조회하면서 각 데이터를 표시(print)할 수도 있다. 모든 노드가 부모 자식의 관계를 가지고 있기 때문에, 트리의 가장 첫 부분인 루트(Head) 노드로 부터 내림차순으로 조회를 시작해야하며, 기존 컬렉션 자료와는 다르게 무작위로 값이나 인덱스, 또는 키에 따라 노드를 조회하는 것은 불가능하다.

트리를 순회하는 방식에는 크게 3가지가 있는데, 다음과 같다.

• In-Order Traversal
• Pre-Order Traversal
• Post-Order Traversal

1. In-Order Traversal

슷자가 작은 순서에서 큰 순서로 차례대로 트리의 데이터를 정렬해 순회하는 방법이다. 이러한 순회 방법에서는 왼쪽 서브트리가 먼저 조회되며, 이후 루트, 오른쪽 서브트리의 방향으로 데이터를 조회한다. 주의할 것은, 모든 노드는 서브트리 자체를 나타낼 수 있다는 것이다.

아래 코드 예제에서는, Node 클래스를 통해 루트 노드와 왼쪽 노드 및 오른쪽 노드의 생성에 대한 규칙을 만든다. 이후 삽입 기능을 구현하여 트리에 데이터를 삽입할 수 있는 함수를 만든다. 마지막으로, In-order Traversal을 할 수 있도록 empty list를 초기화하고, 왼쪽 노드부터 오른쪽의 루트, 부모 노드 순으로 더한다. 여기서, 왼쪽 노드는 In-Order Traveral을 할 수 있도록 추가되었다. 주의할 것은, 트리의 모든 노드가 조회될 때까지, 각 서브트리에 대해 이 과정이 반복된다는 것이다.

# Node 클래스 선언
class Node:
  def __init__(self, data):
    self.left = None
    self.right = None
    self.data = data
  # 노드 삽입 기능 함수 구현
  def insert(self, data):
    if self.data:
      if data < self.data:
        if self.left is None:
          self.left = Node(data)
        else:
          self.left.insert(data) 
      elif data > self.data:
    if self.right is None:
      self.right = Node(data)
    else:
      self.right.insert(data)
  else:
    self.data = data
  # 트리 출력 함수
  def PrintTree(self):
    if self.left:
      self.left.PrintTree()
    print( self.data),
    if self.right:
      self.right.PrintTree()
# Inorder traversal 로직
# 왼쪽 -> 루트 -> 오른쪽의 순서로 조회
def inorderTraversal(self, root):
  res = []
  if root:
    res = self.inorderTraversal(root.left)
    res.append(root.data)
    res = res + self.inorderTraversal(root.right)
  return res
# 위 클래스를 객체화하여, 노드를 삽입하고 트리를 만들기
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
# 완성된 트리에 대한 In-Order Traversal
print(root.inorderTraversal(root))
>> [10, 14, 19, 27, 31, 35, 42]

2.Pre-order Traversal

이 순회 방법에서는 루트 노드를 먼저 조회하고, 이후 왼쪽 서브트리에서 오른쪽 서브트리 방향으로 조회한다. 아래 예제에서는, 이전 In-Order Traversal처럼 Node 클래스를 선언하고, 삽입 기능을 구현한다. 이후, 텅빈 리스트를 초기화하고 루트 노드를 먼저 더한후에, 왼쪽 노드와 오른쪽 노드를 더해 Pre-Order Traversal을 구현한다. 이 순회방법 역시 모든 노드가 조회될때까지 각 서브트리에 반복되어 적용된다.

# Node 클래스 선언
class Node:
 
    def __init__(self, data):
 
        self.left = None
        self.right = None
        self.data = data
    # 노드 삽입 기능 함수 구현
    def insert(self, data):
 
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
 
    # 트리 출력 함수
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
 
# Preorder traversal 로직
# 루트 -> 왼쪽 -> 오른쪽의 순서로 조회
    def PreorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.PreorderTraversal(root.left)
            res = res + self.PreorderTraversal(root.right)
        return res
 
# 위 클래스를 객체화하여, 노드를 삽입하고 트리를 만들기
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
# 완성된 트리에 대한 Pre-Order Traversal
print(root.PreorderTraversal(root))
>> [27, 14, 10, 19, 35, 31, 42]

3. Post-order Traversal

이 순회 방법은 루트 노드를 가장 마지막에 조회한다. 왼쪽 서브트리부터 시작하여 오른쪽 서브트리, 마지막으로 루트를 조회하는 방식이다. 아래 코드 예제에서도 Node 클래스를 정의했고, 삽입 기능을 구현했다. Post-Order Traversal을 위해 이번에는 라스트에 왼쪽 노드를 먼저 더하고, 오른쪽 노드를 더했고, 마지막으로 루트 노드를 더했다. 이 순회 방법 역시 모든 노드를 조회할 때까지 각 서브트리에 대해 적용된다.

# Node 클래스 선언
class Node:
 
    def __init__(self, data):
 
        self.left = None
        self.right = None
        self.data = data
    # 노드 삽입 기능 함수 구현
    def insert(self, data):
 
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
 
    # 트리 출력 함수
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
 
# Postorder traversal 로직
# 왼쪽 -> 오른쪽 -> 루트의 순서로 조회
    def PostorderTraversal(self, root):
        res = []
        if root:
            res = self.PostorderTraversal(root.left)
            res = res + self.PostorderTraversal(root.right)
            res.append(root.data)
        return res
 
# 위 클래스를 객체화하여, 노드를 삽입하고 트리를 만들기
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
# 완성된 트리에 대한 Post-Order Traversal
print(root.PostorderTraversal(root)) 
>>> [10, 19, 14, 31, 42, 35, 27]

앞으로 할일:

오늘은 재귀 및 검색이라는 알고리즘과, 트리 구조에서 사용할 수 있는 알고리즘인 순회에 대해 알아보았다. 순회에 대해서는 오늘 자세히 배우지는 않았고, 사실 내일 배울 내용인데, 예습을 한 것이라 볼 수 있다. 오늘 트리 구조를 배우니, 순회의 개념은 그렇게 어렵게 느껴지지 않았다.

검색 알고리즘 역시, 연결리스트에서 처음부터 끝까지 데이터를 조회하는 방식이라 그렇게 어렵게 느껴지지 않았다. 물론 오늘 다룬 선형검색보다 더 복잡한 알고리즘을 만나게 되면 또 다르겠지만.

특히, 재귀 함수를 이해하는 것이 생각보다 좀 어려웠다. 포프TV라는 유명한 프로그래머 유튜버의 영상을 보니, 재귀 함수 알고리즘을 잘 알고쓰면 정말 유능한 프로그래머로써 인정받을 수 있다는 느낌이들었다. 사실 오늘 보고 들은 내용 만으로는 재귀의 사용 방법이 정확히 이해가 가지않아 앞으로도 계속 공부하면서 활용해 보아야겠다는 생각이든다.

사실, 내가 이번 주와 다음 주까지 다룰 수 있는 알고리즘은 많지 않을 것이다. 정말 다양한 데이터 구조와 알고리즘이 있고, 지금도 계속 정리되고 있다고 한다. 최근에 비트코인으로 잘 알려진 블록체인(Blockchain)과 같은 데이터 구조역시 새로운 개념의 데이터 구조다.

하지만, 블록체인도 최근에 배운 연결리스트에 기반하고 있는 만큼, 기본적인 데이터 구조를 이번에 잘 익혀 놓으면 조금 더 심화된 개념도 배울 수 있을 것이라는 생각이든다. 더 복잡한 알고리즘도 오늘 다룬 선형 검색이나 재귀만 제대로 터득해도 더 쉽게 배울 수 있다고 하니, 무엇보다도 기초를 쌓는게 중요하다는 것을 다시 한번 느꼈다.

그러나, 이러한 개념들을 이해하는 것과, 어떻게 사용할 줄 아는 것은 조금 다르다고 생각한다. 프로그래밍 세계에서는 개념을 이해하는 것 보다도, 그 것을 적재적소에 적용하는 것이 더 힘든 것 같다는 생각이 든다. 아무리 많은 것을 알고 있어도 그것을 사용하지 않고, 사용할 줄 모른다면 죽은 지식이나 다름없다. 프로그래밍을 공부하면서 그 것이 정말 꼼짝할 수 없는 사실이라는 것을 절실히 느낀다. 단순히 이해하는 것에서 끝나지 않고, 내 손가락이 반응할 수 있을 정도로 연습하는 것이 가장 좋은 학습법이라는 생각이 든다. 마치 수학 공부도 원리를 더 많이 이해하는 것보다, 문제를 더 많이 풀어보는 것이 더 효과적인 학습 방법인 것처럼.

프로그래밍의 넓고도 깊은 세계에 초대 받게 되어서 기쁘다. 이 세계는 내 생각보다 방대하고 무한하지만, 여기서 헤엄치면서 새로운 것을 발견하고 싶다. 앞으로 내가 프로그래밍을 평생의 업으로 삼을 수 있을지는 확신할 수 없지만, 이 재미난 세계에서 더 흥미로운 개념들과 기술들을 익히는 것을 멈추고 싶지 않다는 생각이든다. 이번 기회를 통해 진정한 프로그래밍의 매력을 느낄 수 있게 된 것에 매우 감사하며, 앞으로도 컴퓨터의 언어를 공부하는 것을 게을리 하지 않겠다고 다짐해 본다.

내일도 새롭게 배울 지식이어, 내게 오라!

참조:

(1) Python - Searching Algorithms, TutorialsPoint

(2) Python Function Recursion, W3School

(3) Python — Tree Traversal Algorithms, TutorialsPoint