| {{{#!wiki style="margin: -5px -10px; padding: 10px 0px; color:#fff; background-image: linear-gradient(to right, #33CCCC , #0066DC); word-break:keep-all" 컴퓨터 과학 & 공학 Computer Science & Engineering {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-8px -1px -11px" | <colbgcolor=#3CC>기반 학문 | 수학 (해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학 (환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학 (형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 |
하드웨어 구성 | SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 | |
| 기술 | 기계어 · 어셈블리어 · C(C++) · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍(디자인 패턴) · 해킹 · ROT13 · OTP · IoT · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 | |
| 연구 · 기타 | 논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 디자인 패턴 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) | }}}}}}}}} |
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#aa3366> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.
그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까?만약 도시가 20개라고 할 때 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 [math(20!)]다. 이 값은 얼마나 될까? [math(20!=2,432,902,008,176,640,000)]이다. 그러니까 약 240경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있다. 문제는 단순하지만 정답은 실로 엄청나다.
2. 문제의 정의
외판원 순회 문제는 다음과 같이 그래프 이론의 용어로 엄밀하게 정의할 수 있다.주어진 완전 그래프 G=(V, E)가, 연결되어 있고(connected) 가중치가 있는(weighted) 완전한(complete) 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾아라.
3. 문제의 해결
외판원 순회 문제는 NP-완전 집합에 속하는 문제라는 것이 증명되었다. 다항 시간에 이 문제를 해결할 수 있는 알고리즘을 아무도 찾지 못했으며, 그렇다고 다항 시간에 문제를 해결하지 못한다는 것도 아무도 증명하지 못했다. 만약 이 문제를 다항 시간에 해결할 수 있는 알고리즘을 발견하거나, 다항 시간에 해결이 불가능함을 명확히 증명한다면 100만 달러의 상금을 받을 수 있다.3.1. 동적 계획법으로 풀기
외판원 순회 문제의 최적해는 동적 계획법으로 지수 시간에 풀 수 있다. 다음은 동적 계획으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.#!syntax python
def travel (W):
n = len(W) - 1
size = 2 ** (n - 1)
D = [[0] * size for _ in range(n + 1)]
P = [[0] * size for _ in range(n + 1)]
for i in range(2, n + 1):
D[i][0] = W[i][1]
for k in range(1, n - 1):
for A in range(1, size):
if (count(A, n) == k):
for i in range(2, n + 1):
if (not isIn(i, A)):
D[i][A], P[i][A] = minimum(W, D, i, A)
A = size - 1
D[1][A], P[1][A] = minimum(W, D, 1, A)
return D, P
def minimum (W, D, i, A):
minValue = INF
minJ = 1
n = len(W) - 1
for j in range(2, n + 1):
if (isIn(j, A)):
m = W[i][j] + D[j][diff(A, j)]
if (minValue > m):
minValue = m
minJ = j
return minValue, minJ
3.2. 분기 한정으로 풀기
외판원 순회 문제의 최적해는 분기 한정(Branch-and-Bound)으로 지수 시간에 풀 수 있다. 다음은 분기 한정으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.#!syntax python
def travel2 (W):
global minlength, opttour
n = len(W) - 1
PQ = PriorityQueue()
v = SSTNode(0)
v.path = [1]
v.bound = bound(v, W)
minlength = INF
PQ.put((v.bound, v))
while (not PQ.empty()):
v = PQ.get()[1]
if (v.bound < minlength):
for i in range(2, n + 1):
if (v.contains(i)):
continue
u = SSTNode(v.level + 1)
u.path = v.path[:]
u.path.append(i)
if (u.level == n - 2):
for k in range(2, n + 1):
if (not u.contains(k)):
u.path.append(k)
u.path.append(1)
if (length(u.path, W) < minlength):
minlength = length(u.path, W)
opttour = u.path[:]
else:
u.bound = bound(u, W)
if (u.bound < minlength):
PQ.put((u.bound, u))
def bound(v, W):
n = len(W) - 1
total = length(v.path, W)
for i in range(1, n + 1):
if (hasOutgoing(i, v.path)):
continue
min = INF
for j in range(1, n + 1):
if (i == j): continue
if (hasIncoming(j, v.path)): continue
if (j == 1 and i == v.path[len(v.path) - 1]): continue
if (min > W[i][j]): min = W[i][j]
total += min
return total