오늘 배울 내용(1) 최단경로(shortest path) 문제, (2) 최소 스패닝트리(minimum spanning tree)
오늘 배울 내용 : Prim 알고리즘(욕심쟁이 알고리즘, )Kruskal 알고리즘(욕심쟁이 알고리즘), 상호 배타적 집합의 처리
(1) 위상정렬(2) 에지에 가중치가 있는(weighted) DAG에서 최장경로(longest path) 문제
깊이 우선 탐색 (Depth First Search)과 너비 우선 탐색 (Breadth First Search)
개요, 동전 교환 문제, 평균적인 대기 시간을 최소로 하는 작업 스케쥴링, 회의실 배정, 문제배낭 문제
Dynamic Programming (동적 계획법 - 4) > 8. 연속하는 수들의 최대 합 구하기 > 9. 그리드(Grid)에서 경로 찾기 > 10. LCS(Longest common subsequence) 문제 8. 연속하는 수들의 최대 합 구하기
Weighted Interval SchedulingWe are given a set of intervals(구간) : "I" = {(si, fi) | i = 1, ..., n} (si = 시작시간, fi = 끝나는 시간)Our goal is to find a subse
Dynamic Programming (동적 계획법 - 2) >4. 양의 정수 n의 합 표현 방법 >5. 거스름 돈 나누어 주는 방법 >6. Weighted Interval Scheduling
두 원소의 키 비교에 의한 정렬 방법이 아닌 정렬 알고리즘으로 기수정렬과 계수정렬이 있다.