정글사관학교 19일차 TIL: 트리 순회, 이진 검색 트리, Union-Find(유니온 파인드) 알고리즘

0. 목차

 

1. 트리 순회 - Preorder / Inorder / Postorder

2. 이진 검색 트리 - 재귀를 활용해 검색하는 방법

3. 서로소 집합 구조 & 유니온 파인드 & 크루스칼 알고리즘: 서로소인 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

 

 

1. 이진 검색 트리 & 데이터 탐색 방법: 트리 순회 - Preorder / Inorder / Postorder

 

개념 정리부터 먼저 하고 넘어가자.

 

이진 트리란, 부모 노드가 왼쪽/오른쪽 자식 이렇게 두 개의 자식 노드만을 갖는 트리를 말한다. 이때, 왼쪽/오른쪽 자식을 구분한다. 이진 트리에 대한 보다 자세한 정리는 아래 챕터에서 하기로 하고, 여기서는 곧바로 문제를 보면서 이진 트리에서 데이터를 탐색하는 방법인 트리 순회에 대해서 다루겠다.

 

먼저 트리 순회를 하기 위한 전제는 이 트리가 전부 이진트리로 구성되어있어야 한다는 점이다. 단, 이전에 힙 정렬에 대해 정리한 내용에서는 완전 이진 트리만 다뤘다면, 여기서는 보다 포괄적인 범위에서의 이진 트리를 다룬다. 포괄적인 범위에서의 이진 트리는 완전 이진 트리와 같이 반드시 왼쪽부터 작은 값이 채워질 필요가 없다.

 

1번 문제 링크 는 여기.

 

트리 순회에는 아래와 같이 크게 세 가지 방식이 있다. 사실 네 가지인데 여기서 소개하지 않는 하나는 BFS를 포함하는 레벨 순회(층위별로 순회하는 방식)이다.

 

1. Preorder traversal (전위 순회): 노드 자신을 방문 -> 왼쪽 자식 노드 방문 -> 오른쪽 자식 노드 방문

먼저 자기 자신을 처리한 다음, 왼쪽 자식 노드를 방문하고 뒤이어 오른쪽 자식 노드를 방문하는 순서로 이어진다. 자기를 처리하고 나서 왼쪽 자식 노드를 방문하면, 그 시점을 기준으로 왼쪽 자식노드는 자기 자신이 되고 이떄의 자신을 기준으로 자신 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드를 방문하는 순서가 반복된다. 즉, 재귀를 활용하면 된다는 뜻이다.

 

이를 코드로 구현하면 아래와 같다.

 

class Node:
    def __init__(self, item, left, right) -> None:
        self.item = item # 부모 노드 저장
        self.left = left # 왼쪽 자식 노드
        self.right = right # 오른쪽 자식 노드

def preorder(node): # 전위 순회: 자기 자신 방문 -> 왼쪽 자식 -> 오른쪽 자식
    print(node.item, end="")
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])

 

2. Inorder traversal (중위 순회):  왼쪽 자식 노드 방문 -> 노드 자신을 방문 -> 오른쪽 자식 노드 방문

왼쪽 자식 노드를 먼저 처리한 다음, 뒤이어 자기 자신을 처리한다. 그 다음에 오른쪽 자식 노드를 방문한다. 마찬가지로 재귀를 이용한다.

class Node:
    def __init__(self, item, left, right) -> None:
        self.item = item # 부모 노드 저장
        self.left = left # 왼쪽 자식 노드
        self.right = right # 오른쪽 자식 노드


def inorder(node):
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end="")
    if node.right != '.':
        inorder(tree[node.right])

 

3. Postorder traversal (후위 순회)

마지막 순회인 후위 순회는 왼쪽 자식과 오른쪽 자식을 다 방문하고 나서 마지막으로 자기 자신을 방문하는 순서로 순회한다. 여기까지 보면 대략 예상하겠지만, 전/중/후위 순회는 모두 코드가 동일하다. 그저 무엇을 먼저 방문하고 나중에 방문할 것인지에 대한 순서 차이만 있을 뿐이다.

def preorder(node): # 전위 순회
    print(node.item, end="")
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])
    
def inorder(node):# 중위 순회
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end="")
    if node.right != '.':
        inorder(tree[node.right])

def postorder(node): # 후위 순회
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    print(node.item, end="")

전체적인 구성은 똑같고 if(left) / if(right) / print(자기자신)의 순서만 다르기 때문에 이에 유념해서 클래스를 생성해 코드를 짜면 끝.

 

문풀에 참고한 링크는 여기.

 

