본문 바로가기
반응형
[알고리즘] Week 10: 고급 그래프 이론 - 트리 분해, 트리 DP, 라벨링 기법 Day 1: 트리 분해 (Tree Decomposition)강의 내용:트리 분해의 개념트리 분해란 무엇인가?트리 분해의 목적 및 응용 사례트리 분해의 기본 용어트리 너비 (Treewidth)트리 분해의 정의트리 분해 알고리즘나이스 트리 분해 (Nice Tree Decomposition)시간 복잡도 분석트리 분해의 복잡도 및 효율성실습:간단한 예제 그래프에서 트리 분해 수행# 트리 분해 예제import networkx as nxdef tree_decomposition_example(): G = nx.Graph() G.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]) T = nx.Graph() T.add_edges_fro.. 2024. 6. 2.
[알고리즘] Week 9: 고급 기하 알고리즘 - 개요와 예제 Day 1: 고급 기하 알고리즘 개요강의 내용:기하 알고리즘의 정의 및 중요성기하 알고리즘이란 무엇인가?기하 알고리즘의 응용 분야 (컴퓨터 그래픽스, 로봇 공학, GIS 등)기하 알고리즘의 기본 개념점, 선분, 다각형 등의 기본 요소벡터와 교차 곱 (Cross Product), 내적 (Dot Product)실습:기본 기하 연산 예제 (점, 선분, 벡터 등)import math# 두 점 사이의 거리 계산def distance(p1, p2): return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)# 벡터의 내적 계산def dot_product(v1, v2): return v1[0] * v2[0] + v1[1] * v2[1]# 벡터의 교차 곱 계산de.. 2024. 6. 2.
[알고리즘] Week 8: 고급 문자열 알고리즘 - 문자열 검색 알고리즘 Day 1: 고급 문자열 알고리즘 소개강의 내용:문자열 알고리즘의 중요성문자열 알고리즘의 다양한 응용 사례문자열 검색의 필요성문자열 검색 알고리즘의 개요패턴 매칭 문제 정의다양한 문자열 검색 알고리즘 소개실습:간단한 문자열 검색 예제# 간단한 문자열 검색 예제def naive_search(pattern, text): M = len(pattern) N = len(text) for i in range(N - M + 1): j = 0 while j  Day 2: KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)강의 내용:KMP 알고리즘의 개념KMP 알고리즘이란 무엇인가?KMP 알고리즘의 동작 원리KMP 알고리즘의 시간 복잡도시간 복잡도: O(N +.. 2024. 6. 2.
[알고리즘] Week 7: 고급 그래프 최단 경로 알고리즘 - 벨만-포드 알고리즘과 존슨 알고리즘 Day 1: 벨만-포드 알고리즘 (Bellman-Ford Algorithm)강의 내용:벨만-포드 알고리즘의 개념벨만-포드 알고리즘이란 무엇인가?다익스트라 알고리즘과의 차이점음의 가중치 허용벨만-포드 알고리즘의 동작 원리각 단계에서 간선의 완화 (Relaxation) 수행음의 사이클 존재 여부 검출벨만-포드 알고리즘의 시간 복잡도시간 복잡도: O(VE)실습:파이썬을 사용한 벨만-포드 알고리즘 구현 및 예제# 벨만-포드 알고리즘 구현class Graph: def __init__(self, vertices): self.V = vertices self.graph = [] def add_edge(self, u, v, w): self.graph.append([u, v.. 2024. 6. 2.
[알고리즘] Week 6: 고급 그래프 알고리즘 - 강한 연결 요소와 위상 정렬 Day 1: 강한 연결 요소 (Strongly Connected Components, SCC)강의 내용:강한 연결 요소의 개념강한 연결 요소란 무엇인가?그래프의 SCC를 찾는 중요성 및 응용 사례강한 연결 요소 탐색 알고리즘코사라주 알고리즘 (Kosaraju's Algorithm)타잔 알고리즘 (Tarjan's Algorithm)실습:간단한 예제 그래프에서 SCC 찾기# 코사라주 알고리즘을 사용한 SCC 찾기from collections import defaultdictclass Graph: def __init__(self, vertices): self.graph = defaultdict(list) self.V = vertices def add_edge(self, u,.. 2024. 6. 2.
[알고리즘] Week 5: 네트워크 플로우 알고리즘 - 개념과 최대 유량 문제 Day 1: 네트워크 플로우의 개념강의 내용:네트워크 플로우의 정의네트워크 플로우란 무엇인가?유량 네트워크와 그 구성 요소 (소스, 싱크, 용량 등)네트워크 플로우의 기본 용어유량, 잔여 용량, 경로, 컷네트워크 플로우의 응용 사례물류 및 교통 네트워크데이터 네트워크작업 할당 문제실습:간단한 네트워크 플로우 예제 그래프 그리기# 간단한 네트워크 플로우 예제class Graph: def __init__(self, vertices): self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)] self.V = vertices def add_edge(self, u, v, w): self.graph[u.. 2024. 6. 2.
[알고리즘] Week 4: 고급 그리디 알고리즘 - 심화와 예제 Day 1: 그리디 알고리즘 심화강의 내용:그리디 알고리즘 복습그리디 알고리즘의 기본 원리그리디 알고리즘의 장단점 및 사용 사례고급 그리디 알고리즘그리디 알고리즘 심화 개념그리디 알고리즘을 사용해야 하는 경우와 사용하지 않아야 하는 경우그리디 알고리즘의 시간 복잡도 분석그리디 알고리즘의 시간 복잡도 계산 방법실습:간단한 그리디 알고리즘 문제 복습# 간단한 그리디 알고리즘 예제: 동전 교환 문제def coin_change_greedy(coins, amount): coins.sort(reverse=True) result = [] for coin in coins: while amount >= coin: amount -= coin result... 2024. 6. 2.
[알고리즘] 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.
반응형

티스토리툴바