차례
Recursive
달팽이 만들기
Pointer
상수포인터, 포인터 상수
함수 포인터
함수 포인터 배열
Sorting
Sorting Comparison
Insertion Sorting
Bubble Sorting
Shell Sorting
Selection Sorting
Quick Sorting
Merge Sorting
Heap Sorting
Radix Sorting
Bucket Sorting
Search
Linear Search
Binary Search
Binari Search Tree(BST)
Graph
Graph
Recursive
달팽이 만들기
 #include <windows.h>
#include <tchar.h>
#include <iostream>
#include <iomanip>
using namespace std;
int array[10][10];
void snail(int n, int direct)
{
static int value = 0, x = -1, y = 0;
if (0 == n) return;
for (int i=0; i<2*n-1; i++)
{
if (i < n) x += direct;
else y += direct;
array[y][x] = ++value;
}
snail(n-1, direct * (-1));
}
int _tmain(int argc, _TCHAR* argv[])
{
int size = 10;
snail(size, 1); //달팽이 생성
for (int i=0; i<size; i++) //출력
{
for (int j=0; j<size; j++)
cout << setw(4) << array[i][j];
cout << endl;
}
return 0;
}
|
Pointer
상수 포인터, 포인터 상수
const char* p = "hi"; //상수 포인터
p[0] = 'a'; //error //데이터 변경 불가
p = "aa"; //ok //포인터 변경 가능
char* const p = "hi"; //포인터 상수
p[0] = 'a'; //ok //데이터 변경 가능
p = "aa"; //error //포인터 변경 불가
const char* const p = "hi";
p[0] = 'a'; //error //데이터 변경 불가
p = "aa"; //error //포인터 변경 불가 |
#include <windows.h>
#include <tchar.h>
#include <iostream>
using namespace std;
int func(int a) { return ++a; }
int oper(int (*f)(int)) //함수 포인터 사용
{
return (*f)(1); //또는 return f(1);
}
int _tmain(int argc, _TCHAR* argv[])
{
int v = oper(&func);
cout << v << endl;
return 0;
}
|
함수 포인터 배열
#include <windows.h>
#include <tchar.h>
#include <iostream>
using namespace std;
int func1(int a) { return a+=1; }
int func2(int a) { return a+=2; }
int _tmain(int argc, _TCHAR* argv[])
{
int (*f[2])(int); //함수 포인터 배열
f[0] = func1;
f[1] = func2;
for (int i=0; i<2; i++)
cout << (*f[i])(1) << endl;
return 0;
}
|
Sorting
Sorting Comparison
 |
