편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
본격적으로 알고리즘을 종류별로 다룬다. 각 알고리즘을 적용하는 간단한 예시와 연습문제를 제공하니 풀어보면서 이해하는 것이 좋다. 연습문제는 acmicpc.net의 것을 링크한다. [[KOI]] 같은 경시대회를 대비하는데 도움이 될 수도..? | {{토막글}} | ||
본격적으로 알고리즘을 종류별로 다룬다. 각 알고리즘을 적용하는 간단한 예시와 연습문제를 제공하니 풀어보면서 이해하는 것이 좋다. 연습문제는 acmicpc.net의 것을 링크한다. [[KOI]]같은 경시대회를 대비하는데 도움이 될 수도..? | |||
== 알고리즘의 정당성 증명 == | == 알고리즘의 정당성 증명 == | ||
갑자기 | 갑자기 왠 뜬금없이 증명이 튀어나왔는지 궁금할 것이다. 당연하지만, 우리는 천재가 아니라서 머릿속으로 생각한 알고리즘이 실제로 아주 잘 돌아간다고 보장할 수 없기 때문에 생각해낸 알고리즘이 문제를 풀 수 있다는 것을 보여야 한다. | ||
=== 수학적 귀납법 === | === 수학적 귀납법 === | ||
다들 수학 공부하면서 한 번씩은 들어봤을 그것이다. 수학적 귀납법을 이용한 증명은 크게 ''단계 나누기''와 ''첫 단계 증명'', ''귀납 증명''으로 나눈다. 자세한 내용은 [[수학적 귀납법|해당 항목]] 참고. | 다들 수학 공부하면서 한 번씩은 들어봤을 그것이다. 수학적 귀납법을 이용한 증명은 크게 ''단계 나누기''와 ''첫 단계 증명'', ''귀납 증명''으로 나눈다. 자세한 내용은 [[수학적 귀납법|해당 항목]] 참고. | ||
22번째 줄: | 22번째 줄: | ||
=== 구성적 증명 === | === 구성적 증명 === | ||
위에 언급한 증명 방법들과는 달리, 구성적 증명은 답의 존재성을 보이는 게 아닌, ''답을 구하는 방법 그 자체를 보이는 것''이다. 쉽게 말해, 그냥 '''답을 구하는 알고리즘의 실행 과정을 설명'''한다고 생각하면 된다. | 위에 언급한 증명 방법들과는 달리, 구성적 증명은 답의 존재성을 보이는 게 아닌, ''답을 구하는 방법 그 자체를 보이는 것''이다. 쉽게 말해, 그냥 '''답을 구하는 알고리즘의 실행 과정을 설명'''한다고 생각하면 된다. | ||
== 정렬 알고리즘 == | == 고급 정렬 알고리즘 == | ||
=== 안정 정렬 === | === 안정 정렬 === | ||
비교한 값이 같을 때 서로 바뀌지 않는 정렬법을 안정 정렬이라고 한다. | 비교한 값이 같을 때 서로 바뀌지 않는 정렬법을 안정 정렬이라고 한다. | ||
28번째 줄: | 28번째 줄: | ||
==== 거품(Bubble) 정렬 ==== | ==== 거품(Bubble) 정렬 ==== | ||
[[수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초#거품(Bubble) 정렬|해당 항목]] 참고. | [[수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초#거품(Bubble) 정렬|해당 항목]] 참고. | ||
==== 병합(Merge) 정렬 ==== | ==== 병합(Merge) 정렬 ==== | ||
분할정복기법의 대표적 예이다. 소스는 은근 쉽다.<!-- 에러 수정바람 --> | 분할정복기법의 대표적 예이다. 소스는 은근 쉽다.<!-- 에러 수정바람 --> | ||
< | <source lang="C"> | ||
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; | int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; | ||
int tmparr[10]; | int tmparr[10]; | ||
69번째 줄: | 66번째 줄: | ||
arr[i] = tmparr[i]; | arr[i] = tmparr[i]; | ||
} | } | ||
</ | </source> | ||
[[파이썬]]에서 재귀 기법을 사용하는 병합 정렬의 예제는 다음과 같다. | [[파이썬]]에서 재귀 기법을 사용하는 병합 정렬의 예제는 다음과 같다. | ||
< | <source lang="Python"> | ||
def mergeSort(x): | def mergeSort(x): | ||
if len(x) <= 1: | if len(x) <= 1: | ||
95번째 줄: | 92번째 줄: | ||
result += R[j:] | result += R[j:] | ||
return result | return result | ||
</ | </source> | ||
* 연습문제 | * 연습문제 | ||
106번째 줄: | 103번째 줄: | ||
==== 선택(Selection) 정렬 ==== | ==== 선택(Selection) 정렬 ==== | ||
[[수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초#선택(Selection) 정렬|해당 항목]] 참고. | [[수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초#선택(Selection) 정렬|해당 항목]] 참고. | ||
==== 삽입(Insertion) 정렬 ==== | |||
[[수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초#삽입(Insertion) 정렬|해당 항목]] 참고. | |||
==== 퀵(Quick) 정렬 ==== | ==== 퀵(Quick) 정렬 ==== | ||
112번째 줄: | 112번째 줄: | ||
예를 들어, 5, 3, 7, 8, 6, 4, 2, 1, 0, 9를 정렬한다고 해보자. 맨 앞의 5를 기준으로 일단 정렬한다. 사람이 한다면 아마 3, 4, 2, 1, 0, '''5''', 7, 8, 6, 9가 될 것이다. 이 상태에서 5의 앞을 다시 정렬한다. 2, 1, 0, '''3''', 4와 '''5'''와 7, 8, 6, 9가 남았다. 이 때, 4는 3 뒤에 있는 오직 한 개의 수이므로 정렬이 되었다고 본다. 이런 식으로 하다 보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9의 올바른 순열이 나올 것이다. 소스는 다음과 같다.<ref>물론 최적화는 되어 있지 않다.</ref> | 예를 들어, 5, 3, 7, 8, 6, 4, 2, 1, 0, 9를 정렬한다고 해보자. 맨 앞의 5를 기준으로 일단 정렬한다. 사람이 한다면 아마 3, 4, 2, 1, 0, '''5''', 7, 8, 6, 9가 될 것이다. 이 상태에서 5의 앞을 다시 정렬한다. 2, 1, 0, '''3''', 4와 '''5'''와 7, 8, 6, 9가 남았다. 이 때, 4는 3 뒤에 있는 오직 한 개의 수이므로 정렬이 되었다고 본다. 이런 식으로 하다 보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9의 올바른 순열이 나올 것이다. 소스는 다음과 같다.<ref>물론 최적화는 되어 있지 않다.</ref> | ||
< | <source lang="C"> | ||
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; | int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; | ||
151번째 줄: | 151번째 줄: | ||
sort(j + 1, end); | sort(j + 1, end); | ||
} | } | ||
</ | </source> | ||
[[파이썬]]에서 재귀 기법을 사용하는 퀵 소트 함수의 예제는 다음과 같다. | [[파이썬]]에서 재귀 기법을 사용하는 퀵 소트 함수의 예제는 다음과 같다. | ||
< | <source lang="Python"> | ||
def quicksort(x): | def quicksort(x): | ||
if len(x) <= 1: | if len(x) <= 1: | ||
173번째 줄: | 173번째 줄: | ||
return quicksort(less) + equal + quicksort(more) | return quicksort(less) + equal + quicksort(more) | ||
</ | </source> | ||
퀵 정렬이 모든 경우에 항상 빠른 것은 아니다. {{ㅊ|거의 항상 빠른 것 뿐이다.}} 최악의 경우, 즉 이미 모든 자료가 | 퀵 정렬이 모든 경우에 항상 빠른 것은 아니다. {{ㅊ|거의 항상 빠른 것 뿐이다.}} 최악의 경우, 즉 이미 모든 자료가 거의 정렬된 상태인 경우라면 <math>O(n^2)</math>의 성능을 보일 수 있지만, 정렬 기준을 맨 앞 값 대신 아무거나 하나 골라 잡는 방법으로 해결하면 거의 대부분의 경우에 <math>O(n\log n)</math>의 성능을 보장받을 수 있다. 더불어 실제로 정렬 알고리즘을 돌렸을 때 퀵 정렬은 다른 <math>O(n\log n)</math> 알고리즘보다 캐시 히트 레이트가 높아 훨씬 더 빠르기 때문에 일반적으로 정렬의 대부분은 퀵 정렬 알고리즘을 활용한 형태를 사용한다. | ||
==== 힙(Heap) 정렬 ==== | ==== 힙(Heap) 정렬 ==== | ||
=== 그 밖의 정렬 알고리즘 === | === 그 밖의 정렬 알고리즘 === | ||
==== 버킷( | ==== 버킷(Bukket) 정렬 ==== | ||
==== 자릿수(Radix) 정렬 ==== | ==== 자릿수(Radix) 정렬 ==== | ||
== 고급 자료구조 == | |||
== 브루트 포스 == | == 브루트 포스 == | ||
컴퓨터의 [[크고 아름다운]] 우월한 성능을 이용하여 모든 경우의 수를 시도하는 방법이다. 이 방법을 전문용어로 완전탐색 알고리즘이라고 한다. | 컴퓨터의 [[크고 아름다운]] 우월한 성능을 이용하여 모든 경우의 수를 시도하는 방법이다. 이 방법을 전문용어로 완전탐색 알고리즘이라고 한다. | ||
189번째 줄: | 189번째 줄: | ||
문제를 쓸데없이 어렵게 접근하여 골치아파하지 말고 이 방법을 가장 먼저 적용하자. 이 방법도 나쁜 방법이 아니며, 준수한 성능을 내는 알고리즘을 설계할 수 있는 좋은 방법이다. | 문제를 쓸데없이 어렵게 접근하여 골치아파하지 말고 이 방법을 가장 먼저 적용하자. 이 방법도 나쁜 방법이 아니며, 준수한 성능을 내는 알고리즘을 설계할 수 있는 좋은 방법이다. | ||
다만 이 방법을 쓰려 한다면, 리소스를 많이 써먹을 수 있는 | 다만 이 방법을 쓰려 한다면,리소스를 많이 써먹을 수 있는 프로그렘을 짤 수 있다는 전제조건이 따라붙는다. 크고 아름다운 성능을 이용하려 해도 싱글코어밖에 못 쓰는 프로그렘이라면 빛이 바랠 것이다. | ||
== 분할 정복 == | == 분할 정복 == | ||
199번째 줄: | 199번째 줄: | ||
미리 모든 필요한 데이터들을 DP Table에 채워넣고 거기서 값을 뽑아서 계산하고 출력하는 방식이다. 스택 오버플로우가 날 일이 없어지고, 수행 시간이 줄어들며 토글링을 적용할 수 있다는 장점이 있다. | 미리 모든 필요한 데이터들을 DP Table에 채워넣고 거기서 값을 뽑아서 계산하고 출력하는 방식이다. 스택 오버플로우가 날 일이 없어지고, 수행 시간이 줄어들며 토글링을 적용할 수 있다는 장점이 있다. | ||
== 탐욕법 == | == 탐욕법 == | ||
그리디 알고리즘 또는 욕심쟁이 알고리즘 등으로도 불리운다. 현재 봤을 때 가장 | 그리디 알고리즘 또는 욕심쟁이 알고리즘 등으로도 불리운다. 현재 봤을 때 가장 최적해같아 보이는 것을 선택하는 알고리즘이다. 근사해를 구할 때 쓰이면 가장 좋으나, 최적해를 구할 때에는 역추적을 해야만 한다. 가장 사람을 잘 흉내내는 알고리즘이다.{{--|이런 욕심쟁이들.}} | ||
== 파라매트릭 서치 == | == 파라매트릭 서치 == | ||
206번째 줄: | 206번째 줄: | ||
== 트리 == | == 트리 == | ||
=== 구현과 순회 === | === 구현과 순회 === | ||
=== | === Union-Find 알고리즘 === | ||
=== 이진 검색 트리 === | === 이진 검색 트리 === | ||
이진 검색 트리는 고급 자료구조를 위해서 다양하게 활용되기도 한다. 그에 관해서는 다음 문서를 참고. | 이진 검색 트리는 고급 자료구조를 위해서 다양하게 활용되기도 한다. 그에 관해서는 다음 문서를 참고. | ||
233번째 줄: | 232번째 줄: | ||
C 코드로 표현하면 다음과 같다. | C 코드로 표현하면 다음과 같다. | ||
< | <source lang=c> | ||
for(int k = 1; k <= n; ++k) | for(int k = 1; k <= n; ++k) | ||
for(int i = 1; i <= n; ++i) | for(int i = 1; i <= n; ++i) | ||
for(int j = 1; j <= n; ++j) | for(int j = 1; j <= n; ++j) | ||
cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); | cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); | ||
</ | </source> | ||
이 때, cost[i][j]의 초기값에는 둘을 잇는 간선이 있을 경우 그 간선의 코스트, 없을 경우 무한대에 해당하는 매우 큰 값을 넣는다. | 이 때, cost[i][j]의 초기값에는 둘을 잇는 간선이 있을 경우 그 간선의 코스트, 없을 경우 무한대에 해당하는 매우 큰 값을 넣는다. | ||
245번째 줄: | 244번째 줄: | ||
==== 데이크스트라(Dijkstra) 알고리즘 ==== | ==== 데이크스트라(Dijkstra) 알고리즘 ==== | ||
{{--|이거 왜 그리디에 없고 여기 있냐}} | {{--|이거 왜 그리디에 없고 여기 있냐}} | ||
[[ | 최단거리를 찾는 알고리즘이다. 움짤이 여럿 돌아다니니 한 번 보자. | ||
[[File:Shortest path Dijkstra vs BellmanFord.gif|thumb|Shortest path Dijkstra vs BellmanFord]] | |||
{{--|c부터 조사하지 않는 게 수상하긴 하지만 }}윗 것은 데이크스트라, 아랫 것은 벨먼 포드 알고리즘이다. 이것만 보고도 이해할 수 있다면 참 좋겠다. <!-- 다음은 그 소스이다. c로 구현하기 힘든데...--> | {{--|c부터 조사하지 않는 게 수상하긴 하지만 }}윗 것은 데이크스트라, 아랫 것은 벨먼 포드 알고리즘이다. 이것만 보고도 이해할 수 있다면 참 좋겠다. <!-- 다음은 그 소스이다. c로 구현하기 힘든데...--> | ||
254번째 줄: | 254번째 줄: | ||
[[추가바람]] | [[추가바람]] | ||
벨먼-포드의 알고리즘은 데이크스트라의 알고리즘과 비슷한 시기에 나왔으나, 데이크스트라의 알고리즘에 비하면 계산 횟수는 더 안 좋지만, 계산 과정과 전달 자체만은 비교적 간결한 형태를 | 벨먼-포드의 알고리즘은 데이크스트라의 알고리즘과 비슷한 시기에 나왔으나, 데이크스트라의 알고리즘에 비하면 계산 횟수는 더 안 좋지만, 계산 과정과 전달 자체만은 비교적 간결한 형태를 띄고 있다. 인터넷에서 라우터가 라우팅을 할 때 사용되는 방법 중 하나인 라우팅 정보 프로토콜(RIP)에서 이 알고리즘을 사용하고 있다. OSPF에 비해서는 비교적 간결한 통신을 하지만, 순환 경로나 수신자가 메시지 도착 전에 가동 불능이 되는 경우에는 문제가 생길 수 있다는 단점이 있다. | ||
=== 위상 정렬 === | === 위상 정렬 === | ||
267번째 줄: | 267번째 줄: | ||
=== 강연결요소(SCC) === | === 강연결요소(SCC) === | ||
=== 네트워크 | === 네트워크 유량 === | ||
네트워크 유량을 계산하는 포드-풀커슨 알고리즘이 존재한다. | |||
== 문자열 알고리즘 == | == 문자열 알고리즘 == | ||
285번째 줄: | 281번째 줄: | ||
접미사 트리에서 필요한 리프노드 부분만 잘라낸 배열인데, 프로그래밍 대회에서 접미사 트리는 잘 안쓰기 때문에 항목명을 바꾸었다. | 접미사 트리에서 필요한 리프노드 부분만 잘라낸 배열인데, 프로그래밍 대회에서 접미사 트리는 잘 안쓰기 때문에 항목명을 바꾸었다. | ||
문자열의 맥가이버 칼이라고 불릴 정도로 정말로 각종 프로그래밍 문제에서 쓰인다. 접미사 배열을 제안한 밴머와 마이어스의 알고리즘을 이용해 <math>O\left( nlg^2n \right)</math><ref><math>O\left( nlgn \right)</math>으로도 구현할 수 있지만, 복잡하고 <math>O\left( nlg^2n \right)</math>으로도 충분해서 안쓴다</ref>의 시간 복잡도로 생성할 수 있다. | 문자열의 맥가이버 칼이라고 불릴 정도로 정말로 각종 프로그래밍 문제에서 쓰인다. 접미사 배열을 제안한 밴머와 마이어스의 알고리즘을 이용해 <math>O\left( nlg^2n \right)</math><ref><math>O\left( nlgn \right)</math>으로도 구현할 수 있지만, 복잡하고 <math>O\left( nlg^2n \right)</math>으로도 충분해서 안쓴다</ref>의 시간 복잡도로 생성할 수 있다. | ||
{{각주}} | |||
[[작성중]] | |||
[[분류:집단연구]] | |||
[[분류:수학인듯 과학아닌 공학같은 컴퓨터과학]] | [[분류:수학인듯 과학아닌 공학같은 컴퓨터과학]] | ||
[[분류:컴퓨터 과학]] | [[분류:컴퓨터 과학]] |