반응형 [알고리즘] Week 3: 고급 동적 프로그래밍 기법과 예제 Day 1: 고급 동적 프로그래밍 기법 소개강의 내용:동적 프로그래밍 복습동적 프로그래밍의 기본 개념과 원리메모이제이션과 테이블화 방법 (Top-down vs Bottom-up)고급 동적 프로그래밍 기법상태 압축 (State Compression)비트마스크 (Bitmasking)공간 복잡도 최적화 기법실습:간단한 동적 프로그래밍 문제 복습# 기본 동적 프로그래밍 예제: 피보나치 수열def fibonacci(n, memo={}): if n in memo: return memo[n] if n Day 2: 상태 압축 (State Compression)강의 내용:상태 압축의 개념상태 압축이란 무엇인가?상태 압축을 통해 공간 복잡도를 줄이는 방법상태 압축을 활용한 예제예제: 최소 비용 경.. 2024. 6. 2. [알고리즘] 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 = keydef insert(root, key): if root is None: return BSTNode(key) else: .. 2024. 6. 2. [알고리즘] Week 1: 고급 정렬 알고리즘 - 계수 정렬, 기수 정렬, 버킷 정렬 Day 1: 계수 정렬 (Counting Sort)강의 내용:계수 정렬의 개념계수 정렬이란 무엇인가?계수 정렬의 작동 원리계수 정렬의 시간 복잡도시간 복잡도: O(n + k) (n은 배열의 길이, k는 배열의 최대값)공간 복잡도: O(k)계수 정렬의 장단점장점: 매우 빠름, 안정적단점: 메모리 사용량이 큼, 숫자 범위가 제한적일 때 적합실습:파이썬을 사용한 계수 정렬 구현 및 예제def counting_sort(arr): max_val = max(arr) count = [0] * (max_val + 1) for num in arr: count[num] += 1 sorted_arr = [] for i, cnt in enumerate(count): .. 2024. 6. 2. 이전 1 2 다음 반응형
