C/C++

자료형

String

/* string 함수 구현 */
void mystrcpy(char *dst, const char *src) {
    while (*dst++ = *src++) ;
}

bool mystrcmp(char *a, char *b) {
    while (*a && *a == *b) {
        a++;
        b++;
    }
    return *a - *b;
}

자료구조

Hash & Hash Table

typedef struct _elem
{
    char name[MAXL];
    _elem *next = NULL;
} elem;

elem pool[MAXN];
elem hashTable[NBUCKET];

int hash(char* str) { return STH; }

void add(char* str) {
	strcpy(pool[i].name, str);
	int val = hash(str);
	pool[i].next = hashTable[val].next;
	hashTable[val].next = &pool[i];
}

elem *find(char *str) {
    int val = hash(str);
    elem *e = hashTable[val].next;

    while (e != NULL) {
        if (mystrcmp(e->name, str) == 0) { return e; }
        else { e = e->next; }
    }
    return NULL;
}

Linked List

typedef struct _elem {
    char c;
    _elem* prev = NULL; // nullptr error 주의
    _elem* next = NULL;
} elem;

정렬

Merge Sort

void merge_sort(int s, int e) {
    if(e - s < 2) { return; }

    int m = (s + e) / 2;
    merge_sort(s, m);
    merge_sort(m, e);

    short tmp[MAXN];
    int i = s, j = m, c = s;
    while ((i < m) && (j < e)) {
        if (numbers[i] <= numbers[j]) {
            tmp[c++] = numbers[i++];
        } else { // numbers[i] > numbers[j]
            tmp[c++] = numbers[j++];
        }
    }

    while (i < m) {
        tmp[c++] = numbers[i++];
    }
    while (j < e) {
        tmp[c++] = numbers[j++];
    }

    for (int i = s; i < e; i++) {
        numbers[i] = tmp[i];
    }
};

Quick Sort

void quick_sort(int s, int e)
{
    if(e - s < 2) { return; }

    int pivot = numbers[s];
    int low = s + 1, high = e - 1;
    while(low <= high) {
        if(numbers[low] < pivot) {
            low++;
        } else if(pivot <= numbers[high]) {
            high--;
        } else {
            int tmp = numbers[low];
            numbers[low] = numbers[high];
            numbers[high] = tmp;
            low++; high--;
        }
    }

    numbers[s] =  numbers[low - 1];
    numbers[low - 1] = pivot;

    quick_sort(s, low - 1);
    quick_sort(low, e);
};

Heap Sort

void heapify(int root, int size) {
    int left = root * 2 + 1, right = root * 2 + 2;

    int midx = root;
    if (left < size && numbers[left] > numbers[midx]) {
        midx = left;
    }
    if (right < size && numbers[right] > numbers[midx]) {
        midx = right;
    }

    if (midx != root) {
        swap(numbers[root], numbers[midx]);
        heapify(midx, size);
    }
}

void heap_sort(int size)
{
    /* build heap */
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i, size);
    }

    /* get value from heap */
    for(int i = 0; i < size; i++) {
        swap(numbers[0], numbers[size - i - 1]);
        heapify(0, size - i - 1);
    }
};

BFS

2개의 queue로 BFS 구현하기

    queue<int> q[2];
    int cur = 0, next = 1; // current queue: 0
    int dist = 1;

    /* initialize ... */
    
    while (!q[cur].empty())
    {
        while (!q[cur].empty())
        {
            int s = q[cur].front();
            q[cur].pop();

            int ns = getNextNode();
            q[next].push(ns);
        }

        dist++;
        cur = next;
        next = 1 - cur;
    }

DFS

위상 정렬

void dfs(int v) {
    stack<int> s;

    visited[v] = true;
    s.push(v);

    while(!s.empty()) {
        int cur = s.top();

        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i];

            if(!visited[next]) {
                visited[next] = true;
                s.push(next);
                break;
            }
        }

        if(cur == s.top()) {
            s.pop();
            order.push_back(cur);
        }
    }
}

최단거리 알고리즘

Dijkstra

	while(!pq.empty()) {
		info i = pq.top();
		pq.pop();

		int cur = i.city;

		if(visited[cur][i.pave]) { continue; }

		visited[cur][i.pave] = true;
		minDist[cur] = i.dist < minDist[cur] ? i.dist : minDist[cur];

		if(cur==N){ continue; } // reach goal

		list<pair<int, int>>::iterator it;
		for(it = graph[cur].begin(); it != graph[cur].end(); it++) {
			int next = it->first;
			int cost = it->second;
			
			if(i.pave > 0) {
				pq.push(info(i.dist, next, i.pave - 1));
			}

			pq.push(info(i.dist + cost, next, i.pave));
		}
	}

Bellman Ford

    for(int i = 0; i < N; i++) {
        set<int>::iterator sit;
        for(sit = target.begin(); sit != target.end(); sit++) {
            int cur = *sit;

            list<pair<int, int>>::iterator it;
            for(it = graph[cur].begin(); it != graph[cur].end(); it++) {
                int next = it->first;
                int t = it->second;

                if(dist[next] > dist[cur] + t) {
                    tmp.insert(next);
                    dist[next] = dist[cur] + t;
                }
            }
        }

        if(tmp.empty()) { return true; } // no update
        else {
            target = tmp;
            tmp = set<int>();
        }
    }

Floyd Warshall

void FloydWarshall() {
    for(int i = 1; i <= N; i++) { DP[i][i] = 0; }

    for(int k = 1; k <= N; k++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]);
            }
        }
    }
}