2. 이진 검색 트리(Binary Search Tree, BST) - 재귀를 활용해 검색하는 방법

다음은 이진 검색 트리에 대해 소개한다.

위에 비해 훨씬 더 까다로웠는데 난이도 하라니..(백준 난이도 기준으로는 골드4인데 정글 난이도 기준에서는 "하"다. 하하하...)

 

위에서 미처 덜했던 이진 트리 및 이진 검색 트리에 대한 정리를 여기서 마저 진행하겠다.

 

이진 트리의 정의는 위에서 소개했으니, 이진 검색 트리에 대해 좀 더 알아보자. 이진 검색 트리는 모든 노드가 아래 조건을 만족하는 이진 트리를 말한다.

 

1. 왼쪽 서브트리(자식) 노드의 키값은 자기 자신의 노드 키값보다 작아야 한다. (왼쪽 자식 노드 < 부모 노드)
2. 오른쪽 서브트리 노드의 키값은 자기 자신의 노드 키값보다 커야 한다. (오른쪽 자식 노드 > 부모 노드)
* 위의 두 경우를 만족하려면 키값이 같은 노드는 복수로 존재할 수 없게 된다.

이진 검색 트리의 특징은 다음과 같다.

• 구조가 단순하다.
• 중위 순회의 깊이 우선 탐색의 경우 노드값을 오름차순으로 얻을 수 있다.
• 노드 삽입이 쉽다. (O(logN))

이진 검색 트리는 포인터를 이용해서 만든다. 아래 그림과 같이, 노드 클래스는 아래와 같이 구성되며, 하나의 트리는 4개의 필드를 갖는다. 

 

1. key(키)
2. value(자기 자신 노드의 값)
3. left(왼쪽 자식 노드에 대한 참조 => 포인터를 이용)
4. right(오른쪽 자식 노드에 대한 참조 => 역시 포인터를 이용)

아직 포인터를 제대로 배우지 않아 포인터가 정확히 어떤 걸 말하는지는 모르겠으나, 대략 감으로 보면 다른 공간에 있는데 그걸 가리키는 도구?인 것 같다. 아래 이미지처럼 일종의 연결된 실 같은 게 아닐지. left 안에는 실제 값이 들어있는 게 아니라 다른 공간에 있는 left에 해당하는 노드에 있는 value값을 불러오는 것일듯.

 

 

워낙 포인터가 어렵다고 하는데, 굳이굳이 이진 검색 트리를 포인터로 만들어야 할 이유가 있을까? 당연히 있다. 이진 트리의 경우, 힙 정렬(=완전 이진 트리)과 달리 완전 이진 트리의 형태가 아닌 경우가 더 많다. 예컨대 오른쪽 자식 노드로만 연결되어 있는 2 - 6 - 14 이런 케이스도 엄연히 이진 트리다. 그런데 이걸 완전 이진트리로 구현하게 되면? 쓸데없는 데이터가 덕지덕지 달라붙는다. 아래 예시 이미지를 보자. 0-2-6-14라는 이진 트리 하나를 완전 이진 트리로 구현하기 위해서는 0부터 14까지 전혀 필요없는 데이터까지 만들어줘야한다.

 

 

포인터로 이진 검색 트리를 구현하면 이런 낭비를 줄일 수 있어 복잡도가 줄어든다는 이점이 있다.

 

이와 관련된 문제는 요거인데, 오늘은 개념 위주로 정리할 생각이라 이 문제에 대한 풀이는 내일로 패스. 풀이 참고한 링크만 공유한다.

 

풀이 링크 1(더 긴 ver => 이해하기에는 good)

풀이 링크 2(더 짧은 ver)

 

3. 서로소 집합 구조 & 유니온 파인드 & 크루스칼 알고리즘: 서로소인 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

 

마지막으로 유니온 파인드. 오늘 배운 개념 중 가장 신박한 내용이었다. 중요도로 치면 이진 (검색) 트리가 훨씬 중요할 것 같지만 유니온 파인드를 알면 그래프 관련 많은 문제를 해결할 수 있다.

 

강의는 나동빈 강의를 참고했다. (굉장히 좋으니 꼭 보시길!)

 

서로소 집합 자료구조

서로소인 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다.

• 합집합으로 합치기(Union): 두 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

맞다. 그래서 Union-Find가 여기서 나온 개념이었다! 구글링하니 다들 이상한 말만 해대서 도저히 이해가 어려웠는데 여기서 아주 명쾌깔끔하게 설명해준다 ㅎㅎ 즉, 서로소 집합 자료구조에서 지원하는 연산이  1)Union & 2) Find 이다.

 

