본문 바로가기
반응형
[알고리즘] Week 5: Voronoi Diagram과 Delaunay Triangulation Day 1: Voronoi Diagram강의 내용:Voronoi Diagram의 개념Voronoi Diagram이란 무엇인가?Voronoi Diagram의 특성과 응용 사례Voronoi Diagram의 기본 원리셀 (Cells) 및 경계 (Boundaries)보로노이 셀의 생성 방법시간 복잡도 분석Voronoi Diagram의 복잡도 및 효율성실습:파이썬을 사용한 간단한 Voronoi Diagram 생성 및 시각화 예제import matplotlib.pyplot as pltimport numpy as npfrom scipy.spatial import Voronoi, voronoi_plot_2d# 예제: Voronoi Diagram 생성 및 시각화points = np.random.rand(10, 2) #.. 2024. 6. 2.
[알고리즘] Week 4: 마르코프 체인과 랜덤화 알고리즘 Day 1: 마르코프 체인 (Markov Chain)강의 내용:마르코프 체인의 개념마르코프 체인이란 무엇인가?마르코프 체인의 특성 및 응용 사례마르코프 체인의 기본 원리상태 공간 (State Space)전이 행렬 (Transition Matrix)마르코프 체인의 시간 복잡도 분석마르코프 체인의 복잡도 및 효율성실습:파이썬을 사용한 간단한 마르코프 체인 구현 및 예제import numpy as np# 예제: 마르코프 체인 구현def markov_chain(trans_matrix, state, steps): current_state = state states = [current_state] for _ in range(steps): current_state = np.random.c.. 2024. 6. 2.
[알고리즘] Week 3: 기하학적 동적 프로그래밍과 문자열 관련 동적 프로그래밍 Day 1: 기하학적 동적 프로그래밍 소개강의 내용:기하학적 동적 프로그래밍의 개념기하학적 문제를 해결하기 위한 동적 프로그래밍의 응용기하학적 문제의 특성 및 응용 사례기하학적 동적 프로그래밍의 기본 원리문제 분할 및 점진적 접근시간 복잡도 분석기하학적 동적 프로그래밍의 복잡도 및 효율성실습:파이썬을 사용한 간단한 기하학적 동적 프로그래밍 예제# 예제: 다각형의 최소 삼각분할 (Minimum Triangulation of Polygon)def min_triangulation(points): n = len(points) dp = [[0] * n for _ in range(n)] def cost(i, j, k): return abs(points[i][0] * points[j][1.. 2024. 6. 2.
[알고리즘] Week 2: 이분 그래프 매칭과 최대 가중치 매칭 Day 1: 이분 그래프 매칭 (Bipartite Graph Matching)강의 내용:이분 그래프의 개념이분 그래프란 무엇인가?이분 그래프의 특성 및 응용 사례이분 그래프 매칭의 개념매칭이란 무엇인가?최대 매칭 (Maximum Matching) 개념헝가리안 알고리즘 (Hungarian Algorithm)알고리즘의 원리알고리즘의 단계별 설명시간 복잡도 분석헝가리안 알고리즘의 복잡도 및 효율성실습:파이썬을 사용한 헝가리안 알고리즘 구현 및 예제# 이분 그래프 매칭 예제: 헝가리안 알고리즘def bpm(bpGraph, u, matchR, seen): for v in range(len(bpGraph[0])): if bpGraph[u][v] and not seen[v]: s.. 2024. 6. 2.
[알고리즘] Week 1: 최소 컷 문제와 강한 연결 요소 분해 Day 1: 최소 컷 문제 (Minimum Cut Problem)강의 내용:최소 컷 문제의 개념최소 컷 문제란 무엇인가?네트워크에서 최소 컷의 중요성 및 응용 사례최소 컷 문제의 정의최대 유량 - 최소 컷 정리 (Max-Flow Min-Cut Theorem)컷의 개념과 용량최소 컷 알고리즘에드몬드-카프 알고리즘 (Edmonds-Karp Algorithm)푸드-풀커슨 알고리즘 (Ford-Fulkerson Algorithm)실습:파이썬을 사용한 간단한 최소 컷 문제 구현 및 예제# 파이썬을 사용한 최소 컷 문제 예제: 에드몬드-카프 알고리즘from collections import dequedef bfs(graph, source, sink, parent): visited = [False] * len(g.. 2024. 6. 2.
[알고리즘] 추가 자료 및 연습 문제 추가 자료1. 선형 계획법 (Linear Programming)도서:"Introduction to Linear Optimization" by Dimitris Bertsimas and John N. Tsitsiklis"Linear Programming and Network Flows" by Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali온라인 강의:MIT OpenCourseWare - Linear ProgrammingCoursera - Linear Optimization2. 제약 만족 문제 (Constraint Satisfaction Problem, CSP)도서:"Constraint Processing" by Rina Dechter"Artificial .. 2024. 6. 2.
[알고리즘] Week 12: 종합 실습 및 프로젝트 Day 1: 종합 실습 준비강의 내용:종합 실습의 목적과 목표전체 과정에서 배운 알고리즘과 기법을 통합하여 실제 문제 해결프로젝트 개요프로젝트 주제 소개 및 요구사항 분석팀 구성 및 역할 분담프로젝트 계획 수립단계별 목표 설정 및 일정 관리실습:프로젝트 주제 및 요구사항 확정팀 구성 및 역할 분담### 프로젝트 주제 예시1. 대규모 데이터 분석 도구 개발2. 실시간 경로 최적화 시스템3. 종합 퍼즐 해결 시스템### 프로젝트 요구사항 예시1. 데이터 입력 모듈2. 알고리즘 구현 모듈3. 결과 출력 및 성능 분석 모듈### 프로젝트 계획 수립 예시1. 데이터 입력 모듈 설계 및 구현 (1일)2. 알고리즘 구현 모듈 설계 및 구현 (3일)3. 결과 출력 및 성능 분석 모듈 설계 및 구현 (1일)4. 통합 테.. 2024. 6. 2.
[알고리즘] Week 11: 최적화 알고리즘 - 선형 계획법과 제약 만족 문제 Day 1: 선형 계획법 (Linear Programming)강의 내용:선형 계획법의 개념선형 계획법이란 무엇인가?선형 계획법의 응용 사례 (예: 자원 배분, 생산 계획)선형 계획법의 기본 요소목적 함수 (Objective Function)제약 조건 (Constraints)변수 (Variables)선형 계획법의 표준 형태표준 형태로의 변환시간 복잡도 분석선형 계획법의 복잡도 및 효율성실습:파이썬을 사용한 간단한 선형 계획법 예제from scipy.optimize import linprog# 선형 계획법 예제: 최대화 문제# 목적 함수: maximize 3x + 4y# 제약 조건: 2x + y = -10, -x + 2y >= -2, -x + 5y = 15c = [-3, -4]A = [[2, 1], [-4,.. 2024. 6. 2.
[알고리즘] 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.
반응형

티스토리툴바