[알고리즘] Week 2: 고급 탐색 알고리즘 - 이진 탐색 트리 성능 최적화 및 트라이

Day 1: 이진 탐색 트리 (BST)의 성능 최적화

강의 내용:
- BST의 성능 문제
  - 균형 잡힌 트리 vs. 불균형 트리
  - 최악의 경우 시간 복잡도: O(n)
- BST 성능 최적화 개념
  - 균형 잡힌 트리의 필요성
  - 자가 균형 이진 탐색 트리 개념 소개
- AVL 트리와 레드-블랙 트리
  - AVL 트리 개요
  - 레드-블랙 트리 개요
실습:
- 불균형 BST와 균형 잡힌 트리의 성능 비교

# 불균형 BST 예제
class BSTNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return BSTNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)

# 불균형 BST 생성
root = None
keys = [10, 20, 30, 40, 50, 60, 70]
for key in keys:
    root = insert(root, key)

# 예제 실행
print("불균형 BST의 중위 순회 결과:")
inorder(root)  # 10 20 30 40 50 60 70

Day 2: AVL 트리

강의 내용:
- AVL 트리의 개념
  - AVL 트리란 무엇인가?
  - AVL 트리의 균형 조건
- AVL 트리의 삽입 및 삭제
  - AVL 트리에서 삽입과 삭제 시 균형 유지 방법
  - 회전 연산 (좌회전, 우회전, 좌우회전, 우좌회전)
- AVL 트리의 시간 복잡도
  - 시간 복잡도: O(log n)
실습:
- 파이썬을 사용한 AVL 트리 구현 및 예제

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def insert(root, key):
    if not root:
        return AVLNode(key)
    elif key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)

    root.height = 1 + max(get_height(root.left), get_height(root.right))

    balance = get_balance(root)
    if balance > 1 and key < root.left.key:
        return right_rotate(root)
    if balance < -1 and key > root.right.key:
        return left_rotate(root)
    if balance > 1 and key > root.left.key:
        root.left = left_rotate(root.left)
        return right_rotate(root)
    if balance < -1 and key < root.right.key:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

def left_rotate(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def get_height(root):
    if not root:
        return 0
    return root.height

def get_balance(root):
    if not root:
        return 0
    return get_height(root.left) - get_height(root.right)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=' ')
        inorder(root.right)

# 예제 실행
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
    root = insert(root, key)

print("AVL 트리의 중위 순회 결과:")
inorder(root)  # 10 20 25 30 40 50

Day 3: 레드-블랙 트리

강의 내용:
- 레드-블랙 트리의 개념
  - 레드-블랙 트리란 무엇인가?
  - 레드-블랙 트리의 균형 조건
- 레드-블랙 트리의 삽입 및 삭제
  - 레드-블랙 트리에서 삽입과 삭제 시 균형 유지 방법
  - 색상 변경 및 회전 연산
- 레드-블랙 트리의 시간 복잡도
  - 시간 복잡도: O(log n)
실습:
- 파이썬을 사용한 레드-블랙 트리 구현 및 예제

class RBTreeNode:
    def __init__(self, key, color='RED'):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.TNULL = RBTreeNode(0, 'BLACK')
        self.root = self.TNULL

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.TNULL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.TNULL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def insert_fix(self, k):
        while k.parent.color == 'RED':
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == 'RED':
                    u.color = 'BLACK'
                    k.parent.color = 'BLACK'
                    k.parent.parent.color = 'RED'
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = 'BLACK'
                    k.parent.parent.color = 'RED'
                    self.left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right
                if u.color == 'RED':
                    u.color = 'BLACK'
                    k.parent.color = 'BLACK'
                    k.parent.parent.color = 'RED'
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = 'BLACK'
                    k.parent.parent.color = 'RED'
                    self.right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = 'BLACK'

    def insert(self, key):
        node = RBTreeNode(key)
        node.parent = None
        node.left = self.TNULL
        node.right = self.TNULL
        node.color = 'RED'
        y = None
        x = self.root
        while x != self.TNULL:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right
        node.parent = y
        if y is None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node
        if node.parent is None:
            node.color = 'BLACK'
            return
        if node.parent.parent is None:
            return
        self.insert_fix(node)

    def inorder_helper(self, node):
        if node != self.TNULL:
            self.inorder_helper(node.left)
            print(node.key, end=' ')
            self.inorder_helper(node.right)

# 예제 실행
rbt = RedBlackTree()
keys = [7, 3, 18, 10, 22, 8, 11, 26]
for key in keys:
    rbt.insert(key)
print("레드-블랙 트리의 중위 순회 결과:")
rbt.inorder_helper(rbt.root)  # 3 7 8 10 11 18 22 26

Day 4: 트라이 (Trie)

강의 내용:
- 트라이의 개념
  - 트라이란 무엇인가?
  - 트라이의 구조 및 사용 사례
