안희갑
포스텍 컴퓨터공학과 교수
UNIVERSITEIT UTRECHT 박사
香港科技大學(The Hong Kong University of Science and Technology) 박사
포항공과대학교 석사
Algorithm (알고리즘)
POSTECH
수강신청하실 수 없습니다.
강좌 소개
인공지능, 머신러닝, 알고리즘 트레이딩 등 다양한 기술에서 알고리즘은 핵심 이론이며 문제 해결의 기반입니다. 여러가지 복잡한 문제를 컴퓨터가 해결해주지만, 문제의 구조를 분석하여 최적의 알고리즘을 구현해야 컴퓨터가 빠르게 해답을 찾습니다.
본 강좌는 주어진 문제를 해결하는 가장 적합한 알고리즘의 설계와 분석 방법에 대해 학습합니다. 알고리즘에 대한 소개부터 시작하여 분할정복, 그리디 알고리즘, 동적계획법, 네트워크플로우 등 4가지의 기본적인 알고리즘 설계 기법에 대해서 학습합니다. 또한 다루기 힘든 문제의 유형에 대해서 학습하고, 정밀한 해를 찾는 알고리즘 이외에도 휴리스틱한 기법을 통해 단시간에 문제를 해결하는 방법에 대해서 소개합니다.
강좌 목차
| 주차 | 학습내용 | |
|---|---|---|
| 1 | 오리엔테이션 | 강의 개요 |
| 계산 효율성 | ||
| 계산 복잡도 표현(big O, Ω, Θ) | ||
| 2 | 정수론 알고리즘 | 정수론 알고리즘 기초 |
| 기초 연산 | ||
| 소수 판정 | ||
| 3,4 | 분할정복 | 분할정복 원리 |
| 이진 탐색 & 합병 정렬 | ||
| 행렬 곱하기 | ||
| 중앙값 찾기와 선택 알고리즘 | ||
| 가장 가까운 쌍 찾기 | ||
| 4,5 | 그래프 알고리즘 | 그래프 이론 기초 |
| 깊이 우선 탐색(DFS) | ||
| 너비 우선 탐색(BFS) | ||
| 최단 경로 문제 | ||
| 다익스트라 알고리즘 I | ||
| 다익스트라 알고리즘 II | ||
| 6,7 | 그리디 알고리즘 | 그리디 알고리즘 원리 |
| 최소신장트리 I | ||
| 최소신장트리 II | ||
| 허프만 코드 | ||
| 트리 군집화 | ||
| 작업 일정 짜기 문제 | ||
| 8,9 | 동적계획법 | 동적계획법 구조 |
| 사다리 올라가기 | ||
| 비트스트링 | ||
| 금화 모으기 | ||
| 행렬의 연속 곱 | ||
| 최단 신뢰 경로 | ||
| 모든 쌍 최단 경로 | ||
| 10 | 선형계획법 | 선형계획법 개론 |
| 이익 극대화 | ||
| 서포트 벡터 머신3 | ||
| 식단 구성하기 | ||
| 과제 할당하기 | ||
| 11 | 네트워크 플로우 | 네트워크 플로우 I |
| 네트워크 플로우 II | ||
| 12,13 | 계산 복잡도와 문제의 난이도 | P & NP |
| 되추적 | ||
| 분기한정법 | ||
| NP 문제 예시 | ||
| 휴리스틱 알고리즘 소개 | ||
교수자