본문 바로가기
반응형

알고리즘7

[알고리즘] sort sort c++ sort 예제 algorithm 헤더에 sort를 지원하고 있으며 아래와 같이 사용할 수 있다. 아래와 같이 기본적으로 사용할 경우에는 오름차순 정렬을 한다. c에서는 qsort를 제공하고 있으며 배열을 기반으로 설계 된 함수이기 때문에 사용성이 떨어진다. c++의 sort의 경우 연속된 컨테이너는 모두 정렬이 가능하며 수행시간도 qsort보다 빠르다. sort의 세번째 parameter인 compare에 greater, less으로 오름차순(기본), 내림차순으로 정렬이 가능하며, compare 함수를 구현하여 사용할 수 있다. #include #include using namespace std; int arr[100]; int n; void input() { cin >> n; for(i.. 2018. 10. 20.
[알고리즘] DFS 경로찾기 DFS 경로찾기 (백준 11403번) n: 정점의 개수 모든 정점(i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구분. 방향이 있는 간선에 대한 문제를 풀기위해서는 destination을 기준으로 도달이 가능한지를 확인이 필요하며, 방문을 확인하기 위해 2차원 배열을 사용. 기존 DFS 알고리즘의 확인하는 부분은 동일하게 사용. 예제 3 0 1 0 0 0 1 1 0 0 #include #include using namespace std; bool graph[101][101]; bool visit[101][101]; int n; void input() { cin >> n; for(int i=0; i graph[i][j]; } void output() { for(int i=0; i 2018. 10. 20.
[알고리즘] BFS BFS(Breadth First Search) 너비우선탐색을 예제를 통해 알아본다. queue를 사용하며 FIFO의 특징을 가지고 있으므로, push된 순서대로 front 값을 얻을 수 있다. 예제. 4 5 1 1 2 1 3 1 4 2 4 3 4 결과: 1 2 3 4 c언어. bool map[1001][1001]; bool visit[1001]; bool queue[1001]; int front, rear; int n;//정점개수 int m;//간선개수 int v;//시작정점 void input(void) { scanf("%d%d%d", &n, &m, &v); for(int i=1; i n >> m >> v; for(int i=1; i> x >> y; graph[x][y] = graph[y][x] = 1.. 2018. 10. 17.
[알고리즘] DFS DFS (Depth First Search) 깊이우선 탐색을 예제를 통해 알아본다. 예제 1 4 5 1 2 1 3 1 4 2 4 3 4 결과: 1 2 4 3 map 상태 map[x][y] 0 1 2 3 4 0 1 (시작) 1 1 1 2 1 1 3 1 1 4 1 1 1 DFS 탐색 경로 map[x][y] 0 1 2 3 4 0 1 (시작) 1 (2 찾음) 2 (두번째 탐색) 1 (4 찾음) 3 (마지막) 4 (세번째 탐색) 1 (3 찾음) #include #include bool map[1001][1001]; bool visit[1001]; int n;//정점개수 int m;//간선개수 int v;//시작정점 void input(void) { scanf("%d%d%d", &n, &m, &v); for(int.. 2018. 8. 31.
[알고리즘] 쿼드트리 (Quad Tree) 쿼드트리 (Quad Tree) 8x8 quad tree를 압축하는 경우 아래와 같이된다. Flow는 아래와 같다. S(Size) Start X:0, Y:0 S:8 -> x:0, y:4 break, "(" 출력 Q1 X:0, Y:0 S:4 -> x:2, y:0 break, "(" 출력 Q1 X:0, Y:0 S:2 -> return, 1 출력 Q2 X:2 Y:0 S:2 -> return, 1 출력 Q3 X:0 Y:2 S:2 -> return, 0 출력 Q4 X:2 Y:2 S:2 -> x:2 y:3 break, "(" 출력 Q1 X:2 Y:2 S:1 -> return, 0 출력 Q2 X:3 Y:2 S:1 -> return, 1 출력 Q3 X:2 Y:3 S:1 -> return, 0 출력 Q4 X:3 Y:3 S.. 2018. 7. 31.
[알고리즘] 계수 정렬(Counting sort) 계수 정렬(Counting sort) #include #include #define MAX_NUMBER 10000 int main() { int maxnum =0, i = 0; int *arr = NULL, *sort = NULL, *cnt = NULL; scanf("%d", &maxnum); arr = (int*)calloc(maxnum, sizeof(int)); sort = (int*)calloc(maxnum+1, sizeof(int)); cnt = (int*)calloc(MAX_NUMBER, sizeof(int)); //입력. for(i=0; i 2018. 6. 11.
[알고리즘] 퀵 정렬(Quick sort) 퀵 정렬(Quick sort) quick 정렬의 source code이다. C에서 기본으로 제공하는 qsort는 아래와 같은 원리도 동작한다. #include #include void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } int quickSort(int* arr, int left, int right) { int L = left, R = right; int pivot = arr[(left + right)/2]; do { while( arr[L] pivot ) R--; if( L 2018. 5. 14.
728x90
반응형

티스토리툴바