- 트라이의 시간 복잡도
  - 삽입, 삭제, 검색: O(m) (m은 문자열의 길이)
- 트라이의 장단점
  - 장점: 빠른 검색 속도, 문자열 데이터 처리에 적합
  - 단점: 높은 메모리 사용량
실습:
- 파이썬을 사용한 트라이 구현 및 예제

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# 예제 실행
trie = Trie()
trie.insert("apple")
print("apple 검색 결과:", trie.search("apple"))  # True
print("app 검색 결과:", trie.search("app"))  # False
print("app 접두사 검색 결과:", trie.starts_with("app"))  # True
trie.insert("app")
print("app 검색 결과:", trie.search("app"))  # True

Day 5: 트라이의 응용

강의 내용:
- 트라이의 실제 응용 사례
  - 자동 완성 시스템
  - 사전 구현
  - 문자열 패턴 매칭
- 트라이의 성능 최적화
  - 메모리 사용량 최적화 기법
실습:
- 자동 완성 시스템 구현

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def _find_words_with_prefix(self, node, prefix):
        words = []
        if node.end_of_word:
            words.append(prefix)
        for char, next_node in node.children.items():
            words.extend(self._find_words_with_prefix(next_node, prefix + char))
        return words

    def autocomplete(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return self._find_words_with_prefix(node, prefix)

# 예제 실행
trie = Trie()
words = ["apple", "app", "apricot", "banana", "bat", "ball"]
for word in words:
    trie.insert(word)
print("자동 완성 결과:", trie.autocomplete("ap"))  # ['apple', 'app', 'apricot']
print("자동 완성 결과:", trie.autocomplete("ba"))  # ['banana', 'bat', 'ball']

Day 6: 고급 탐색 알고리즘의 비교 및 응용

강의 내용:
- 이진 탐색 트리 vs. 트라이
  - 각 자료구조의 장단점 비교
  - 사용 사례 비교
- 고급 탐색 알고리즘의 응용 사례
  - 데이터 검색 및 탐색
  - 텍스트 처리 및 검색 시스템
실습:
- 다양한 데이터 셋을 사용한 고급 탐색 알고리즘의 성능 비교

# 성능 비교 예제
import time

def measure_time(func, *args):
    start_time = time.time()
    func(*args)
    end_time = time.time()
    return end_time - start_time

# 데이터 생성
words = ["apple", "app", "apricot", "banana", "bat", "ball"]
trie = Trie()
for word in words:
    trie.insert(word)

# 검색 성능 측정
trie_search_time = measure_time(trie.search, "banana")
print("트라이 검색 시간:", trie_search_time)

Day 7: 종합 연습 및 프로젝트 준비

강의 내용:
- 종합 연습
  - 이진 탐색 트리 성능 최적화 및 트라이를 활용한 종합 문제 풀이
- 프로젝트 준비
  - 프로젝트 주제 선정 및 요구사항 분석
  - 프로젝트 계획 수립
실습:
- 종합 문제 해결 및 프로젝트 준비

### 종합 연습 문제 예시
1. 대규모 데이터셋을 이진 탐색 트리와 트라이를 사용하여 검색하고 성능을 비교하세요.
2. 텍스트 자동 완성 시스템을 구현하고 성능을 최적화하세요.

### 프로젝트 주제 예시
1. 대규모 텍스트 데이터 처리 도구 개발
2. 실시간 검색 및 자동 완성 시스템

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 고급 탐색 알고리즘 구현 (이진 탐색 트리, 트라이 등)
3. 데이터 출력 및 성능 분석 모듈 구현

이 강의는 파이썬의 고급 탐색 알고리즘, 특히 이진 탐색 트리의 성능 최적화와 트라이의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!

저작자표시 비영리 변경금지

'-----ETC2----- > 알고리즘(심화)' 카테고리의 다른 글

[알고리즘] Week 6: 고급 그래프 알고리즘 - 강한 연결 요소와 위상 정렬 (0)	2024.06.02
[알고리즘] Week 5: 네트워크 플로우 알고리즘 - 개념과 최대 유량 문제 (1)	2024.06.02
[알고리즘] Week 4: 고급 그리디 알고리즘 - 심화와 예제 (0)	2024.06.02
[알고리즘] Week 3: 고급 동적 프로그래밍 기법과 예제 (0)	2024.06.02
[알고리즘] Week 1: 고급 정렬 알고리즘 - 계수 정렬, 기수 정렬, 버킷 정렬 (1)	2024.06.02

Python 개발자

[알고리즘] Week 2: 고급 탐색 알고리즘 - 이진 탐색 트리 성능 최적화 및 트라이

'-----ETC2----- > 알고리즘(심화)' 카테고리의 다른 글

티스토리툴바

[알고리즘] Week 2: 고급 탐색 알고리즘 - 이진 탐색 트리 성능 최적화 및 트라이

'-----ETC2----- > 알고리즘(심화)' 카테고리의 다른 글

관련글

티스토리툴바