| 최악 | 평균 | 최고 | 추가공간 | 시간복잡도 | 비교횟수 | 카피횟수 | |
| Selection | O(n2) | O(n2) | O(n2) | N | O(n2) | ~n2/2 | ~2n |
| Insertion | O(n2) | O(n2) | O(n) | N | O(n2) | ~n2/4 | ~ n2/4 |
| Bubble | O(n2) | O(n2) | O(n) | N | O(n2) | ~n2/2 | ~ 3n2/2 |
| Shell | O(nlog2n) | 간격별 | O(n) | N | O(n1.25) | ~ a n | |
| Merge | O(nlogn) | O(nlogn) | O(nlogn) | Y | O(nlogn) | ~nlog2n | ~ 2nlog2n |
| Quick | O(n2) | O(nlogn) | O(nlogn) | Y | O(nlogn) : O(n2) | ~nlog2n|~n2/2 | ~ 2n/3log2n|0 |
| Heap | O(nlogn) | O(nlogn) | O(nlogn) | Y | |||
| Radix | O(dn) | Y | |||||
| Bucket | O(n2) | O(n2) | O(n2) | Y |
* radix의 d는 자릿수
설명 : 왼쪽에서 오른쪽으로 순서대로 왼쪽 값과 비교하면서 자리 이동
| #include <windows.h>
#include <tchar.h>
#include <iostream>
#include <iomanip>
using namespace std;
void print(int *arr, int len)
{
for(int i=0; i<len; i++)
cout << setw(3) << arr[i];
cout << endl;
}
void insertionSorting(int *arr, int len, bool isAscending)
{
for (int i=1; i<len; i++)
{
int tmp = arr[i];
int off = i - 1;
while (off >= 0 /*&& arr[off] > tmp //오름차순 */)
{
if (isAscending)
{
if (arr[off] < tmp) break; //오름차순
}
else
{
if (arr[off] > tmp) break; //내림차순
}
arr[off+1] = arr[off];
off--;
cout << setw(4) << " " << " "; print(arr, len);
}
arr[off+1] = tmp;
cout << setw(4) << i << "."; print(arr, len);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//오름차순
int arr[10] = {10,9,8,7,6,5,4,3,2,1};
int len = sizeof(arr)/sizeof(int);
cout << endl << endl;
insertionSorting(arr, len, true);
//내림차순
int arr2[10] = {1,2,3,4,5,6,7,8,9,10};
int len2 = sizeof(arr)/sizeof(int);
cout << endl << endl;
insertionSorting(arr2, len2, false);
return 0;
}
|
Bubble Sorting O(n^2)
설명 : 자리바꿈을 통한 정렬
| #include <windows.h>
#include <tchar.h>
#include <iostream>
#include <iomanip>
using namespace std;
void print(int *arr, int len)
{
for(int i=0; i<len; i++)
cout << setw(3) << arr[i];
cout << endl;
}
void swap(int&a , int &b)
{
int t = a;
a = b;
b = t;
}
void bubbleSorting(int *arr, int len, bool isAscending)
{
print(arr, len); cout << endl;
for (int i=len; i>1; i--)
{
for (int j=0; j<i-1; j++)
if (isAscending)
{
if (arr[j] > arr[j+1])
{
swap(arr[j], arr[j+1]);
print(arr, len);
}
}
else
{
if (arr[j] < arr[j+1])
{
swap(arr[j], arr[j+1]);
print(arr, len);
}
}
cout << endl;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10] = {10,9,8,7,6,5,4,3,2,1};
int len = sizeof(arr)/sizeof(int);
cout << "오름차순" << endl;
bubbleSorting(arr, len, true);
cout << endl << endl;
int arr2[10] = {1,2,3,4,5,6,7,8,9,10};
int len2 = sizeof(arr)/sizeof(int);
cout << "내림차순" << endl;
bubbleSorting(arr2, len2, false);
return 0;
}
|
Shell Sorting 평균 O(n^1.25), 최악 O(n^1.5)
설명 : 일정 거리(step size)가 있는 배열 요소에 대한 버블 정렬 수행하는 불완전 정렬
| 냉무... |
Selection Sorting O(n^2)
설명 : 처음부터 n까지의 최대값과 n값을 비교하여 swap하면서 정렬
| #include <windows.h>
#include <tchar.h>
#include <iostream>
#include <iomanip>
using namespace std;
void print(int *arr, int len)
{
for(int i=0; i<len; i++)
cout << setw(3) << arr[i];
cout << endl;
}
void selectionSorting(int *arr, int len, bool isAscending)
{
print(arr, len);
for (int i=len-1; i>0; i--)
{
int maxIdx = 0;
for (int j=1; j<=i; j++)
{
if (isAscending) //오름차순
{
if (arr[j] > arr[maxIdx]) maxIdx = j;
}
else //내림차순
{
if (arr[j] < arr[maxIdx]) maxIdx = j;
}
}
//swap
int tmp = arr[maxIdx];
arr[maxIdx] = arr[i];
arr[i] = tmp;
print(arr, len);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10] = {10,9,8,7,6,5,4,3,2,1};
int len = sizeof(arr)/sizeof(int);
cout << "오름차순" << endl;
selectionSorting(arr, len, true);
cout << endl << endl;
int arr2[10] = {1,2,3,4,5,6,7,8,9,10};
int len2 = sizeof(arr)/sizeof(int);
cout << "내림차순" << endl;
selectionSorting(arr2, len2, false);
return 0;
}
|
Quick Sorting O(nLog2 n), 최악 O(n^2)
설명 : 2부분으로 나누는 작업을 반복하며 정렬. pivot이 평균값일때 이상적(샘플은 0).
#include <windows.h>
#include <tchar.h>
#include <iostream>
#include <iomanip>
using namespace std;
void print(int *arr, int len)
{
for(int i=0; i<len; i++)
cout << setw(3) << arr[i];
cout << endl;
}
void quickSortingAscending(int *arr, int startpos, int endpos)
{
print(arr, 10);
if (startpos >= endpos) return;
int start = startpos, end = endpos;
int pivotVal = arr[start];
while (start < end)
{
while ((pivotVal < arr[end]) && (start < end)) end--; //끝에서 부터 pivotval 보다 작은 값
if (start != end)
{
arr[start] = arr[end]; //값 교환
start++; //다음 정렬
}
while ((pivotVal > arr[start]) && (start < end)) start++; //처음부터 pivotval보다 큰 값
if (start != end)
{
arr[end] = arr[start]; //값 교환
end--; //다음 정렬
}
}
arr[end] = pivotVal;
int pivotloc = end;
quickSortingAscending(arr, startpos, pivotloc-1);
quickSortingAscending(arr, pivotloc+1, endpos);
}
void quickSortingDesending(int *arr, int startpos, int endpos)
{
print(arr, 10);
if (startpos >= endpos) return;
int start = startpos, end = endpos;
int pivotVal = arr[start];
while (start < end)
{
while ((pivotVal > arr[end]) && (start < end)) end--; //끝에서 부터 pivotval 보다 큰 값
if (start != end)
{
arr[start] = arr[end]; //값 교환
start++; //다음 정렬
}
while ((pivotVal < arr[start]) && (start < end)) start++; //처음부터 pivotval보다 작은 값
if (start != end)
{
arr[end] = arr[start]; //값 교환
end--; //다음 정렬
}
}
arr[end] = pivotVal;
int pivotloc = end;
quickSortingDesending(arr, startpos, pivotloc-1);
quickSortingDesending(arr, pivotloc+1, endpos);
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "오름차순" << endl;
int arr[10] = {10,9,8,7,6,5,4,3,2,1};
quickSortingAscending(arr, 0, 9);
cout << endl << endl;
cout << "내림차순" << endl;
int arr2[10] = {1,2,3,4,5,6,7,8,9,10};
quickSortingDesending(arr2, 0, 9);
return 0;
}
|
Merge Sorting 최악 O(nLog2 n)
설명 : 구간을 나누어 정렬한 후 합치면서 정렬한다.
| #include <windows.h>
#include <tchar.h>
#include <iostream>
#include <iomanip>
using namespace std;
bool isAscending = true;
void print(int *arr, int len)
{
for(int i=0; i<len; i++)
cout << setw(3) << arr[i];
cout << endl;
}
void merge(int *arr, int low, int high)
{
int k=0;
int n=high-low+1; //개수
int mid=(low+high)/2; //중간 위치
int *b = new int[n]; //임시
for (int i=low; i<=mid; i++) //왼쪽 반을 복사
b[k++] = arr[i];
for (int i=high; i>=mid+1; i--) //오른쪽 반을 역으로 복사
b[k++] = arr[i];
int start = 0;
int end = n-1;
k = low;
if (isAscending)
{
while (start <= end)
{
if (b[start] <= b[end])
arr[k++] = b[start++];
else
arr[k++] = b[end--];
}
}
else
{
while (start <= end)
{
if (b[start] >= b[end])
arr[k++] = b[start++];
else
arr[k++] = b[end--];
}
}
print(arr, 10);
}
void mergeSortingAscending(int *arr, int low, int high)
{
if (low < high)
{
int mid = (low + high) / 2; //중앙 위치
mergeSortingAscending(arr, low, mid);
mergeSortingAscending(arr, mid+1, high);
merge(arr, low, high); //분할된 것을 merge
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "오름차순" << endl;
int arr[10] = {10,9,8,7,6,5,4,3,2,1};
print(arr, 10);
isAscending = true;
mergeSortingAscending(arr, 0, 9);
cout << endl << endl;
cout << "내림차순" << endl;
int arr2[10] = {1,2,3,4,5,6,7,8,9,10};
print(arr, 10);
isAscending = false;
mergeSortingAscending(arr2, 0, 9);
return 0;
}
|
Heap Sorting
설명 : subtree의 root 노드가 최대값을 갖는 complete binary tree를 heap 이라고 함.
"최대값인 root를 제거 > heap 재구성 > 최대값인 root 제거" 의 반복으로 정렬 수행.
Radix Sorting
설명 : 자릿수를 기준으로 정렬하며 큰자릿수부터 정렬을 시작한다.
Search
Linear Search
설명 : 처음부터 끝까지 순차적 검색
| for (int i=0; i<len; i++) { if (arr[i] == val) printf("찾았다"); } |
Binary Search
설명 : 정렬된 대상을 전제로 중앙 값과 비교하여
가까운 쪽에서 다시 중앙 값을 비교하며찾는다. (범위를 반씩 쪼개가며 찾기)
| #include <windows.h>
#include <tchar.h>
#include <iostream>
using namespace std;
int binarySearch(int *arr, int low, int high, int val)
{
if (low <= high)
{
int mid = (low + high) / 2;
if (val == arr[mid]) return mid;
else if (val < arr[mid]) return binarySearch(arr, low, mid-1, val);
else if (val > arr[mid]) return binarySearch(arr, mid+1, high, val);
}
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
cout << binarySearch(arr, 0, 9, 10) << "번째에 들어있음" << endl;
return 0;
}
|
Binary Search Tree (BST)
설명 : BST란 노드가 순서데로 정렬되어 있는 binary tree를 의미 (동의어 : ordered binary tree)
정렬 기준은 (왼쪽 노드 <= 오른쪽 노드) 이다.
Graph
Graph
설명 : 그래프 G는 하나 이상의 정점(vertex)들의 집합 V와 연결선(edge)들의 집합 E로 이루어진다. G=(V,E)
undirected graph(무방향 그래프)는 (v1, v2)또는 (v2, v1)으로 표현.
directed graph(방향 그래프:digraph)는 <v1, v2>로 표현하며 <v2, v1>과 다르다.
* graph를 메모리에서 표현하는 대표적인 방법 4 가지
Adjacency Matrix (인접 행렬)
Adjacency List (인접 리스트)
Inverse Adjacency List (역인접 리스트)
Adjacency Multi-List (인접 다중 리스트)
* graph 탐색
DFS (Depth First Search : 깊이 우선 검색)
BFS (Breadth First Search : 너비 우선 검색)
* spanning tree (신장 트리)
DFS나 BFS로 모든 vertex를 방문하면서 지나는 edge들로 연결된 트리
* spanning tree의 대표적인 찾기 알고리즘
- Kruskal's Minumum Spanning Tree Algorithm
- Prim's Minumum Spanning Tree Algorithm
* Shortest Path (최단 경로)
- Dijkstra Algorithm (다익스트라 알고리즘)
| |
'C++' 카테고리의 다른 글
| 윈도우 창을 모니터 화면 가운데로 이동하기 (0) | 2010.10.13 |
|---|---|
| Random 난수 생성하기 (0) | 2010.10.13 |
| SOCKET (0) | 2010.10.09 |
| Windows Thread 와 Synchronization(동기화) (0) | 2010.10.06 |
| VC++ 수행시간 체크 (1) | 2010.09.15 |
| IME(Input Method Editor) (0) | 2010.09.11 |
| Visual C++ : window 생성 template (0) | 2010.09.10 |
| C++ 포인터 및 레퍼런스 (0) | 2010.09.02 |