2008년 4월 19일 토요일
[기초]분할 정복
음.. 재귀와 함께 알고리즘에서 자주 보이는 분할 정복에 대해서
대충 써보면..
기본적인 컨셉은 큰 하나의 것을 작은 여러개로 분리해서 작은 것들을 전부 끝내고 그것을 합해서 하나로 만드는 것을 말하는 것이다.
이렇게 써 놓으면 뭐 씨뷁하는 생각밖에 들지 않을테고, 알고리즘 책에서도 자주 예를 드는 병합정렬을 예로 들어보면,(여기서는 간단하게 보여주기만 할 것이고, 알고리즘 폴더에 정확한 것을 써 놓을 것이다)
XXXXXXXXXXX 라는 배열을 정렬한다고 했을 때
1.XXXXX 2.XXXXXX 둘로 나누고
1.XX 2.XXX 1.XXX 2.XXX 둘로 나눈 것을 다시 둘로 나누고
1.X 2.X 1.X 2.XX 1.X 2.XX 1.X 2.XX 다시 둘로 나눠서
X X X X X X X X X X X 이렇게 각자 하나가 될 때까지 나누면 하나
의 원소는 정렬된 것이므로 이것들을 합하면서 정렬시키는 것이다.
그래서 저렇게 나눠진 것을 합해서 정렬된 배열이 나타나는데,
이런 식으로 큰 부분을 작게 나누고 작게 나눠진 부분에서 계산이나 실행을 끝내고 합하는 것을 분할 정복이라고 한다.
뭐 잘 이해가 안가는 설명이었는지도 모르겠지만, 나의 설명의 한계는 이정도이므로 여기서 끝낸다..
[기초]재귀
재귀는 말 그대로 자기 자신을 호출하는 것이다.
재귀를 설명할 때의 가장 간단한 프로그램은 역시 피보나치 수열이다.
피보나치 수열은 자기앞의 두 수의 합이 자신의 값이 되는 것이다. 그리고 자기 앞이 존재하지 않는 1, 2번째의 경우 1로 설정된다. 따라서 수열의 모양은 아래와 같다
1 1 2 3 5 8 13 21 34 55.....
이것을 함수로 나타낸다면
int fibo(int index)
{
if(index <= 0)
return 0;
if(index == 1 || index == 2)
return 1;
return fibo(index - 1) + fibo(index - 2);
}
같은 형식이 될 것이다.
재귀의 경우 전부 루프로 나타낼 수 있다고 한다.
c++에서 재귀함수의 문제점이라면
1. 함수이므로 스택이 쌓이면서 메모리 사용양이 증가한다.
2. 위와같은 이유로 느려진다.
[알고리즘]힙정렬
힙정렬이다.. 우선 소스를 보자.
// 깊이를 구하기위해서 값이 1이하가 될 때까지 쉬프트 연산을 해
// 주고
// 쉬프트 연산의 회수를 반환
int Lg2(int iVal)
{
int temp = 0;
while(iVal > 1)
{
++temp;
iVal >>= 1;
}
return temp;
}
// root인덱스가 추가되었을 때 힙을 재구성해주는 함수
// 좌우 자식중 큰 값을 부모와 비교하여 부모가 크다면 그대로 두
// 고
// 자식이 크다면 부모와 바꿔준다.
// 만약 부모와 자식을 바꾸었다면, 내려간 부모의 인덱스를 이용해
// 다시 자신을 호출한다.
// 여기서 root는 최대 iVec.size() >> 1 즉 배열 크기의 절반이므
// 로
// 최소한 왼쪽 자식은 존재한다.
void LocalHeapify(vector
{
int max; // 두 자식중 큰 값의 인덱스를 저장할 변수
int leftChild = root * 2; // 왼쪽 자식
int rightChild = root * 2 + 1; // 오른족 자식
// 두 자식중 큰값의 인덱스를 max에 저장
if(rightChild != iVec.size()) // 오른쪽 자식이 배열의 크기와 같다
//면
// 오른쪽 자식은 배열의 인덱스를 벗어난 것이다.
{
iVec[leftChild] > iVec[rightChild] ? max = leftChild : max = rightChild;
}else
{
max = leftChild;
}
// 만약 자식이 부모보다 크다면 두 값을 바꿔주고
// 내려간 부모의 인덱스를 이용해 재귀적으로 호출
if(iVec[max] > iVec[root])
{
SwapInt(iVec[max], iVec[root]);
if(max <= (iVec.size() >> 1))
{
LocalHeapify(iVec, max);
}
}
}
// 들어온 배열로 힙을 만들어주는 함수
// 마지막 원소의 인덱스를 2로 나눈 것부터 첫번째 원소까지
// LocalHeapify함수를 호출
// 마지막 원소의 인덱스를 2로 나눈 것이 자식을 가지는 가장 아래
// 의 가장 오른쪽 원소이기때문이다.
void MakeHeap(vector
{
int temp = (iVec.size() - 1) >> 1;
for(int i = temp; i > 0; --i)
{
LocalHeapify(iVec, i);
}
}
// 만들어진 힙을 사용해서 힙정렬을 수행하는 함수
// 루트를 마지막원소와 바꿔주는 연산을 계속하면서
// 바꿔준 뒤에 힙을 재구성하는 AcceleratedHeapify함수를 호출
void HSort(vector
{
int end = iVec.size() - 1;
while(end > 1)
{
SwapInt(iVec[1], iVec[end]);
AcceleratedHeapify(iVec, --end);
}
}
// 루트의 바뀐 값을 이용해 힙을 재구성 하는 함수
// 깊이의 절반만큼 자식들만 비교해서 내려간뒤
// 들어온 값이 자신의 부모보다 크다면 위로 올라가면서 제자릴 찾
//고 끝내고
// 들오온 값이 자신의 부보보다 작다면 다시 남은 깊이의 절반만큼
//내려간다.
// 만약 리프까지 내려오면 종료한다.
void AcceleratedHeapify(vector
{
// 값이 1개도 남지않았다면 종료
if(end < cur =" 1;">
//다.
int treeHeight = Lg2(end); // 정렬되지 않은 트리의 깊이를 구한
//다.
int currentHeight = 0; // 들어온 값이 내려온 깊이를 저장한다.
// 리프까지 내려갈때까지 루프를 돈다.
while(currentHeight <= treeHeight) { int move = (treeHeight - currentHeight) / 2 + 1; // 한번에 내려
//갈 깊이
for(int i = 0; i <>
//내려간다.
{
int leftChild = cur * 2;
int rightChild = cur * 2 + 1;
int max;
if(leftChild > end)
{
break;
}else if(rightChild > end)
{
max = leftChild;
}else if(iVec[leftChild] > iVec[rightChild])
{
max = leftChild;
}else
{
max = rightChild;
}
SwapInt(iVec[cur], iVec[max]);
cur = max;
}
int parent = cur / 2;
if(cur > 1 && iVec[cur] > iVec[parent]) // 만약 내려간 위치에
//서 부모가 자신보다 작다면
{
while(cur > 1 && iVec[cur] > iVec[parent]) // 정확한 위치를
//찾을 때까지 거슬러 올라간다.
{
SwapInt(iVec[cur], iVec[parent]);
cur = parent;
parent = cur / 2;
}
return; // 정확한 위치를 찾았으니 종료
}
currentHeight += move; // 내려간 위치의 깊이를 저장
}
}
주석때문에 보기가 엉망이다... 거기다 힙정렬의 변화형을 사용했기때문에 소스가 길어졌다.
이 소스도 아래의 퀵정렬과 마찬가지로 전에 만들었던 소스를 그냥 올린 것이다.
[알고리즘]퀵 정렬
아.. 간만에 쓴다.. 솔직히 버블이나 삽입같은거야 그냥 쉽게 쉽게 설명이 되는데 이분부터는 재귀씨가 들어가셔서 애로사항이 꽃필수도 있다.
우선 코드를 보면
void QuickSort(vector
{
if(first >= last) // 값이 1개만 들어오거나 안들어왔을 경우를 위한
//문장
return;
if((last - first) <>
//를 사용
InsertSort(iVec, first, last);
SwapInt(iVec[first], iVec[last]); // 처음 인덱스의 값을 마지막으
//로 보냄
// 굳이 보낼 필요는 없지만, 보내고 싶어서 보냄
int pbot = iVec[last]; // 처음 값을 인덱스로 결정
--last;
int f = first; // 피봇보다 작은 값의 범위를 나타내줄 변수
int l = last; // " 큰 "
while(f <= l) { while(iVec[f] <>= pbot) // 피봇보다 작은 값이 나올때까지 이동
{
--l;
}
if(f <>= l이면 파티션이 제 자리를 찾았으므로 swap하지않
//는다.
SwapInt(iVec[f], iVec[l]);
}
SwapInt(iVec[++last], iVec[f]); // 피봇값을 제자리로 위치 시킴
QuickSort(iVec,first, f - 1); // 피봇보다 작은 쪽 파티션을 다시 재
//귀적으로 호출
QuickSort(iVec,f + 1, last); // " 큰 "
}
아.. 예전에 만든 코드를 가져다 붙였더니 엉망이다..
가장먼저 보이는 것은 vector
알고리즘을 설명하면 정렬하려는 범위내에서 피봇을 하나 선택한 후 그 피봇보다 작은 것은 앞쪽에 크거나 같은 것은 뒤쪽에 놓는다. 이 과정이 끝나면 피봇값은 정확한 위치에 놓이게된다.
그 다음 자신보다 작은부분과 큰부분에 다시 위의 것을 적용한다.
이것이 기본적인 컨셉이다.
이것을 구현하는 방식이 책이나 문서마다 조금씩 다른 경우가 있는데, 큰 차이는 없다. 위의 코드에서 사용한 방식을 보면
3 5 6 1 6 8 9 // 시작값
9 5 6 1 6 8 3 // 처음 값을 피봇으로 선택후 맨 뒤와 교체
f l p //p는 피봇값 f,l은 인덱스를 가리키는것으로 뒤에설명
9 5 6 1 6 8 3 // 앞쪽부터 피봇값보다 크거나 같은값이 올때까지 f를
f l p //이동
// 이동이 없다.
9 5 6 1 6 8 3 // 뒤쪽부터 피봇값보다 작은 값이 올 때까지 l을 이동
f l p// 1까지 이동
1 5 6 9 6 8 3 // f <>
f l p // 교체
// f > l이라면 끝낸다
1 5 6 9 6 8 3 // 다시 f를 이동
f l p // 5까지 이동
1 5 6 9 6 8 3 // l을 이동
l f // 1까지 이동
// f > l 이므로 현재 단계를 끝낸다.
1 3 6 9 6 8 5 // 피봇값과 f를 교체
l p f // 교체
// 피봇값의 앞 뒤로 다시 알고리즘을 실행한다.
// 앞쪽은 1 하나로 종료
// 위에 설명했으므로 바뀌는 순서만 표시
6 9 6 8 5
5 9 6 8 6
5 6 6 8 9 // 피봇값은 두번째
// 앞쪽은 5 하나로 종료
6 8 9
9 8 6
6 8 9 // 피봇값은 첫번째
8 9
8 9
// 결과
1 3 5 6 6 8 9
알고리즘은 이런 식 이지만, 자료가 일정 수 이하일 경우
퀵정렬이 삽입정렬보다 정렬 시간이 더 걸리게 되므로
현재 정렬해야하는 원소의 수를 세어서 위의 코드의 경우 10개 미만이라면 삽입 정렬을 사용한다.
위의 예에서는 단지 퀵정렬이 이루어지는 방식을 보여주는 것으로
저정도 숫자라면 삽입 정렬을 사용한다
[알고리즘]버블 정렬
이번에도 기초적인 것으로 버블 정렬이다.
우선 소스를 보면
bubbleSort(int array[], int arrayNum)
{
for(int i = arrayNum - 2; i >=0; --i)
{
for(int j = 0; j <= i; ++j)
{
if(array[j] > array[j+1])
{
array[j] += array[j+1];
array[j+1] = array[j] - array[j+1];
array[j] = array[j] - array[j+1];
}
}
}
}
알고리즘을 설명하면
버블 정렬은 배열의 끝으로 최대값을 보내고
최대값이 들어간 부분은 제외하고 다시 최대값을 끝으로
보내는 것을 반복하는 것이다.
예를 들면,
4 10 3 6 2 라는 배열이 주어진다면
4& 10 3 6 2 // 초기값
// &앞과 뒤의 값을 비교해서 큰 수를 뒤로보냄
4 10& 3 6 2 // 먼저 나온 for문의 첫번째 루프
4 3 10& 6 2
4 3 6 10& 2
4 &3 6 2 *10 // 별표 이후는 고정값
3 4 &6 2 *10 // 두번째 루프
3 4 6 &2 *10
3 &4 2 *6 10
3 4 &2 *6 10 // 세번째 루프
3 &2 *4 6 10
2 *3 4 6 10 // 네번재 루프
이번에는 예가 긴데, 버블정렬은 삽입정렬과는 달리 항상 n(n-1)/2
번의 연산을 해야하기 때문이다.
버블정렬은 가장 큰 수가 맨 뒤로 가는 구조로 마치 물방울이 떠오르는 것처럼 보여서 '버블' 정렬이라고 부른다
[알고리즘]삽입정렬
우선 알고리즘의 기초라고 할 수 있는 삽입정렬
insertSort(int array[], int arrayNum)
{
int temp;
for(int i = 1; i <>
{
temp = i;
while(array[temp] <>= 0)
{
array[temp] += array[temp-1];
array[temp-1] = array[temp] - array[temp-1];
array[temp] = array[temp] - array[temp-1];
--temp;
}
}
}
이건 슈도코드가 아니라 c++ 코드로 만든 것으로
돌아가는지는 확인해봤음
알고리즘에 관한 간단한 설명이라면
우선 while문 부터 설명하면
정렬할 숫자(array[i])의 앞부분은 정렬이 되어있다는 가정하에
바로 앞의 숫자와 비교해봐서 자신이 작다면 교환한뒤
다시 앞의 숫자와 비교하는 것을
맨 앞까지 가거나 앞의 숫자가 자신보다 작거나 같다면
끝나는 구조로 되어있다.
for문이 1부터 시작하는 것은 1개의 값은
항상 정렬되어있기 때문이다.
나의 특유의 이해하기 힘든 설명으로
위의 글은 거의 알아먹기 힘들테니 예를 들어보면,
입력이 10, 4, 5, 2, 8 이라면
우선 i = 1이니 4부터 시작
10* 4 5 2 8 // 시작부분
4 10* 5 2 8 // i = 1
4 5 10* 2 8 // i = 2
4 5 2 10 8 // i = 3
4 2 5 10 8 // i = 3
2 4 5 10* 8 // i = 3
2 4 5 8 10* // i = 4 끝
위에서 별표를 한 곳 앞쪽은 정렬이 되어있다.
바로 뒤의 것을 정렬이 되어있는 부분에 '삽입' 하기때문에
삽입정렬이라고 하는 것이다.
어쨋든 설명을 잘 하지는 않았지만 나로서는 이것이 한계로
더 이상의 설명은 관두기로..