회원가입시 10%할인권 증정!
NO.1 대학교육의 멘토 유니와이즈 캠퍼스
홈 > 강의목록
알고리즘 통합과정
신흥철 교수님 KAIST 대학원 전산학부 박사졸업
| 강의 신청하기 | 총 합계금액 : 390,000원 |
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 1장. 기초 | ||
|
[1강] 알고리즘의 역할
|
0 :
10 :
02
|
|
알고리즘, 기술로서의 알고리즘 | ||
|
[2강] 삽입 정렬. 알고리즘의 분석
|
0 :
51 :
35
|
|
루프 불변성(수학적 귀납법)-타당성 증명, 삽입정렬의 루프 불편성, 알고리즘의 분석, 분석 대상, 구현 기술 모델, 삽입 정렬의 분석, 삽입 정렬 알고리즘의 수행시간(증가 비율/차수) | ||
|
[3강] 알고리즘의 설계 (1)
|
0 :
33 :
49
|
|
분할정복 방법(삽입 정렬: 점진적 방법), 재귀 호출 구조, 병합정렬 | ||
|
[4강] 알고리즘의 설계 (2)
|
0 :
40 :
13
|
|
분할정복 알고리즘의 분석, 병합정렬의 분석 | ||
|
[5강] 점근적 표기
|
0 :
40 :
48
|
|
점근적 표기, 등식에서의 점근적 표기, 함수들의 비교, 삼분법 | ||
|
[6강] 표준 표기법과 함수
|
0 :
47 :
47
|
|
단조성, 내림과 올림, 나머지(모듈로) 연산, 다항식, 지수함수, 로그, 계승, 함수의 반복, 피보나치 수, 면적형, 나선형, 자연 나선형, 황금율, 재귀 알고리즘, 동적 계획법, 반복 알고리즘, 분할정복 알고리즘 | ||
|
[7강] 최대 부분 배열 문제
|
0 :
45 :
18
|
|
분할정복 방법, 분할정복 알고리즘 분석 | ||
|
[8강] 스트라센 알고리즘
|
0 :
25 :
32
|
|
단순 행렬 곱셈, 단순 분할정복 방법, 스트라센의 방법 | ||
|
[9강] 점화식을 풀기 위한 치환법
|
0 :
28 :
23
|
|
치환법 사례, 치환법의 잘못된 사례 | ||
|
[10강] 점화식을 풀기위한 재귀 트리 방법
|
0 :
32 :
30
|
|
재귀 트리 방법 | ||
|
[11강] 점화식을 풀기위한 마스터 방법
|
1 :
01 :
31
|
|
마스터 방법, 마스터 방법 사용하기, 다항식에서 정규조건, 마스터 방법이 적용되지 않는 경우 | ||
|
[12강] 고용 문제. 지표 확률 변수
|
0 :
43 :
30
|
|
면접비용과 고용비용 분석, 고용 문제 비용, 확률적 분석, 랜덤화된 알고리즘, 지표 확률 변수, 지표 확률 변수를 이용한 고용 문제 비용 분석 | ||
|
[13강] 랜덤화된 알고리즘
|
0 :
45 :
50
|
|
확률적 분석, 랜덤화된 알고리즘, 고용 문제의 랜덤화된 알고리즘, 임의의 순서로 배열 뒤바꾸기(랜덤화) | ||
| 2장. 정렬과 순서 통계량 | ||
|
[14강] 힙. 힙 특성 유지하기
|
0 :
50 :
35
|
|
힙, 최대 힙 유지하기 | ||
|
[15강] 힙 만들기
|
0 :
45 :
30
|
|
최대 힙 만들기, BuildMaxheap의 루프 불변성, BuildMaxheap(최대 힙 만드는) 수행시간 | ||
|
[16강] 힙 정렬 알고리즘. 우선 순위 큐
|
0 :
29 :
04
|
|
힙 정렬 알고리즘, 우선 순위 큐 | ||
|
[17강] 퀵 정렬 (1)
|
0 :
52 :
48
|
|
분할정복에 의한 퀵정렬, 배열 분할, 배열 분할의 루프 불변성 | ||
|
[18강] 퀵 정렬 (2)
|
0 :
47 :
38
|
|
최악의 분할, 최선의 분할(균등 분할), 불균등 분할, 퀵정렬의 성능, 랜덤화된 퀵정렬, 퀵정렬 분석, 평균 수행시간 | ||
|
[19강] 정렬의 하한. 계수 정렬
|
0 :
59 :
18
|
|
결정 트리 모델, 안정성 | ||
|
[20강] 기수 정렬. 버킷 정렬
|
0 :
50 :
56
|
|
정확성 | ||
|
[21강] 중앙값과 순서 통계량 (1)
|
1 :
01 :
32
|
|
최솟값과 최댓값, 최솟값과 최댓값을 동시에 구하기, 선형 평균 수행시간에 선택 | ||
|
[22강] 중앙값과 순서 통계량 (2)
|
0 :
50 :
44
|
|
선형 시간에 선택하기 | ||
| 3장. 자료구조 | ||
|
[23강] 기본 자료구조 (1)
|
0 :
53 :
43
|
|
자료구조, 동적 집합의 원소, 사전, 스택과 큐, 연결 리스트, 경계원소, 경계원소를 이용한 연결 리스트에서의 검색 | ||
|
[24강] 기본 자료구조 (2)
|
0 :
31 :
05
|
|
포인터와 객체 구현하기, 배열과 인덱스를 이용한 객체와 포인터 구현, 객체의 다중 배열 표현, 객체의 할당과 해제, 두 개의 연결 리스트, 루트 있는 트리 표현하기, 이진 트리, 제한 없는 가지를 가지는 루트 있는 트리 | ||
|
[25강] 직접 주소 테이블. 해시 테이블
|
0 :
54 :
56
|
|
직접 주소 테이블의 기본 사전적 연산, 해싱 방법 vs 직접 주소화 방법, 해시 함수(결정론적 함수), 충돌, 해시 테이블 & 해시 함수 & 충돌, 체이닝에 의한 충돌 해결, 체이닝을 사용하는 해싱의 분석 | ||
|
[26강] 해시 함수
|
0 :
20 :
26
|
|
나누기 방법, 곱하기 방법 | ||
|
[27강] 개방 주소화 방법 (1)
|
0 :
36 :
36
|
|
개방 주소화 방법에서의 삽입, 개방 주소화 방법에서의 검색, 선형 조사, 2차원 조사, 중복 해싱 | ||
|
[28강] 개방 주소화 방법 (2)
|
0 :
46 :
34
|
|
개방 주소 해싱의 분석 | ||
|
[29강] 이진 검색 트리 (1)
|
0 :
45 :
00
|
|
이진 탐색 트리 순회, 이진 검색 트리에 대한 질의, 최소 원소와 최대 원소, 직후 원소와 직전 원소 | ||
|
[30강] 이진 검색 트리 (2)
|
0 :
34 :
36
|
|
삽입과 삭제 | ||
|
[31강] 레드블랙 트리의 특성. 회전
|
0 :
40 :
35
|
|
레드블랙 트리, 레드블랙 트리에서 연산의 수행시간, 회전(포인터 변경), 좌우 회전 | ||
|
[32강] 삽입 (1)
|
0 :
37 :
16
|
|
삽입 조정 | ||
|
[33강] 삽입 (2)
|
0 :
39 :
42
|
|
삽입 조정, 삽입 조정의 타당성 증명, 삽입 조정의 수행시간 분석 | ||
|
[34강] 삭제
|
1 :
08 :
53
|
|
삭제, 이동, 삭제 후 특성 위반 유형, 삭제 후 여분의 흑색 이동, 삭제 조정, 삭제 조정의 수행시간 분석 | ||
|
[35강] 동적 순서 통계량
|
0 :
44 :
08
|
|
순서 통계량 트리, 순서 통계량 트리의 예, 주어진 순위의 원소 찾기, 원소의 순위 구하기, 원소의 순위 구하기에 대한 타당성 증명, 서브트리 크기 유지하기 | ||
|
[36강] 자료구조의 확장 기법. 구간 트리
|
1 :
00 :
39
|
|
자료구조의 확장 단계, 동적 순서 통계량 트리 설계, 구간, 구간 트리, 구간의 집합, 구간의 집합을 구간 트리로 나타내는 방법, 구간 검색 | ||
| 4장. 고급 설계 및 분석 기법 | ||
|
[37강] 동적 프로그래밍. 막대 자르기
|
0 :
57 :
54
|
|
동적 프로그래밍 적용의 중요 요소, 최적화 문제에 대한 동적 프로그래밍 적용 단계, 분할정복 알고리즘, 동적 프로그래밍, 그리디 알고리즘, 막대 자르기 문제, 하향식 재귀의 구현, 하향식 재귀의 구현에 대한 재귀 트리 예, 메모하기를 이용한 하향식 방법, 상향식 동적 프로그래밍 방법, 동적 프로그래밍 방법의 수행시간 분석, 부분 문제 그래프, 해의 재구성 | ||
|
[38강] 행렬-체인 곱셈
|
1 :
06 :
48
|
|
괄호 묶는 방법의 수 세기, 동적 프로그래밍의 적용, 1단계: 최적 괄호 묶기의 구조, 2단계: 재귀해, 3단계: 최적 비용 계산, 4단계: 최적해 구성하기 | ||
|
[39강] 동적 프로그래밍의 요소
|
0 :
48 :
07
|
|
최적 부분 구조, 미묘한 문제들, 중복되는 부분 문제, 메모하기 | ||
|
[40강] 최장 공통 부분 시퀀스
|
0 :
53 :
06
|
|
부분 시퀀스, 최장 공통 부분 시퀀스 | ||
|
[41강] 최적 이진 검색 트리
|
0 :
58 :
42
|
|
최소 기대 검색 비용 트리, 1단계: 최적 이진 검색 트리 구조, 2단계: 재귀해, 3단계: 최적의 기대 검색 비용 계산하기 & 최적 이진 검색 트리 알고리즘 | ||
|
[42강] 활동 선택 문제
|
0 :
51 :
51
|
|
그리디 알고리즘, 활동 선택 문제, 1단계: 최적 부분 구조, 2단계: 재귀해, 3단계: 그리디 선택하기, 4단계: 그리디 선택의 안전함 증명, 5단계: 재귀 그리디 알고리즘, 6단계: 반복 순환 그리디 알고리즘 | ||
|
[43강] 그리디 방법의 요소들
|
0 :
27 :
01
|
|
그리디 방법 단계, 그리디 알고리즘 만들기, 그리디 선택 특성, 최적 부분 구조, 그리디와 동적 프로그래밍의 비교 | ||
|
[44강] 허프만 코드
|
1 :
03 :
36
|
|
문자 코드화, 프리픽스 코드, 허프만 코드 만들기, 허프만 코드 알고리즘의 정확성문자 코드화, 프리픽스 코드, 허프만 코드 만들기, 허프만 코드 알고리즘의 정확성문자 코드화, 프리픽스 코드, 허프만 코드 만들기, 허프만 코드 알고리즘의 정확성 | ||
|
[45강] 분할 상환 분석. 총계 분석
|
0 :
39 :
10
|
|
분할상환 분석, 총계 분석에서 분할상환 비용, 스택연산, 이진 카운터 증가시키기 | ||
|
[46강] 결산 방법. 잠재 비용 방법
|
0 :
42 :
23
|
|
결산 방법, 스택 연산, 이진 카운터 증가시키기, 잠재 비용 방법 | ||
|
[47강] 동적 테이블 (1)
|
0 :
43 :
28
|
|
테이블 확장 | ||
|
[48강] 동적 테이블 (2)
|
0 :
45 :
20
|
|
테이블 확장과 축소 | ||
| 5장. 고급 자료구조 | ||
|
[49강] B-트리의 개념
|
0 :
35 :
06
|
|
보조 기억 장치(디스크)의 자료구조, B-트리의 특징과 높이 | ||
|
[50강] B-트리의 기본연산
|
0 :
52 :
59
|
|
B-트리에 대한 연산의 전제, 빈 B-트리 생성, B-트리의 검색, B-트리에 키 삽입하기, B-트리에서 노드 분할, B-트리에서 루트 분할, 하향 단일 경로를 따라 B-트리에 키 삽입 | ||
|
[51강] B-트리에서 키 삭제하기
|
0 :
42 :
00
|
|
노드 x에서 키 k 삭제하기, 키 k가 내부 노드 x에 있는 경우, 내부 노드에서 키 삭제 | ||
|
[52강] 피보나치 힙의 구조
|
0 :
15 :
41
|
|
병합 가능한 힙(최소 힙)이 지원하는 연산, 피보나치 힙이 지원하는 추가적인 연산, 잠재 비용 함수 | ||
|
[53강] 병합 가능한 힙 연산
|
0 :
59 :
58
|
|
새 피보나치 힙의 생성, 최소 노드 찾기, 노드 삽입하기, 2개의 피보나치 힙 합치기, 최소 노드 추출, 루트 리스트 정리, Consolidate의 타당성 증명, 최소 노드 추출의 비용 분석 | ||
|
[54강] 키 감소시키기와 노드 삭제하기
|
0 :
34 :
01
|
|
키 감소시키기, 키 감소시키기의 비용 분석, 노드 삭제하기 | ||
|
[55강] 최대 차수의 한계 정하기
|
0 :
46 :
01
|
|
피보나치 수 | ||
|
[56강] 동적 집합, 기본 방법
|
0 :
56 :
20
|
|
동적 집합(우선순위 큐) 연산, 동적 집합 저장 방법(키의 저장), 이진 트리 구조의 중첩, 질의 연산, 변경 연산 | ||
|
[57강] 재귀 구조 (1)
|
0 :
59 :
59
|
|
수정된 재귀 구조, 초기 반 엠데 보아스 구조 | ||
|
[58강] 재귀 구조 (2)
|
0 :
58 :
30
|
|
원소의 포함 여부 검색, 최소 원소 검색, 직후 원소 검색, 원소 삽입, 원소 삭제 | ||
|
[59강] 반 엠데 보아스트리 (1)
|
0 :
42 :
57
|
|
전체 집합 크기 제한의 완화, min & max를 이용한 재귀 호출 감소 방법 | ||
|
[60강] 반 엠데 보아스트리 (2)
|
0 :
59 :
28
|
|
최소 원소와 최대 원소 검색, 원소의 포함 여부 검색, 직후 원소 검색, 직전 원소 검색, 원소 삽입, 원소 삭제 | ||
|
[61강] 서로 소 집합의 연결 리스트 표현
|
0 :
45 :
02
|
|
서로 소 집합의 자료구조, 서로 소 집합 자료구조의 응용, 그래프에서 연결 요소 찾기, 같은 연결 요소 여부 확인, 서로 소 집합의 연결 리스트 표현, 합집합의 단순 구현, 가중치 UNION 휴리스틱 | ||
|
[62강] 서로소 집합 포리스트
|
0 :
32 :
23
|
|
수행시간을 향상시키는 휴리스틱, 서로 소 집합 포리스트를 위한 의사코드, 수행시간에 대한 휴리스틱의 영향 | ||
| 6장, 그래프 알고리즘 | ||
|
[63강] 그래프의 표현. 너비 우선 검색 (1)
|
0 :
52 :
22
|
|
그래프의 표현 방법, 너비 우선 검색, 수행시간 분석 | ||
|
[64강] 너비 우선 검색 (2)
|
0 :
30 :
50
|
|
최단 경로 거리 | ||
|
[65강] 너비 우선 검색 (3)
|
0 :
45 :
45
|
|
너비 우선 검색의 정확성, 너비 우선 트리 | ||
|
[66강] 깊이 우선 검색 (1)
|
0 :
35 :
24
|
|
깊이 우선 포리스트, 깊이 우선 검색의 수행시간 | ||
|
[67강] 깊이 우선 검색 (2)
|
0 :
45 :
58
|
|
깊이 우선 검색의 특성, 괄호 정리, 자손 구간들의 중첩, 흰색 경로 정리, 간선들의 분류 | ||
|
[68강] 위상정렬
|
0 :
35 :
37
|
|
비순환 방향 그래의 위상 정렬, 알고리즘의 정확성 증명 | ||
|
[69강] 강한 연결요소
|
0 :
58 :
10
|
|
방향 그래프의 강한 연결 요소 | ||
|
[70강] 최소 신장 트리의 확장
|
0 :
57 :
13
|
|
최소 신장 트리 확장의 타당성 증명, 그래프의 절단, 절단의 예 | ||
|
[71강] 크루스칼 알고리즘과 프림 알고리즘. 안전성 정리
|
0 :
56 :
36
|
|
크루스칼 알고리즘, 프림 알고리즘, 프림 알고리즘의 루프 불변성, 프림 알고리즘의 수행시간, | ||
|
[72강] 단일 출발지 최단 경로
|
0 :
38 :
39
|
|
최단 경로 문제, 최단 경로의 최적 부분 구조, 가중치 간선과 순환, 직전원소 부분 그래프, 최단 경로 트리 특성, 완화, 최단 경로 완화의 특성 | ||
|
[73강] 벨만-포드 알고리즘
|
0 :
44 :
47
|
|
단일 출발점 최단 경로, 벨만-포드 알고리즘의 정확성 | ||
|
[74강] DAG 단일 출발점 최단 경로
|
0 :
29 :
12
|
|
가중치가 있는 dag G=(V, E)의 최단 경로 | ||
|
[75강] 다익스트라 알고리즘
|
0 :
34 :
32
|
|
그리디 알고리즘, 다익스트라 알고리즘의 정확성, 수행시간 분석(피보나치 힙 사용) | ||
|
[76강] 차이 제약 조건과 최단 경로
|
0 :
41 :
46
|
|
선형 계획법, 차이 제약조건 시스템, 제약조건 그래프, 차이 제약조건 시스템 풀기 | ||
|
[77강] 최단 경로 특성의 증명 (1)
|
0 :
32 :
01
|
|
삼각 부등식, 상한 특성, 무경로 특성, 수렴 특성 | ||
|
[78강] 최단 경로 특성의 증명 (2)
|
0 :
42 :
09
|
|
경로 완화 특성, 비순환&유일한 경로 증명, 직전원소 부분 그래프 특성 | ||
|
[79강] 최단 경로와 행렬 곱셈
|
1 :
02 :
06
|
|
모든 쌍의 최단 경로 알고리즘, 모든 쌍의 최단 경로, 직전 원소 부분 그래프, 동적 프로그래밍 적용 단계, 모든 쌍 최단 경로 문제에 대한 재귀 해, 수행시간의 개선 | ||
|
[80강] 플로이드-워샬 알고리즘
|
0 :
56 :
56
|
|
최단 경로의 구조, 모든 쌍 최단 경로 문제에 대한 재귀 해, 최단 경로 가중치의 상향식 계산, 최단 경로의 구성, 방향 그래프의 이행적 폐쇄 | ||
|
[81강] 존슨 알고리즘
|
0 :
37 :
52
|
|
간선의 가중치 조정을 위한 충족 요건(특성), 가중치를 조정해 음이 아닌 가중치 만들기, 모든 쌍 최단 경로 계산 | ||
|
[82강] 플로우 네트워크
|
0 :
27 :
26
|
|
플로우 네트워크와 플로우, 플로우의 예& 역평행 간선의 변환, 다중 출발점과 도착점의 플로우 네트워크 | ||
|
[83강] 포드 풀커슨 방법 (1)
|
0 :
32 :
04
|
|
잔여 네트워크 | ||
|
[84강] 포드 풀커슨 방법 (2)
|
0 :
46 :
12
|
|
증강 경로 | ||
|
[85강] 포드 풀커슨 방법 (3)
|
0 :
42 :
21
|
|
최대 플로우 최소 절단 정리 | ||
|
[86강] 포드 풀커슨 방법 (4)
|
0 :
28 :
10
|
|
포드-풀커슨 알고리즘, 포드-풀커슨 알고리즘의 분석, 포드-풀커슨 알고리즘 최악의 경우 예 | ||
|
[87강] 포드 풀커슨 방법 (5)
|
0 :
53 :
11
|
|
에드몬드-카프 알고리즘, 에드몬드-카프 알고리즘의 반복 횟수 상한 | ||
|
[88강] 최대 이분 매칭
|
0 :
53 :
53
|
|
무방향 이분 그래프, 최대 이분 매칭 문제 | ||
| 7장. 알고리즘 분야의 중요한 토픽 | ||
|
[89강] 동적 멀티스레딩의 기본 (1)
|
0 :
37 :
35
|
|
병렬 알고리즘, 병렬 컴퓨터 모델, 스레드 | ||
|
[90강] 동적 멀티스레딩의 기본 (2)
|
0 :
55 :
03
|
|
멀티스레드 실행 모델, 성능 측정 | ||
|
[91강] 동적 멀티스레딩의 기본 (3)
|
0 :
44 :
19
|
|
스케줄링, 멀티스레드 알고리즘의 분석 | ||
|
[92강] 동적 멀티스레딩의 기본 (4)
|
0 :
51 :
04
|
|
병렬루프, 경쟁조건, 체스교훈 | ||
|
[93강] 멀티스레드 행렬의 곱셈
|
0 :
52 :
20
|
|
멀티스레드 행렬의 곱셈, 분할정보 멀티스레드 행렬의 곱셈, 멀티스레딩 스트라센의 방법 | ||
|
[94강] 멀티스레드 병합 정렬
|
0 :
54 :
01
|
|
중첩 병렬성 멀티스레드 병합 정렬, 멀티스레드 병합, 멀티스레드 병합 정렬의 분석 | ||
|
[95강] 선형 연립방정식의 해 (1)
|
0 :
41 :
49
|
|
미지수 n개의 선형 방정식, 가우스 소거법, LUP 분할의 개요, 전진 대입과 후진 대입 | ||
|
[96강] 선형 연립방정식의 해 (2)
|
0 :
55 :
21
|
|
가우스 소거법, LU 분할 계산, LUP 분할 계산 | ||
|
[97강] 역행렬
|
1 :
00 :
11
|
|
LUP 분할을 이용한 역행렬의 계산, 행렬의 곱과 역행렬, 전치 행렬을 이용한 선형 방정식의 해 | ||
|
[98강] 양으로 정의된 대칭 행렬과 최소-제곱 근사 (1)
|
0 :
43 :
17
|
|
양으로 정의된 대칭 행렬의 특성, Schur 보조 행렬 정의 | ||
|
[99강] 양으로 정의된 대칭 행렬과 최소-제곱 근사 (2)
|
0 :
32 :
34
|
|
최소-제곱 근사값 | ||
|
[100강] 선형 계획법
|
0 :
35 :
20
|
|
선형 계획법, 정치적 문제 | ||
|
[101강] 정규형과 이완형
|
0 :
59 :
57
|
|
정규형, 선형 계획법의 정규형으로 변환, 이완형 선형 계획법의 예 | ||
|
[102강] 문제의 선형 계획법 구성
|
0 :
41 :
06
|
|
최단 경로, 최대 플로우, 최소 비용 플로우, 다중 상품 플로우 | ||
|
[103강] 심플렉스 알고리즘 (1)
|
0 :
57 :
56
|
|
심플렉스 알고리즘의 예, 피벗 | ||
|
[104강] 심플렉스 알고리즘 (2)
|
0 :
52 :
32
|
|
공식화한 심플렉스 알고리즘 | ||
|
[105강] 심플렉스 알고리즘 (3)
|
0 :
31 :
43
|
|
종료 | ||
|
[106강] 쌍대성
|
1 :
02 :
16
|
|
쌍대성 선형 계획법, 쌍대성 선형 계획법의 최적해 | ||
|
[107강] 초기 가능한 기본 해
|
0 :
56 :
10
|
|
초기 해를 구함, 보조 선형 계획법 구성, 심플렉스 초기화 | ||
|
[108강] 다항식의 표현
|
0 :
57 :
24
|
|
계수 표현, 점값 표현, 점값 표현을 이용한 다항식 연산, 계수 형태 다항식의 고속 곱셈 | ||
|
[109강] DFT와 FFT (1)
|
0 :
59 :
11
|
|
단위값의 복소수 근 | ||
|
[110강] DFT와 FFT (2)
|
0 :
51 :
58
|
|
FFT, 단위값의 복소수 근에 의한 보간법 | ||
|
[111강] 효율적인 FFT의 구현
|
0 :
30 :
22
|
|
반복 FFT 구현, 병렬 FFT 회로 | ||
|
[112강] 기초 정수론
|
0 :
53 :
35
|
|
정수론 알고리즘, 기초 정수론, 유일 인수분해 | ||
|
[113강] 최대공약수
|
1 :
06 :
55
|
|
유클리드 알고리즘, GCD의 재귀정리, 유클리드 알고리즘의 수행시간, Lames의 정리, 확장된 유클리드 알고리즘 | ||
|
[114강] 모듈로 연산 (1)
|
0 :
53 :
54
|
|
유한군, 모듈로 덧셈과 곱셈에 의해 정의된 군, 군(연산)의 표현 | ||
|
[115강] 모듈로 연산 (2)
|
1 :
02 :
15
|
|
서브군, 라그랑주(Lagrange)의 정리, 한 원소에 의해 생성된 서브군 | ||
|
[116강] 모듈로 선형 방정식의 해
|
1 :
03 :
57
|
|
모듈로 선형 방정식의 해 | ||
|
[117강] 중국인의 나머지 정리
|
0 :
39 :
33
|
|
중국인의 나머지 정리 | ||
|
[118강] 원소의 거듭제곱
|
1 :
07 :
11
|
|
오일러의 정리, 반복제곱을 이용한 멱(거듭제곱) 계산 방법, 알고리즘의 타당성 증명 | ||
|
[119강] RSA 공개키 암호 시스템
|
0 :
48 :
29
|
|
공개키 암호 시스템, 공개키, 비밀키, 메세지 전송, 전자 서명, 암호화된 메세지/전자 서명 쌍 송수신, 전자 서명의 특징, RSA 암호시스템 | ||
|
[120강] 스트링 매칭 문제. 단순 스트링 매칭 알고리즘
|
0 :
38 :
36
|
|
스트링 매칭 문제의 정의, 적절한 시프트에 의한 스트링 매칭, 표기법과 용어, 스트링 비교 연산, 중복-접미부 보조정리, | ||
|
[121강] 라빈-카프 스트링 매칭
|
0 :
41 :
58
|
|
라빈-카프 스트링 매칭, 라빈-카프 스트링 매칭 알고리즘의 매칭 시간 | ||
|
[122강] 유한 오토마타를 이용한 스트링 매칭 (1)
|
1 :
03 :
56
|
|
유한 오토마타, 스트링 매칭 오토마타, 텍스트 스트링 T와 패턴 P의 매칭 | ||
|
[123강] 유한 오토마타를 이용한 스트링 매칭 (2)
|
1 :
09 :
58
|
|
접미부 함수 부등식, 순환 접미부 함수의 보조정리, 전이 함수 계산 알고리즘 | ||
|
[124강] 크누스-모리스-프랫 알고리즘
|
0 :
58 :
05
|
|
패턴의 접두부 함수, KMP 알고리즘 | ||
|
[125강] 보이어-무어 알고리즘
|
0 :
41 :
42
|
|
텍스트 점프 방법, 보이어-무어 알고리즘, 보이어-무어 휴리스틱 | ||
|
[126강] 선분의 특징
|
0 :
52 :
47
|
|
선분, 선분 관련 문제, 벡터 곱, 두 선분의 교차 여부 검사 | ||
|
[127강] 선분의 교차성 결정
|
0 :
58 :
51
|
|
선분의 순서화, 검사선의 이동, 선분 교차 알고리즘, 선분 교차 알고리즘의 수행시간 | ||
|
[128강] 볼록 껍질의 발견
|
0 :
57 :
31
|
|
그레이엄의 스캔, 자비스의 마치 | ||
|
[129강] 가장 가까운 점들의 쌍 구하기
|
0 :
39 :
16
|
|
유클리드 거리, 가장 가까운 점의 쌍을 구하는 알고리즘, 분할정복 알고리즘, 결합, 구현과 수행시간 | ||
|
[130강] NP-완비문제
|
0 :
41 :
19
|
|
다항 시간 알고리즘, NP-완비, 결정 문제 대 최적화 문제, 환원, NP-완비의 증명(환원 알고리즘) | ||
|
[131강] 다항 시간
|
1 :
02 :
16
|
|
다항 시간 알고리즘, 추상적 문제, 인코딩, 형식 언어 틀 | ||
|
[132강] 다항 시간 확인
|
0 :
56 :
10
|
|
해밀토니안 순환, 해밀토니안 순환 문제, 확인 알고리즘, 복잡성군 | ||
|
[133강] NP-완비성과 환원 가능성
|
1 :
06 :
25
|
|
환원 가능성, NP-완비성, 회로만족여부 | ||
|
[134강] NP-완비성 증명 (1)
|
0 :
44 :
00
|
|
식 만족여부 | ||
|
[135강] NP-완비성 증명 (2)
|
0 :
40 :
05
|
|
3-CNF 만족여부 | ||
|
[136강] NP-완비성 문제들 (1)
|
1 :
03 :
15
|
|
클릭 문제, 정점 덮개 문제 | ||
|
[137강] NP-완비성 문제들 (2)
|
1 :
04 :
05
|
|
해밀토니안 순환 문제, 순회 판매원 문제 | ||
|
[138강] NP-완비 문제들 (3). NP-하드 최적화 문제 확장
|
1 :
00 :
31
|
|
부분 집합 합 문제, 순회 판매원 문제(TSP) | ||
|
[139강] 정점 덮개 문제
|
0 :
31 :
15
|
|
NP-완비 극복 방법, 근사 알고리즘의 성능비, 최적에 가까운 정점 덮개 | ||
|
[140강] 순회 판매원 문제
|
0 :
45 :
43
|
|
삼각 부등식을 만족하는 순회 판매원 문제 | ||
|
[141강] 집합 덮개 문제
|
1 :
01 :
06
|
|
집합 덮개 문제의 사례, 드리디 근사 알고리즘 | ||
|
[142강] 랜덤화와 선형 계획법
|
0 :
31 :
38
|
|
MAX-3CNF 만족 문제의 랜덤화 근사 알고리즘, 선형 계획법을 이용한 정점 덮개 근사 | ||
|
[143강] 부분 집합의 합 문제
|
1 :
07 :
04
|
|
지수 시간에 정확한 최적해를 구하는 알고리즘, 완전 다항 시간 근사 전략 | ||
|
[144강] 상태공간 트리. 백트래킹
|
0 :
29 :
01
|
|
미로 찾기 문제 예, 미로 찾기 백트래킹 알고리즘, 색칠 문제 백트래킹 알고리즘 | ||
|
[145강] 한정분기. 알고리즘
|
0 :
54 :
06
|
|
최단경로찾기 문제, TSP | ||
