|
'''
이론 컴퓨터 과학 {{{#!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=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | 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. 정의
그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.예를 들어 5개의 도시를 모두 한 번씩만 거쳐서 여행하고 싶은데 여행 도중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 사용할 수 있는 전략은 몇 가지가 있다. 가능한 120가지의 경우의 수를 브루트 포스로 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이고, 외판원 순회 문제 문서에 나와있는 복잡한 전략을 쓸 수도 있고, "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법, 즉 그리디 알고리즘을 쓸 수도 있다.
단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위와 같은 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 살짝 먼 길을 섞어서 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다. 스탠퍼드 마시멜로 실험에 비유하면 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.
2. 특징
그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.예를 들어서 상기의 외판원 순회 문제는 도로가 어떻게 생겼는지에 따라서 다음 선택에 영향이 가기 때문에 쓸 수 없다.
2.1. 최적 부분 구조
|
|
최적 부분 구조를 좀 더 살펴보면 그림과 같이 설명할 수 있다. 서울에서 대구를 거쳐 부산까지 가는 최단 경로를 찾는다고 가정해보자. 그림에서 보듯이, 서울에서 대구까지 가는 경로는 3가지가 있으며, 부산까지도 마찬가지로 3가지 경로가 있다. 서울에서 부산까지 가는 최단 경로는 200km + 80km = 280km이다. 이 경로는 서울에서 대구까지 가는 최단 경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다. 즉, 서울에서 대구를 거쳐 부산까지 가는 최단 경로는 각각의 부분 문제인 1)서울에서 대구까지 가는 최단 경로 문제와 2)대구에서 부산까지 가는 최단 경로 문제의 해결 방법의 합이다. 따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다. 이러한 구조를 최적 부분 구조라 한다.
3. 근사 알고리즘
상기했다시피 그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만 어느 정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 사용이 가능하다.또한 어떤 복잡한 알고리즘과 함께 사용될 수도 있다. 그리디로 빠르게 구한 값을 비교값으로 설정 후 그 값보다 낮은 값을 만들어내는 경로는 가지치기하여 복잡한 알고리즘의 시간을 단축시킬 수 있기도 하다.
이렇게 만들어진 "적당히" 괜찮은 해답이 진짜로 적당히 괜찮은지에 대해서는 또 다른 판단이 필요하다. 문제를 푸는 사람이 엄밀한 해답을 요하는 수학자라면, 적당히 괜찮은 정도로는 충분하지 않다. 문제의 상황이 그리디 알고리즘에 불리한 경우라면, 적당히 괜찮은 해답이 아니라 매우 안 좋은 해답이 나올 수도 있다. 외판원 순회 문제에 대해서 그리디 알고리즘이 최악의 해답을 만들어내는 상황을 쉽게 만들어 낼 수 있다.
4. 예시
- 결정 트리 학습(Decision Tree Learning)
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제. 단, 동전들에 배수관계가 성립할 때만 한정. 대부분의 화폐는 1, 5, 10, 25, 50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.
- 최소 신장 트리(Minimum spanning tree)
- 제약조건이 많은 대부분의 문제. 항상 그런 것은 아니지만, 프로그래밍 문제를 풀 때 제약조건이 많다면 의외로 그리디로 풀리는 경우가 많다.
- 다익스트라 알고리즘
- 허프만 코드
- 크루스칼 알고리즘