백트래킹 & 트리

• 백트래킹

완전 탐색 + 가지치기

가능성이 없는 경우의 수를 제거하는 기법

가지치기 (prunning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않음.

Tip : 백트래킹 코드를 작성할 때 가지치기 하는 과정에서 유망한 조건을 따져서 경로를 이어갈 수도 있지만, 유망하지 않은 조건을 따져서 걸러내는 방법이 보통 코드가 더 깔끔해진다.

 

• 백트래킹과 깊이 우선 탐색의 차이

백트래킹은 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다. (prunning 가지치기)

반면, 깊이 우선 탐색은 모든 경로를 추적하기에 경우의 수가 너무 많으면 처리가 불가능하다.

그러나 백트래킹 알고리즘도 일반적으로는 경우의 수를 줄이지만 이 역시 최악의 경우에는 여전히 지수함수 시간을 필요로 하기 때문에 처리가 불가능해진다.

 

• 트리

싸이클이 없는 무향 연결 그래프 :

싸이클 → 방문했던 노드로 다시 돌아오는 다른 경로가 있다.

무향 → 방향이 없다

연결 그래프 → 모든 점이 서로 갈 수 있는 경로가 있다.

 

두 노드(정점) 사이에는 유일한 경로가 존재한다.

각 노드는 최대 하나의 부모노드가 존재할 수 있다.

각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있다.

 

비선형 구조 :

원소들 간에 1:n 관계를 가지는 자료 구조

원소들 간에 계층 관계를 가지는 계층형 자료구조

 

트리는 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.

1. 노드 중 부모가 없는 노드를 루트(root)라 한다.
2. 나머지 노드들은 n개의 분리 집합으로 분리될 수 있다.

 

노드 : 트리의 원소이고 정점이라고도 한다.

간선 : 노드를 연결하는 선

루트 노드 : 트리의 시작 노드

 

• 차수

노드의 차수 : 노드에 연결된 자식 노드의 수

트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값

단말 노드 = 리프 노드 : 차수가 0인 노드 = 자식 노드가 없는 노드

 

• 높이

노드의 높이 : 루트에서 노드에 이르는 간선의 수 = 노드의 레벨

트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값 = 최대 레벨

 

• 트리 개발 버전

arr = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6, 4, 7, 5, 8, 5, 9, 6, 10, 6, 11, 7, 12, 11, 13]

# 정석 개발 버전
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, child):
        # 왼쪽에 삽입 시도
        if not self.left:
            self.left = child
            return

        # 오른쪽에 삽입 시도
        if not self.right:
            self.right = child
            return

        # 삽입 실패
        return

    def inorder(self):
        if self != None:
            # 왼쪽이 있으면 계속 탐색
            if self.left:
                self.left.inorder()

            # 오른쪽이 있으면 계속 탐색
            if self.right:
                self.right.inorder()

            print(self.value, end=' ')

# 이진 트리 만들기
# 1. 노드들을 생성
nodes = [TreeNode(i) for i in range(0, 14)]

# 2. 간선 연결
for i in range(0, len(arr), 2):
    parent_node = arr[i]
    child_node = arr[i+1]
    nodes[parent_node].insert(nodes[child_node])

nodes[1].inorder()

 

• 트리 인접리스트 활용 버전

arr = [1, 2, 1, 3, 2, 4, 3, 5, 3, 6, 4, 7, 5, 8, 5, 9, 6, 10, 6, 11, 7, 12, 11, 13]

# 코딩테스트에서는 간단하게
nodes = [[] for _ in range(14)]
for i in range(0, len(arr), 2):
    parent_node = arr[i]
    child_node = arr[i+1]
    nodes[parent_node].append(child_node)

# 자식이 없다는 걸 표시하기위해 None
for li in nodes:
    for _ in range(len(li), 2):
        li.append(None)

# 중위순회 구현
def inorder(nodeNum):
    # 갈 수 없다면 skip
    if nodeNum == None:
        return

    # 왼쪽으로 갈 수 있다면 진행
    inorder(nodes[nodeNum][0])
    print(nodeNum, end=' ')
    # 오른쪽으로 갈 수 있다면 진행
    inorder(nodes[nodeNum][1])

inorder(1)

 

• 이진 트리 : 모든 노드들이 최대 2개의 자식 노드를 갖는 트리

 

• 이진 트리의 특성

레벨 i 에서의 노드 최대 개수는 2**i 개

높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1 이며, 최대 개수는 (2**h+1) - 1 이다.