여러 개의 union find 연산이 주어질 때, 서로소 집합 자료구조가 어떻게 동작하는지 살펴보자.

 

• 먼저 합집합 연산을 시도한다. 서로 연결된 두 노드 A, B를 확인한다.
  • 이때 A와 B 각각의 루트 노드 A', B'을 찾는다.
  • 둘 중 더 작은 값에 해당하는 루트 노드(예컨대 여기서 A' < B'이라면)를 더 큰 루트 노드의 부모 노드로 설정(*)한다.
• 모든 합집합 연산을 처리할 때까지 위의 과정을 반복한다.

(*) 다른 유니온 파인드 관련 설명을 볼 때 저 부분을 생략하고 적어놔서 도통 이해되지 않았던 건데, 이제야 알았다. 일반적으로 합치기 연산을 수행할 때는 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 만들어서 테이블을 갱신하는 것이 관행이라고 한다! (노드의 값이 아닌 인덱스 자체는 누가 크던 작던 상관이 없어서 왜 이렇게 하는지 이해 못했는데 관행이라고 하니, 그러려니 하며 받아들이자! 어차피 크거나 작거나 일관된 방향성이 있어야 정렬이 가능하다.)

 

아래 예시를 보자. 모두 다 서로소인 노드 1, 2, 3, 4, 5, 6이 있다고 해보자. 이때, 우리는 합집합 연산으로 1과 4, 2와3, 2와4 5와6에 대해 처리할 것이다. 기본적인 세팅을 보면 각 노드는 서로 연결되어 있지 않으며, 따라서 자기 자신을 부모 노드로 갖고 있다. 즉, 초기 단게에서 서로 다른 집합이다.

• Union(1, 4): 4와 1을 비교한다. 4가 더 큰 값이니 1을 4의 부모 노드로 설정한다. (참고로 이때 1, 4는 해당 노드에 들어가는 value가 아니다! 착각 ㄴㄴ! 1번 노드, 4번 노드를 지칭하는 인덱스 번호다!)
• Union(2, 3): 2와 3을 비교. 각 노드의 루트는 원래 각각 2, 3이었는데 3이 더 작은 2를 가리키도록 설정을 바꾼다. 즉, 3번 노드의 부모 노드는 2번이 된다.

여기까지 한 작업을 보면 아래와 같이 나타낼 수 있다. 아래 테이블을 보면, 부모 노드가 바뀐 것을 볼 수 있다. 이때 주의해야 할 점은, 아래 테이블은 각 노드의 루트를 나타내는 테이블이 아닌 바로 윗 노드에 해당하는 부모 노드를 말한다.

 

모든 합집합 연산 작업을 끝나면 아래와 같이 연결되는 걸 볼 수 있다. 집합 {1, 2, 3, 4}의 경우 루트는 1이지만 아래 테이블에서는 부모만 표시되어 있다.

이렇게 유니온 연산으로 {1,2,3,4}, {5, 6} 두 집합이 만들어진다. 여기서 이 두 집합은 어떤 원소도 서로 공유하지 않으니 서로소이다.

 

위와 같은 형태(노드와 부모를 연결해놓는 식)의 서로소 집합 자료구조는 가장 기본적인 형태이나 문제점이 하나 있다. 바로, 특정 노드를 선택했을 때 그 노드의 루트 노드로 즉시 접근이 불가능하다는 점이다. 루트 노드를 찾기 위해서는 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다. 예컨대 위의 이미지에서 3의 루트 노드를 찾기 위해서는 3-> 2-> 1을 거쳐야 루트를 찾는다.

 

따라서 최악의 경우를 고려한다면 합집합 연산이 편향되게 이뤄질 경우 루트를 찾는 Find 함수가 비효율적으로 동작하게 될 것이다. 모든 노드가 한 방향으로 연결되어 있는 케이스를 생각해보자. 이때, 가장 아래에 있는 자식 노드에서 루트를 찾으려 하면 시간복잡도는 O(N)에 해당한다. 

 

 

따라서 루트 찾기를 최적화하기 위한 방법으로 재귀를 이용한 경로 압축을 이용한다. 찾기 함수를 함수 내에서 재귀적으로 호출해 테이블에 부모 노드가 아닌 해당 노드의 루트 노드를 바로 가져오게 한다. 위의 케이스의 경우, 모든 노드의 루트가 동일하므로 아래 이미지와 같이 노드가 1개 층으로 단순해진다.

 

 

문제풀이 및 크루스칼 알고리즘 소개는 내일...