들어가기 전
일단 이게 입문인지부터 생각해보자
빨간 컵에 칠성사이다가 담겨져 있고 파란 컵에 스프라이트가 담겨져있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 안된다고는 안했다. 알고리즘은 문제를 해결하기 위한 것이지 수수께끼나 넌센스 문제가 아니다.
이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스 처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. 이제 제 3의 변수를 쓰지 않고 변수 2개의 값을 맞바꾸는 알고리즘을 생각해보자.
| 의사코드 펼치기 |
|---|
1 function 바꾸기(첫번째컵, 두번째컵): 2 잠시담아둘컵 ← 첫번째컵 3 첫번째컵 ← 두번째컵 4 두번째컵 ← 잠시담아둘컵 5 end function 6 7 function 지금상황(): 8 파란컵 ← "칠성사이다" 9 빨간컵 ← "스프라이트" 10 바꾸기(파란컵, 빨간컵) 11 print 파란컵 12 print 빨간컵 13 end function |
using System;
namespace 사이다컵바꾸기
{
class Program
{
static void Main(string[] args)
{
// 빨간 컵과 파란 컵에 칠성사이다와 스프라이트가 담겨져 있다.
string 빨간컵 = "칠성사이다";
string 파란컵 = "스프라이트";
Console.WriteLine("=====바꾸기 전=====");
Console.WriteLine("빨간컵 : {0}", 빨간컵);
Console.WriteLine("파란컵 : {0}", 파란컵);
// 새롭게 준비한 노란 컵
string 노란컵;
// 스프라이트를 빨간 컵에 붓기 위해 칠성사이다를 노란컵에 붓는다.
// 그 다음 파란 컵의 스프라이트를 빨간 컵에 붓는다.
// 그 다음 노란 컵에 임시로 담아둔 칠성 사이다를 파란 컵에 붓는다.
노란컵 = 빨간컵;
빨간컵 = 파란컵;
파란컵 = 노란컵;
Console.WriteLine("=====바꾼 후=====");
Console.WriteLine("빨간컵 : {0}", 빨간컵);
Console.WriteLine("파란컵 : {0}", 파란컵);
}
}
}
여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값을 b에 저장한다. 그 다음 a에서 b를 뺀 값을 a에 저장하면 된다. 숫자가 아니고 객체면? 포인터 주소값을 더하고 빼면... ... 사실 덧셈보다 더 빠른 방법은 XOR 회로를 사용하는법이 있다. 값이 같지 않으면 a=a^b b=a^b a=a^b를 넣어두면 정수가 아니더라도, 산술적 연산이 아니라 비트 배열 자체가 바뀌기 때문에 값이 교환된다.하지만 병렬 프로그래밍에서는 무리DA☆ZE★
알고리즘의 시간 복잡도
방을 정리한다고 해보자. 방에 널려있는 물건의 양에 따라 정리에 걸리는 시간이 달라질 것이다. 이렇게 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이걸 알고리즘의 시간 복잡도라 한다.
알고리즘의 시간 복잡도는 계산 횟수가 많아지면 높아진다. 그런데 이 계산 횟수의 정확한 측정이 어렵기 때문에, 보통 Big O 표기법이라는 걸 이용해서 표시한다.
예를 들어, 입력된 데이터의 갯수가 [math]\displaystyle{ n }[/math]개일 때 [math]\displaystyle{ 2n+7 }[/math]번 계산하는 알고리즘과 [math]\displaystyle{ 2n }[/math]번 계산하는 알고리즘이 있다고 하자. [math]\displaystyle{ n }[/math]이 커지면 둘 사이의 차이는 사실상 없어진다. 즉 [math]\displaystyle{ O(2n+7)=O(2n) }[/math]이다. 좀 더 나아가면 계산 횟수가 [math]\displaystyle{ n }[/math]에 비례하므로, 그냥 [math]\displaystyle{ O(n) }[/math]라고 표현할 수 있다. 일반적으로, 이 중 가장 간단한 형태인 [math]\displaystyle{ O(n) }[/math]로 표기한다. 이와 비슷하게, [math]\displaystyle{ 2n^3+n^2 }[/math]번 계산하는 알고리즘의 시간 복잡도는 [math]\displaystyle{ O(n^3) }[/math]로 나타낼 수 있다.
자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다. 위에서 아래로 갈수록 시간 복잡도가 높아진다.
| 시간 복잡도 | 설명 |
|---|---|
| [math]\displaystyle{ O(1) }[/math] | 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다. |
| [math]\displaystyle{ O(\log n) }[/math] | 로그 형태 |
| [math]\displaystyle{ O(n) }[/math] | 선형 |
| [math]\displaystyle{ O(n\log n) }[/math] | 선형로그 형태 |
| [math]\displaystyle{ O(n^2), O(n^3),\cdots }[/math] | 다차 형태 |
| [math]\displaystyle{ O(2^n) }[/math] | 지수 형태 |
| [math]\displaystyle{ O(n!) }[/math] | 팩토리얼 형태 |
예를 들어 아래의 링크드 리스트에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 [math]\displaystyle{ O(n) }[/math], 해시 테이블에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 [math]\displaystyle{ O(1) }[/math]이다. 이는 평균적으로 해시 테이블에서의 탐색이 링크드 리스트에서의 탐색보다 빠르다는 뜻이다.
알고리즘의 정당성 증명
수학적 귀납법
반복문 불변식
귀류법
비둘기집의 원리
구성적 증명
이 문서에서 알고리즘을 표현한 언어
아래 나오는 모든 코드는 C언어를 기본으로[1][2], 다른 언어들은 알아서 추가해주길 바란다. 실제 문제 풀이 예제를 제외한 알고리즘을 의사코드로 작성할 수 있다면 각 언어별 코드보다 위에 의사코드 버전을 추가해주길 바란다.
플로우 차트
기호
자료구조
선형 자료구조
선형 랜덤 접근 가능
배열
가장 쉬운 자료구조이자 가장 언어에 따라 달라지는 자료구조. c언어에서는 대괄호를 사용한다.
int array1[]; //int *array1과 비슷함.
int array2[10]; //크기를 가지는 배열
int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열
해시
해시는 해시 함수로 구현한다. 해시 함수는 마치 배열처럼, 어떤 자료를 찾을 때 O(1)의 시간만을 소요한다. 해시함수에 키 값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다. 하지만, 언제나 O(1)이 보장되는 것은 아니다. 자세한 것은 해시 테이블 참고.
선형 랜덤 접근 불가능
스택
후입선출(後入先出) 자료구조 스택이다. push 함수와 pop 함수를 갖는 게 정석이며, 추가로 옵션함수(empty, full 등)을 가질 수 있다. 아래는 배열로 구현한 스택이다.[3]
//헤더 부분
void push(int); //push 함수 정의
int pop();
//소스 부분
int array[500]; //스택의 최대 크기는 500
int top = -1; //스택의 현재 크기는 0;
void push(int n)
{
array[++top] = n;
}
int pop()
{
return array[top--];
}
사용법은 스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다.
push(1), push(2), push(3);
printf("%d %d %d", pop(), pop(), pop());
출력 결과는 3 2 1과 같을 것이다.
큐
선입선출(先入先出) 자료구조 큐이다. put 함수와 get 함수를 가진다. 밑의 큐는 연결 리스트로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다.
void put(int);
int get();
struct linkedList
{
int value;
struct linkedList *next;
};
struct linkedList *front;
struct linkedList *rear;
//포인터가 있어서 이해하기 힘들지만 찬찬히 뜯어보면 그리 어렵지 않은 내용이다.
void put(int n)
{
if(front == NULL)
{
*front = {n, NULL};
rear = front;
}
else
{
rear -> *next = {n, NULL};
rear = rear -> next;
}
}
int get()
{
int res = front -> value;
front = front -> next;
return res;
}
데크
링크드 리스트
연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다.[4] 가장 간단하게 구현한 것은 위의 큐(...). 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다.
앞 또는 뒤 노드만 링크된 단방향과 둘 다 링크된 양방향 두 종류가 있다.
비선형 자료구조
아래 참조
그래프
트리
힙
문자열
알고리즘을 설계하는 일반적인 방법
최적화 문제와 결정 문제
분할 정복
동적 계획법
제귀적 방법
반복적 방법
탐욕법
그리디 알고리즘 또는 욕심쟁이 알고리즘 등으로도 불리운다. 현재 봤을 때 가장 최적해같아 보이는 것을 선택하는 알고리즘이다. 근사해를 구할 때 쓰이면 가장 좋으나, 최적해를 구할 때에는 역추적을 해야만 한다. 가장 사람을 잘 흉내내는 알고리즘이다.이런 욕심쟁이들.
그리디 알고리즘을 사용하기 위해서는 정렬이 된 자료가 필요하다.
조합 탐색
정렬 알고리즘
크기순, 사전순과 같이 정렬하는 알고리즘을 말한다. 효율적인 알고리즘들 중 대부분은 데이터가 사전에 정렬되어 있을 것을 요구하는 것이 많다.
일단 이걸 보고 뭘 배우면 좋을 지 생각해보자.
안정 정렬
비교한 값이 같을 때 서로 바뀌지 않는 정렬법을 안정 정렬이라고 한다.
거품(Bubble) 정렬
세상에서 가장 만만한 정렬(...). 바로 뒤의 원소와 비교해 더 크다면 뒤로 간다. 뒤에서부터 차례차례 정렬돼가는 것을 보면…. 하지만 가능하면 쓰지는 말자. 성능으로 치면 가장 구린 정렬. 캐시 히트 레이트로나 여러가지 면으로 매우 좋지 않지만 워낙 알고리즘 자체가 간단하기 때문에 보통 입문용으로 가르치곤 하지만...
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};
void sort()
{
int i, j;
for(i = 0; i < 10; i++)
for(j = i; j < 9; j++)
if(arr[j] > arr[j + 1]) //j번째 원소가 다음 원소보다 크다면 바꾼다.
{
arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
}
}
병합(Merge) 정렬
분할정복기법의 대표적 예이다. 소스는 은근 쉽다.
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};
int tmparr[10];
void sort(int, int);
void merge(int, int);
void sort(int start, int end)
{
if(end > start)
{
sort(start, (start + end) / 2);
sort((start + end) / 2 + 1, end);
}
merge(start, end);
}
void merge(int start, int end) //여기가 진짜다.
{
int i = start, j = (start + end) / 2 + 1;
int count = start;
while(i <= (start + end) / 2 && j <= end)
{
if(arr[i] > arr[j])
{
tmparr[count++] = arr[j++];
}
else
{
tmparr[count++] = arr[i++];
}
}
while(i <= (start + end) / 2)
{
tmparr[count++] = arr[i++];
}
while(j <= end)
{
tmparr[count++] = arr[j++];
}
for(i = start; i <= end; i++)
{
arr[i] = tmparr[i];
}
}
불안정 정렬
비교한 값이 같을 때 서로 바뀌는 정렬법을 불안정 정렬이라고 한다.
선택(Selection) 정렬
삽입(Insertion) 정렬
퀵(Quick) 정렬
정렬의 왕이다. 평균 [math]\displaystyle{ O(n \log n) }[/math]인 정렬 알고리즘들 중 가장 빠르다. 피봇을 잡고 하는 건 너무 어렵고, 예를 들어 설명하자면 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의 올바른 순열이 나올 것이다. 소스는 다음과 같다.[5]
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};
void sort(int, int);
void sort(int start, int end)
{
int i = start + 1;
int j = end;
if(end < start)
return;
while(i < j)
{
while(arr[i] <= arr[start])
{
i++;
}
while(arr[j] >= arr[start])
{
j--;
}
if(i < j)
{
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
if(arr[start] > arr[j])
{
arr[start] = arr[start] ^ arr[j];
arr[j] = arr[start] ^ arr[j];
arr[start] = arr[start] ^ arr[j];
}
sort(start, j - 1);
sort(j + 1, end);
}
퀵 정렬이 모든 경우에 항상 빠른 것은 아니다. 가장 나쁠 때인 이미 모든 숫자가 거의 정렬된 상태인 경우라면 O(n²)의 성능을 보일 수 있지만, 정렬 기준을 설정할 때 맨 앞 값이 아닌 임의의 한 값을 고르는 방법으로 해결하면 거의 대부분의 경우에 O(n lg n)의 성능을 보장받을 수 있다. 더불어 실제로 정렬 알고리즘을 돌렸을 때 퀵 정렬은 다른 O(n lg n) 알고리즘보다 캐시 히트 레이트가 높아 훨씬 더 빠르기 때문에 일반적으로 정렬의 대부분은 퀵 정렬 알고리즘을 활용한 형태를 사용한다.
힙(Heap) 정렬
그 밖의 정렬 알고리즘
버킷(Bukket) 정렬
자릿수(Radix) 정렬
수치해석
정수론
계산 기하
트리
구현과 순회
Union-Find 알고리즘
이진 검색 트리
이진 검색 트리는 고급 자료구조를 위해서 다양하게 활용되기도 한다. 그에 관해서는 다음 문서를 참고.
힙
힙은 트리의 일종으로 부모 노드 값이 항상 자식 노드 값보다 큰 트리를 말한다. 힙소트 할때 쓰는 트리이다. 보통 이진트리로 구현한다. 힙에 새 원소를 넣고 빼는 데에는 [math]\displaystyle{ O(n \log n) }[/math]의 시간 복잡도를 가진다. 뭔가 힙보다 힙정렬이 더 앞에 있는 것 같은 건 눈의 착각이다.
C로 힙을 구현하는 방법은 크게 두 가지, 배열과 포인터가 있다. 포인터로 하는 방법은 직관적이지만 많은 자원(메모리 또는 시간)이 소모된다. 하지만 배열은 힙의 각 노드를 배열의 어떤 인덱스에 대응시킬지 고민해야 하지만 훨씬 자원을 효율적으로 사용할 수 있다.
구간 트리
트라이
그래프
수학, 과학 시간에 많이 보던 그 그래프와는 사뭇 다르다. 알고리즘을 배우다 보면 어쩌면 가장 많이 나오는 부분일 지도 모른다. 주로 노드와 엣지로 표현된다. 왠지 노드는 동그라미이고 엣지는 선이다. '그래프 구조'로 검색하면 그런 그림을 볼 수 있다. 간단한 구조체를 만들어 보자.
struct Edge //노드보다는 엣지로 나타내는 편이 대부분의 경우에 더 좋다.
{
int snode; //시작 노드
int enode; //종료 노드
//int cost; //가중치를 가지는 엣지에 사용된다.
};
struct Edge가 하나 이상 있는 것이 바로 그래프이다.
순회 알고리즘
깊이 우선 탐색
Depth First Search, DFS
너비 우선 탐색
Breadth First Search, BFS
최단 경로
편의상 [math]\displaystyle{ i\longrightarrow j }[/math]로 이동하는 경로의 최소 비용을 [math]\displaystyle{ cost\left[i\right]\left[j\right] }[/math]라고 표기한다.
플로이드-워셜(Floyd-Warshall) 알고리즘
가장 쉬운 알고리즘이면서, 가장 최악의 효율을 가진 알고리즘이다. 그래프 상에 비용이 음수인 간선이 존재하지 않아야 한다.
현재까지 구한 [math]\displaystyle{ i }[/math]에서 [math]\displaystyle{ j }[/math]로 가는 최소 비용보다 [math]\displaystyle{ i }[/math]에서 [math]\displaystyle{ k }[/math]를 거쳐 [math]\displaystyle{ j }[/math]로 가는 최소비용이 더 작다면 [math]\displaystyle{ cost\left[i\right]\left[j\right] }[/math]를 [math]\displaystyle{ cost\left[i\right]\left[k\right] + cost\left[k\right]\left[j\right] }[/math]로 대치한다. 이렇게 해서 모든 [math]\displaystyle{ \left(i, j\right) }[/math]에 대해 [math]\displaystyle{ cost\left[i\right]\left[j\right] }[/math]를 [math]\displaystyle{ O \left( n^3 \right) }[/math]로 구할 수 있다.
C 코드로 표현하면 다음과 같다.
for(int k = 1; k <= n; ++k)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(cost[i][j] > cost[i][k] + cost[k][j]) cost[i][j] = cost[i][k] + cost[k][j];
}
}
}
데이크스트라(Dijkstra) 알고리즘
이거 왜 그리디에 없고 여기 있냐
최단거리를 찾는 알고리즘이다. 움짤이 여럿 돌아다니니 한 번 보자.
c부터 조사하지 않는 게 수상하긴 하지만 윗 것은 데이크스트라, 아랫 것은 벨먼 포드 알고리즘이다. 이것만 보고도 이해할 수 있다면 참 좋겠다.
데이크스트라의 알고리즘은 인터넷의 네크워크 계층에서 라우터가 라우팅을 할 때 사용되는 방법 중 하나로 최단 경로 우선 프로토콜(OSPF)에 사용된다.
벨먼-포드(Bellman-Ford) 알고리즘
벨먼-포드의 알고리즘은 데이크스트라의 알고리즘과 비슷한 시기에 나왔으나, 데이크스트라의 알고리즘에 비하면 계산 횟수는 더 안 좋지만, 계산 과정과 전달 자체만은 비교적 간결한 형태를 띄고 있다. 인터넷에서 라우터가 라우팅을 할 때 사용되는 방법 중 하나인 라우팅 정보 프로토콜(RIP)에서 이 알고리즘을 사용하고 있다. OSPF에 비해서는 비교적 간결한 통신을 하지만, 순환 경로나 수신자가 메시지 도착 전에 가동 불능이 되는 경우에는 문제가 생길 수 있다는 단점이 있다.