본문 바로가기
반응형
[알고리즘] 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.
[알고리즘] 추가 학습 자료 및 연습 문제 추가 학습 자료온라인 강의 및 코스Coursera: "Algorithms, Part I & II" by Princeton UniversityPart IPart IIedX: "Algorithm Design and Analysis" by MITCourse LinkUdacity: "Data Structures and Algorithms" Nanodegree ProgramCourse Link추천 서적"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein"Algorithm Design Manual" by Steven S. Skiena"Data Structures and Alg.. 2024. 6. 2.
[알고리즘] Week 12: 종합 실습 및 프로젝트 Day 1: 종합 실습 - 탐색 알고리즘강의 내용:이진 탐색 트리 (Binary Search Tree)삽입, 삭제, 탐색 연습깊이 우선 탐색 (DFS)와 너비 우선 탐색 (BFS)그래프 탐색 알고리즘 복습 및 연습실습:이진 탐색 트리 및 그래프 탐색 알고리즘 구현 및 문제 풀이# 이진 탐색 트리의 삽입, 삭제, 탐색 연습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: if root.val  Day 2:.. 2024. 6. 2.
반응형

티스토리툴바