노드의 개수가 N개일 때, 이진 트리의 높이 h는 최소 logN, 최대 N이다.

 

• 포화 이진 트리

모든 레벨에 노드가 포화상태로 채워져있는 이진 트리

 

• 완전 이진 트리

왼쪽부터 자리가 다 채워져 있는 이진 트리 (자리가 있는 부분까지는 포화 이진트리와 같음)

 

• 편향 이진 트리

한쪽 방향의 자식 노드만을 가진 이진 트리, 최소 개수의 노드를 갖게 됨.

(왼쪽 편향 이진 트리 / 오른쪽 편향 이진 트리)

 

• 이진 트리 - 순회

순회 : 트리의 노드들을 체게적으로 방문하는 것

전위 순회 / 중위 순회 / 후위 순회

 

• 이진 탐색 트리 (BST)

탐색 작업을 효율적으로 하기 위한 자료구조

모든 원소는 서로 다른 유일한 키를 갖는다.

왼쪽 서브 트리의 키 < 루트 노드 < 오른쪽 서브 트리의 키

왼쪽, 오른쪽 서브트리도 이진 탐색 트리다.

중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

 

• 이진 탐색 트리 - 성능

트리의 높이만큼 시간이 걸린다.

 

• 이진 탐색 트리 코드

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

def insert(root, key):
    # 처음 삽입 시
    if root is None:
        return TreeNode(key)
    else:
        # 작다면 왼쪽부터 삽입 시도
        if key < root.value:
            root.left = insert(root.left, key)
        else:
            root.right = insert(root.right, key)
    return root

def search(root, key):
    # root 를 찾는다면
    if root is None or root.value == key:
        return root

    # key 값이 더 크다면 왼쪽부터 탐색
    if root.value > key:
        return search(root.left, key)

    # 크다면 오른쪽 탐색
    return search(root.right, key)

def inorder_traversal(root):
    if root:
        print(root.value, end=" ")
        inorder_traversal(root.left)
        inorder_traversal(root.right)

def find_min_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete_node(root, key):
    if root is None:
        return root

    if key < root.value:
        root.left = delete_node(root.left, key)
    elif key > root.value:
        root.right = delete_node(root.right, key)
    else:
        # 삭제하려는 노드가 리프 노드이거나 하나의 자식만 가지는 경우
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # 삭제하려는 노드가 두 개의 자식을 가지는 경우
        # 1. 왼쪽 서브 트리의 가장 큰 값
        # 2. 오른쪽 서브 트리의 가장 작은 값
        # 두 가지가 가능한 후보
        temp = find_min_node(root.right)
        root.value = temp.value
        root.right = delete_node(root.right, temp.value)

    return root

# 이진 탐색 트리 생성 및 사용 예제
arr = [8, 3, 10, 2, 5, 14, 11, 16]
root = insert(None, arr[0])
for el in arr[1:]:
    insert(root, el)
    # 중간 디버깅용 출력코드
    # inorder_traversal(root)
    # print()

# 특정 값 검색 예제
key_to_search = 10
result = search(root, key_to_search)
if result:
    print(f"{key_to_search}를 찾았습니다.")
else:
    print(f"{key_to_search}를 찾을 수 없습니다.")

# 노드 삭제 예제
key_to_delete = 5
inorder_traversal(root)
print()
root = delete_node(root, key_to_delete)
inorder_traversal(root)

test = 1

 

• 힙 (heap)

완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료 구조

 

• 최대 힙 (max heap)

키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리

부모 노드의 키 값 > 자식 노드의 키 값

루트 노드 : 키 값이 가장 큰 노드

 

• 최소 힙 (min heap)

키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리

부모 노드의 키 값 < 자식 노드의 키 값

루트 노드 : 키 값이 가장 작은 노드

 

• 힙 코드

# heapq 라이브러리를 활용하자!
from heapq import heappush, heappop

arr = [20, 15, 19, 4, 13, 11]

# 최소힙
min_heap = []

for el in arr:
    heappush(min_heap, el)

print(min_heap)  # [4, 13, 11, 20, 15, 19] 출력

while len(min_heap) > 0:
    print(heappop(min_heap), end=' ')
print()

# 최대힙
max_heap = []
for el in arr:
    heappush(max_heap, -el)

print(max_heap)  # [-20, -15, -19, -4, -13, -11] 출력

while len(max_heap) > 0:
    print(-heappop(max_heap), end=' ')