ETC/Data Struct | Algorithm
Array 탐색 시 빠르게 연속된 1 찾기(?)
1000000 크기의 배열이 주어지고, 그 배열 내에서 1이 드문 드문 연속된다고 가정합니다. 연속된 1을 카운트할 때 for() 또는 while() 반복문을 이용하여 count 값을 증가시키며 체크를 하는 방법도 있지만, 아래 코드와 같이 길이 8을 뛰어넘으면서 사용도 가능합니다. unsigned char map[1000000]; ... map_ptr = (unsigned long long*) & map[i]; while (*map_ptr == 72340172838076673 && i < 1000000) { *map_ptr = 144680345676153346; map_ptr++; ... // Do something } 위에서 72340172838076673 값은 0x0101010101010101 으로..
[Queue] Thread 간 통신을 위한 Async Queue (비동기 큐)
AsyncQueue라고 표현하면 뭔가 이해하기 쉽지 않습니다. AsyncQueue의 목적은 실제 Queue로 사용하기 보단 Multi-thread 환경에서 thread간 데이터 송수신을 위해 사용합니다. AsyncQueue에 대해 살펴보겠습니다. 저는 AsyncQueue를 pthread(mutex, cond) 기반으로 작성하였습니다. Header에 include되어 있는 다른 header와 source 파일은 아래 URL을 참고해주세요. https://github.com/linuxias/linux-system-programming/tree/master/DataStruct 아래 Header를 보시면 SAsyncQueue 구조체에 mutex, cond, SQueue (자체적으로 구현한 Queue) 등이 있습..
Priority Queue , 우선순위 큐
#include #define MAX_SIZE 100int heap[MAX_SIZE];int heapSize = 0;int heapPush(int value){if (heapSize > MAX_SIZE){printf("queue is full!");return 0;}heap[++heapSize] = value;int current = heapSize;while (current > 1 && heap[current]
Geometry
/** * @file geometru.c * @date 17.07.2017 * @author linuxias * @brief This code is for geometric API. */ typedef struct Point {int x;int y;} Point; int ccw(Point p, Point q){return p.x * q.y - q.x * p.y;} int ccw_with_point(Point r, Point p, Point q){Point rp = {p.x - r.x, p.y - r.y};Point rq = {q.x - r.x, q.y - r.y}; return ccw(rp, rq);} int is_left_turn(Point r, Point p, Point q){return ccw_wi..
[STL] algorithm 내부 sort 함수의 원형
Sort의 원형이다.한번 고민해 봐야 할 것 같다. 123456789101112131415161718192021222324252627282930313233void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred){ // order [_First, _Last), using _Pred _Diff _Count; for (; _ISORT_MAX
Graph - 인접 행렬 그래프
이번 시간에는 그래프 소스에 대해 알아본다.행렬을 이용하여 구현하는 방법과 리스트를 이용하여 구현하는 방법 2가지 인데,먼저 행렬을 이용하여 구현한 인접 행렬 그래프를 알아본다. 그래프의 관련 내용은 검색하면 금방 알아 볼 수 있기 때문에 여기서는 설명 하지 않는다. 먼저 인접행렬그래프의 헤더파일을 살펴보자. 1. arraygraph.h #ifndef _ARRAYGRAPH_H_#define _ARRAYGRAPH_H_ #define UNDIRECTION 0 //무방향 그래프#define DIRECTION 1 //방향 그래프#define SUCCESS 1 #define FAIL 0#define USE 1#define NOT_USE 0 typedef struct ArrayGraphType{ int maxVer..