국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Motivation 외판원 순환 문제 (TSP : Travelling salesman problem) 모든 정점을 방문하고 시작 정점으로 돌아오는 최단 경로를 찾는 문제인데 Brute-force 방식으로 n개의 정점의 모든 permutation(순열)을 조사해야함 => O(n!) TSP 문제를 다항시간에 푸는 알고리즘이 존재할까? 이론상 불가능함 Types of Problems Tractable Problem : 입력 n에 대하여 푸는데 걸리는 시간이 다항 함수 f(n) 으로 표현 되는 문제 Intractable Problem: 다항 시간안에 풀 수 없는 문제=> Θ(2^n) ..
