'Tech Stack/algorithms'에 해당되는 글 20건

 [ 1 ]  [ 2 ] 
Tech Stack/algorithms

More on Graph algorithms

1. 최소 스패닝 트리


1) 프림 알고리즘



현재 MST에 속해 있는 점에서 가장 작은 가중치의 엣지와 노드를 추가한다.

계속 추가해 나간다.

끗.


정당성 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>
#include <unordered_map>
 
using namespace std;
 
int main() {
    // get inputs and make graph
    int nodes;
    int edges;
    scanf("%d %d"&nodes, &edges);
    unordered_map<intint> locator;
    vector < vector<pair<intint>>> graph(nodes, vector < pair<intint>>());
    int numbering = 0;
    for (int i = 0; i < edges; i++) {
        int from;
        int to;
        int weight;
        scanf("%d %d %d"&from, &to, &weight);
        auto it = locator.find(from);
        if (it != locator.end()) {
            from = it->second;
        }
        else {
            locator.insert(pair<intint>(from, numbering));
            from = numbering;
            numbering++;
        }
        it = locator.find(to);
        if (it != locator.end()) {
            to = it->second;
        }
        else {
            locator.insert(pair<intint>(to, numbering));
            to = numbering;
            numbering++;
        }
        graph[from].push_back(pair<intint>(to, weight));
        graph[to].push_back(pair<intint>(from, weight));
    }
 
    // do prim mst
    vector<int> included(nodes, 0);
    priority_queue < pair<intpair<intint>>vector<pair<intpair<intint>>>, greater<pair<intpair<intint>>>> queue;
    vector<pair<intint>> total;
    long long sum = 0LL;
 
    for (int k = 0; k < nodes; k++) {
        if (included[k] == 0) {
            included[k] = 1;
            for (int i = 0; i < graph[k].size(); i++) {
                queue.push(pair<intpair<intint>>(graph[k][i].second, pair<intint>(k, graph[k][i].first)));
            }
 
            // go through all candidates
            while (queue.size() != 0) {
                pair<intpair<intint>> curr = queue.top();
                queue.pop();
                if (included[curr.second.second] == 0) {
                    included[curr.second.second] = 1;
                    total.push_back(pair<intint>(curr.second.first, curr.second.second));
                    sum += curr.first;
                    for (int i = 0; i < graph[curr.second.second].size(); i++) {
                        if(included[graph[curr.second.second][i].first]==0)
                            queue.push(pair<intpair<intint>>(graph[curr.second.second][i].second, pair<intint>(curr.second.second, graph[curr.second.second][i].first)));
                    }
                }
            }
        }
    }
    cout << sum << endl;
}
cs


시간 복잡도 : O(ElogE ~ ElogV)

공간 복잡도 : O(V+E)


2. 최단 경로 알고리즘


1) 다익스트라


출발점을 0으로 두고 주변 엣지를 min heap에 저장. 가장 작은 weight부터 하나씩 확장하면서 해당 node의 값을 업데이트하고, 그 edge를 전부 min heap에 추가하면서 진행한다. node의 weight가 작아지는 경우에만 다시 업데이트한다.


2) 플로이드 - 워셜


3) 벨만 - 포드





3. Strongly connected components


[알고리즘]


DFS의 종료 순서대로 스택에 담는다.

역방향 그래프를 생성한다.

스택의 순서대로 역방향 그래프를 DFS로 순회한다.

각 DFS 조각이 SCC 조각이다.


정당성 :


코드 :  https://github.com/fw93/Personal_Projects/tree/master/School/Algorithm%20HW/HW3


시간 복잡도 : O(V+E)



'Tech Stack > algorithms' 카테고리의 다른 글

More on Graph algorithms  (0) 2018.06.03
정수 알고리즘들  (0) 2018.04.18
그래프 응용  (0) 2018.04.16
심화과정  (0) 2018.04.15
Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
Tech Stack/algorithms

정수 알고리즘들

최대공약수 ( Greatest common divisor ) 구하기

최소공배수 ( Least Common Multiplicator )


1
2
3
4
5
6
7
8
9
int GCD(int a, int b) {
    if (a == b) return a;
    if (a > b) return GCD(a - b, b);
    else return GCD(a, b - a);
}
 
int LCM(int a, int b) {
    return (a*b) / GCD(a, b);
}
cs

----------

소인수 분해 하기 ( Prime Factorization )
- 시간 복잡도는 O(sqrt(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void primefactors(int n) {
    // 2를 전부 제거해서 홀수를 만든다.
    while (n % 2 == 0) {
        cout << 2 << " ";
        n /= 2;
    }
    // 남은 것을 3 ~ 루트n까지 하나씩 나눠본다. 여러개일 수도
    // 있으니 전부 나눠 본다.
    for (int i = 3; i*<= n; i = i + 2) {
        while (n%i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
 
    // 소수라면 아직 나눠지지 않은 상태이다.
    if (n > 2) {
        cout << n;
    }
 
    cout << endl;
}
cs

** preprocessing을 이용한 log(N) 시간에 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve()
{
    spf[1= 1;
    for (int i=2; i<MAXN; i++)
 
        // marking smallest prime factor for every
        // number to be itself.
        spf[i] = i;
 
    // separately marking spf for every even
    // number as 2
    for (int i=4; i<MAXN; i+=2)
        spf[i] = 2;
 
    for (int i=3; i*i<MAXN; i++)
    {
        // checking if i is prime
        if (spf[i] == i)
        {
            // marking SPF for all numbers divisible by i
            for (int j=i*i; j<MAXN; j+=i)
 
                // marking spf[j] if it is not 
                // previously marked
                if (spf[j]==j)
                    spf[j] = i;
        }
    }
}
 
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x)
{
    vector<int> ret;
    while (x != 1)
    {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}
cs

----------

소수 구하기 ( 에라토스테네스의 체 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<bool> primes(int n) {
    vector<bool> isprime(n + 1, true);
    
    // 2에서부터 하나씩 트루인 것들의 배수를 싹 지운다.
    for (int i = 2; i * i <= n; i++) {
        if (isprime[i] == true) {
            for (int j = i * 2; j <= n; j++) {
                isprime[j] = false;
            }
        }
    }
 
    // 남는게 답.
    return isprime;
}
cs

----------

나뉘는지 아는 방법

2 : 끝자리가 2로 나뉜다

3 : 모든 자릿수의 합이 3으로 나뉜다.

4 : 끝 두자리가 4로 나뉜다

5: 끝자리가 5나 0이다.

6 : 2로 나뉘고 3으로 나뉜다.

7 : 끝자리를 두배 해서 나머지 자릿수 숫자에서 뺀다. 적당히 적어질 떄 까지 재귀적으로 반복한다.

8 : 끝 세자리가 8로 나뉜다.

9 : 자릿수의 합이 9의 배수다.


------------



'Tech Stack > algorithms' 카테고리의 다른 글

More on Graph algorithms  (0) 2018.06.03
정수 알고리즘들  (0) 2018.04.18
그래프 응용  (0) 2018.04.16
심화과정  (0) 2018.04.15
Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
Tech Stack/algorithms

그래프 응용

그래프의 표현방법


행렬 방법 : 삭제 등을 하는 경우에 사용한다.

vector<vector<int>> graph(32,vector<int>(32,0));

** 간선의 갯수가 아니라 간선에 weight 나 string 등의 특성이 담긴 경우

vector<vector<vector<string>>> graph

>> i->j로 가는 간선의 목록이 vector<string>으로 저장. 각 간선은 string을 가진다.

* vector<vector<int>> adj 와 vector<vector<vector<string>>> graph로 두개의 그래프를 만든 다음에, adj로 지우면서 순회하고 graph로 간선을 짜맞추면 직접 그래프를 순회하는 바람에 간선 정보를 삭제해야 하는 번거로움과 시간 낭비를 없앨 수 있다!!


리스트 방법: 검색의 숫자가 훨신 적어져서 빠르다.

vector<vector<int>> graph(10,vector<int>());

** 간선에 내용이 추가되는 경우

vector<vector<pair<int,int>> graph

>> i->j로 가는 간선에 int 변수가 존재. 간선이 여러 개인 경우에는 리스트 자체에 여러번 push_back 해야한다


--------------



그래프 컴포넌트의 갯수 세기 : 각 정점에서 DFS 해가면서 처음에 시작하는 것들을 센다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void DFS(vector<vector<int>> & graph, vector<bool> & visited, int target) {
    if (visited[target] == false) visited[target] = true;
    cout << "visiting " << target << endl;
    for (int i = 0; i < graph[target].size(); i++) {
        if (visited[graph[target][i]] == false) DFS(graph, visited, graph[target][i]);
    }
}
 
int findcomponents(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    int count = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == false) {
            count++;
            DFS(graph, visited, i);
        }
    }
    return count;
}
cs

----------


두 정점의 연결 확인하기

한 점에서 DFS를 부른 후에 다른 점을 방문하는지 확인한다.

1
2
3
4
5
bool connected(vector<vector<int>> & graph, int i, int j) {
    vector<bool> visited(graph.size(), false);
    DFS(graph, visited, i);
    return visited[j];
}
cs

---------

위상 정렬(비사이클 방향 그래프 - DAG 에서)

: DFSall(for루프로 dfs 전체 돌리는 상위함수) 로 DFS를 부르면서 DFS가 "종료" 하는 순서를 기록한 후에 그것을 뒤집는다!!

증명 - 종료하는 순서를 뒤집었다고 해보자. 이때 더 뒷쪽에 있는 u에서 앞에 있는 v로 간선이 있다고 가정해 보자. u가 더 뒷쪽에 있으므로 v보다 종료를 먼저 했겠지?
이때 visited[v] 가 거짓인 경우에는 u가 v를 불렀을 꺼기 때문에 v가 u 이전에 종료하지 못한다 >> u에서 v로 가는 간선은 존재할 수 없다.
visited[v]가 참이었을 경우에는 u가 v를 불렀을 텐데, v가 종료를 더 늦게 했는데도 이미 방문되어 있다는 점은 v가 u를 호출하게 된다는 뜻이다(v를 방문했는데, u가 살아있고, 먼저 일하고, 죽는 동안 v가 살아있어야 하므로 결국에는 v가 어떤 식으로든 u를 부른 것!!)
그말인 즉슨 v에서 u로 가는 간선이 존재한다는 뜻인데, u에서 v로 가는 간선도 존재한다고 가정했으므로 순환 사이클이 발생하게 되어 우리가 처음 가정한 비사이클 그래프의 가정에 모순된다.

** 따라서 DFS가 종료된 순서를 뒤집은 배열은 역방향 간선이 없는 topological sort이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void tDFS(vector<vector<int>> & graph, vector<bool> & visited, int target, stack<int> & buffer) {
    if (visited[target] == false) visited[target] = true;
    for (int i = 0; i < graph[target].size(); i++) {
        if (visited[graph[target][i]] == false) {
            tDFS(graph, visited, graph[target][i], buffer);
        }
    }
    buffer.push(target);
}
 
void topologicalsort(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> buffer;
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == false) {
            tDFS(graph, visited, i, buffer);
        }
    }
    // print stack
    while (buffer.size() != 0) {
        cout << buffer.top() << " ";
        buffer.pop();
    }
    cout << endl;
}
cs

---------

사이클 존재 확인하기

방향 사이클 : 한 점에서 시작하는 DFS에 대해 모든 점을 기록해 가면서 사이클을 돌린다. 돌다가 기록된 점을 만나면 당첨. 그 점을 다 끝내고 아예 다른 폴션으로 이동할 때에 기록을 삭제해야 한다!( 아 삭제 안해도 상관 없네. 어짜피 방문 안할테니까. 그냥 기록하면서 돌자 ).

비방향 사이클 : 시작점 관계없이 DFS가 불린 부모를 제외한 다른 "visited == true" 점이 adjacent으로 있으면 사이클이 존재한다.
왜냐면, 사이클이 없다는 뜻은 그런 점이 존재하지 않는다는 뜻이고 사이클이 존재하면 그런 점을 반드시 만나게 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
bool iscycle(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> buffer;
    unordered_set<int> contains;
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == false) {
            buffer.push(i);
            contains.insert(i);
            while (buffer.size() != 0) {
                int curr = buffer.top();
                if (visited[curr] == false) visited[curr] = true;
                buffer.pop();
                // go through adjacent elements
                for (int j = 0; j < graph[curr].size(); j++) {
                    // check if element is in track. if so, return true
                    // because the element comes from there to here then
                    // here to there making a cycle
                    if (contains.find(graph[curr][j]) != contains.end()) {
                        cout << i << " " << curr << " " << graph[curr][j] << endl;
                        return true;
                    }
                    if (visited[graph[curr][j]] == false) {
                        buffer.push(graph[curr][j]);
                        contains.insert(graph[curr][j]);
                    }
                }
            }
            contains.clear();
        }
    }
    return false;
}
 
bool cDFS(vector<vector<int>> & graph, vector<bool> & visited, int target, int parent) {
    visited[target] = true;
    // go to adjacent nodes. if visited and not parent, return true
    bool ret = false;
    for (int i = 0; i < graph[target].size(); i++) {
        // self cycle also considered cycle here.
        // if not wanted, do graph[target][i]!=target here
        if (visited[graph[target][i]] == true && graph[target][i] != parent&&parent != -1) {
            cout << "found at " << target << " " << parent << " " << graph[target][i] << endl;
            return true;
        }
        if (visited[graph[target][i]] == false) {
            ret |= cDFS(graph, visited, graph[target][i], target);
        }
    }
    return ret;
}
 
bool iscycle2(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    // start from every unvisited cycle
    for (int i = 0; i < graph.size(); i++) {
        bool ret;
        if (visited[i] == false)
            ret = cDFS(graph, visited, i, -1);
        if (ret == true) return true;
    }
}
cs


---------------

오일러 서킷 : u 에서 u로 모든 Edge를 지난 후에 돌아오는 경로
오일러 트레일 : u 에서 다른 v로 모든 Edge를 지난 후에 가는 경로

                비방향 그래프                             방향 그래프
오일러 서킷           모든 node의 edge가 짝수개                  모든 node의 inbound = outbound edges
오일러 트레일   u와 v는 홀수 개, 나머지는 edge가 짝수개           u는 outbound가 한개 더, v는 inbound가 한개 더

해당 서킷/트레일이 존재하기 위한 필요충분조건이다.

무향 그래프의 오일러 서킷 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void getEuler(int here, vector<int> & res, vector<vector<int>> & graph){
    for(int there = 0 ; there < graph[0].size() ; there++){
        while(graph[here][there]>0){
            graph[here][there]--;
            graph[there][here]--;
            getEuler(there,res,graph);
        }
    }
    res.push_back(here);
}
 
void getEuler2(int here, vector<int> & res, vector<vector<int>> & graph){
    for(int there = 0 ; there < graph[0].size() ; there++){
        while(graph[here][there]>0){
            graph[here][there]--;
            getEuler2(there,circuit);
        }
    }
    res.push_back(here);
}
 
 
cs

** 알고리즘 특성상 트레일 조건이건 서킷 조건이건 그냥 돌리면 구해준다. 엣지 추가하지 말것. 그게 마지막 점이라는 보장 절대 없다. **

방향 그래프의 오일러 서킷 존재성은 함수를 돌린 결과를 분석해도 되지만, 그래프 만드는 과정에서 inbound[n] 과 outbount[n]을 만들어서 트래킹 하면 매우 빠르다.

TODO : 종만책 예제 풀기, 트레일 서킷 변환시 그 구간이 양끝에 항상 존재하는지 확인하기

---------------

양방향 BFS(최단거리)

양쪽 끝에서 동시에 큐를 이용한 BFS를 시작해서 중간에 서로가 visit 한 점을 만나면 값을 더하고 종결한다. 순회할 때에 같은 거리의 값들을 순서대로 순회하므로 처음으로 만나는 경우 그 점이 곧 양쪽의 최단 거리이고 전체의 최단 거리이다. 큐가 비면 그 섹션을 전부 순회했다는 뜻이므로 서로 만나지 못하는 것이다.

*** 보드에 같은 것을 칠하는 여러 점에서의 최단거리 구하기나 painter problem 같은거는 그냥 그 모든 시작점을 enqueue 해버리고 BFS 하면 된다!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int distance(vector<vector<int>> & graph, int i, int j) {
    vector<int> dist(graph.size(), -1);
    vector<bool> visitedi(graph.size(), false);
    vector<bool> visitedj(graph.size(), false);
    dist[i] = 0;
    dist[j] = 0;
    queue<int> iq;
    queue<int> jq;
    iq.push(i);
    jq.push(j);
    while (iq.size() != 0 && jq.size() != 0) {
        int curri = iq.front();
        int currj = jq.front();
        iq.pop();
        jq.pop();
        // do left
        for (int i = 0; i < graph[curri].size(); i++) {
            if (visitedj[graph[curri][i]] == true) {
                // two BFS met
                return dist[curri] + dist[graph[curri][i]]+1;
            }
            else if(visitedi[graph[curri][i]]==false){
                // mark adjacent nodes and enqueue
                dist[graph[curri][i]] = dist[curri] + 1;
                visitedi[graph[curri][i]] = true;
                iq.push(graph[curri][i]);
            }
        }
        // do right
        for (int i = 0; i < graph[currj].size(); i++) {
            if (visitedi[graph[currj][i]] == true) {
                // two BFS met
                return dist[currj] + dist[graph[currj][i]]+1;
            }
            else if (visitedj[graph[currj][i]] == false) {
                // mark adjacent nodes and enqueue
                dist[graph[currj][i]] = dist[currj] + 1;
                visitedj[graph[currj][i]] = true;
                jq.push(graph[currj][i]);
            }
        }
    }
    // not met
    return 99999;
}
cs

---------------

최단 경로 알고리즘(다익스트라)

우선순위 큐를 사용해서 가장 가까운 거리의 노드부터 큐에서 pop 하고, 인접 노드 중에 top의 거리 + 엣지보다 거리 긴 놈 있으면 top의 거리 + 엣지로 거리 업데이트 해준다.
주의사항은 graph의 first는 원소번호고 priority_queue는 (거리,원소번호) 로 되어있어서 first second 잘 쓰자.

시간 복잡도 : O(ElogE) - 최단 경로인 경우 엣지마다 우선순위 큐에 들어갈 수 있어 고려되는 것이 E, 각 경우에 대해 우선순위 큐에 push pop 동작이 log E

정당성 증명 : 만약에 최단 거리가 아닌 노드 u가 존재한다고 하면, 지금까지 방문했던 원소들의 경로가 아닌 다른 경로로 u에 도착하는 것이 더 빠른 경로라는 뜻이다. 그런데, 그렇다는 것은 우선순위 힙에서 u를 부르지 않고 그 최단거리 경로를 우선순위 힙으로 쭉쭉 불러냈을 것이기 때문에 모순이다. 따라서, 우선순위 힙이 u를 불러냈다는 뜻은 그 경로가 최단 경로라는 뜻이다.

*&* 최단 경로를 구하고 싶으면 노드들을 역추적하면 된다. 같은 값이 있을 수 있으므로 재귀적으로 ^^7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> dijkstra(vector<vector<pair<int, int>>>&graph, int i) {
    vector<int> dir(graph.size(), INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    dir[i] = 0;
    q.push(pair<int, int>(0,i));
    while (q.size() != 0) {
        if (dir[q.top().second] < q.top().first) { 
            q.pop(); 
            continue; 
        }
        int curr = q.top().second;
        int cdis = q.top().first;
        q.pop();
        for (int i = 0; i < graph[curr].size(); i++) {
            if (dir[graph[curr][i].first] > cdis + graph[curr][i].second){
                dir[graph[curr][i].first] = cdis + graph[curr][i].second;
                q.push(pair<int, int>(dir[graph[curr][i].first], graph[curr][i].first));
            }
        }
    }
    return dir;
}
cs

* dijkstra with path tracing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<pair<int,vector<int>>> dijkstra(vector<vector<pair<int, int>>> & graph, int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<pair<int,vector<int>>> dist(graph.size(), pair<int,vector<int>>(INT_MAX,vector<int>()));
    dist[start].first = 0;
    dist[start].second.push_back(start);
    q.push(pair<int, int>(dist[start].first, start));
    while (q.size() != 0) {
        auto it = q.top();
        int currd = it.first;
        int curr = it.second;
        q.pop();
        if (currd > dist[curr].first) continue;
        // update adjacent elements
        for (int i = 0; i < graph[curr].size(); i++) {
            int newdist = currd + graph[curr][i].second;
            if (dist[graph[curr][i].first].first > newdist ) {
                dist[graph[curr][i].first].first = newdist;
                vector<int> tmp = dist[curr].second;
                tmp.push_back(graph[curr][i].first);
                dist[graph[curr][i].first].second=tmp;
                q.push(pair<int, int>(newdist, graph[curr][i].first));
            }
        }
    }
    return dist;
}
cs



'Tech Stack > algorithms' 카테고리의 다른 글

More on Graph algorithms  (0) 2018.06.03
정수 알고리즘들  (0) 2018.04.18
그래프 응용  (0) 2018.04.16
심화과정  (0) 2018.04.15
Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
Tech Stack/algorithms

심화과정

Trie, Suffix tree(패턴매칭), KMP algorithm

Segment tree(구간탐색)


Graph algorithms(최단경로 등등)

최소 스패닝 트리, 최단경로 알고리즘

BFS, DFS

Dag topological sorting

'Tech Stack > algorithms' 카테고리의 다른 글

정수 알고리즘들  (0) 2018.04.18
그래프 응용  (0) 2018.04.16
심화과정  (0) 2018.04.15
Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
부분합 사용하기  (0) 2018.04.02
Tech Stack/algorithms

Graph DFS, BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
 
using namespace std;
 
void addedge(vector<vector<int>>& graph, int u, int v) {
    if (u >= graph.size() || v >= graph.size()) return;
    graph[u].push_back(v);
    graph[v].push_back(u);
}
 
void print(vector<vector<int>> & graph) {
    for (int i = 0; i < graph.size(); i++) {
        cout << "node " << i << "'s adjacents ";
        for (int j = 0; j < graph[i].size(); j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}
 
void DFSUtil(int u, vector<vector<int>> & graph, vector<bool> & visited) {
    visited[u] = true;
    cout << u << " ";
    for (int i = 0; i < graph[u].size(); i++) {
        if (visited[graph[u][i]] == false) {
            DFSUtil(graph[u][i], graph, visited);
        }
    }
}
 
void DFS(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == false) {
            DFSUtil(i,graph,visited);
        }
    }
}
 
void DFSiter(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> buffer;
    buffer.push(0);
    while (buffer.size() != 0) {
        int curr = buffer.top();
        buffer.pop();
        if (visited[curr] != true) {
            visited[curr] = true;
            cout << curr << " ";
        }
        for (int i = graph[curr].size()-1; i >=0; i--) {
            if (visited[graph[curr][i]] == false) buffer.push(graph[curr][i]);
        }
    }
    return;
}
 
void BFS(vector<vector<int>> & graph) {
    vector<bool> visited(graph.size(), false);
    queue<int> buffer;
    buffer.push(0);
    while (buffer.size() != 0) {
        int curr = buffer.front();;
        buffer.pop();
        if (visited[curr] != true) {
            visited[curr] = true;
            cout << curr << " ";
        }
        for (int i = graph[curr].size()-1; i >=0; i--) {
            if (visited[graph[curr][i]] == false) buffer.push(graph[curr][i]);
        }
    }
}
 
 
 
int main() {
    vector<vector<int>> graph(10, vector<int>());
    addedge(graph, 1, 2);
    addedge(graph, 2, 4);
    addedge(graph, 3, 1);
    addedge(graph, 5, 2);
    addedge(graph, 7, 2);
    addedge(graph, 7, 3);
    addedge(graph, 8, 4);
    addedge(graph, 6, 3);
    addedge(graph, 9, 1);
    addedge(graph, 0, 6);
    DFS(graph);
    cout << endl;
    DFSiter(graph);
    cout << endl;
    BFS(graph);
    while(1){}
    return 0;
}
cs


'Tech Stack > algorithms' 카테고리의 다른 글

그래프 응용  (0) 2018.04.16
심화과정  (0) 2018.04.15
Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
부분합 사용하기  (0) 2018.04.02
iterative binary method  (0) 2018.03.31
Tech Stack/algorithms

iterative DP

  1. dp[0][0]=dp[1][0]=dp[0][1]=dp[1][1] = 1
  2. for (int i = 0; i < H; i++) {
  3. for (int j = 0; j < W; j++) {
  4. //Skip base cases
  5. if (i < 2 && j < 2) {
  6. continue;
  7. }
  8. //This code ignores array index bounds as the point is to show the skeleton of DP
  9. dp[i + 1][j + 1] += dp[i][j];
  10. dp[i + 2][j + 1] += dp[i][j];
  11. dp[i + 1][j + 2] += dp[i][j];
  12. }
  13. }


'Tech Stack > algorithms' 카테고리의 다른 글

심화과정  (0) 2018.04.15
Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
부분합 사용하기  (0) 2018.04.02
iterative binary method  (0) 2018.03.31
quick sort, merge sort  (0) 2018.03.28
Tech Stack/algorithms

부분합 사용하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
void func3() {
    vector<vector<int>> tmp = { {1,2,3},{4,5,6},{7,8,9} };
    vector<vector<int>> psum(3, vector<int>(3, 0));
    psum[0][0] = tmp[0][0];
    vector<vector<int>> psumx(3, vector<int>(3, 0));
    for (int j = 0; j < 3; j++) {
        psumx[0][j] = tmp[0][j];
        for (int i = 1; i < 3; i++) {
            psumx[i][j] = psumx[i - 1][j]+tmp[i][j];
        }
    }
    // make psum
    for (int i = 0; i < 3; i++) {
        psum[i][0] = psumx[i][0];
        for (int j = 1; j < 3; j++) {
            psum[i][j] = psum[i][j - 1] + psumx[i][j];
        }
    }
    // iterate through all members
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = i; k < 3; k++) {
                for (int l = j; l < 3; l++) {
                    int sum;
                    if (i == 0 && j == 0) {
                        sum = psum[k][l];
                    }
                    else if (i == 0) {
                        sum = psum[k][l] - psum[k][j - 1];
                    }
                    else if (j == 0) {
                        sum = psum[k][l] - psum[i - 1][l];
                    }
                    else {
                        sum = psum[k][l] - psum[i - 1][l] - psum[k][j - 1] + psum[i - 1][j - 1];
                    }
                    cout << "(" << i << "," << j << ")" << " to " << "(" << k << "," << l << ")" << " sum " << sum << endl;
                }
            }
        }
    }
 
}
 
void func2() {
    vector<int> v1 = { 1,2,3,4,5 };
    // make psum
    vector<int> psum(v1.size() + 1, 0);
    psum[0] = 0;
    for (int i = 1; i <= v1.size(); i++) {
        psum[i] = psum[i - 1] + v1[i - 1];
    }
    // find all partial sums
    for (int i = 0; i < v1.size(); i++) {
        for (int j = i; j < v1.size(); j++) {
            cout << "sum of " << i << " " << j << " " << psum[j + 1] - psum[i] << endl;
        }
    }
    // make psum without psum[-1] = 0;
    psum[0] = v1[0];
    for (int i = 1; i < v1.size(); i++) {
        psum[i] = psum[i - 1] + v1[i];
    }
    // find all partial sums
    for (int i = 0; i < v1.size(); i++) {
        for (int j = i; j < v1.size(); j++) {
            if (i == 0) cout << i << " " << j << " " << psum[j];
            else cout << i << " " << j << " " << psum[j] - psum[i - 1];
        }
    }
}
 
vector<int> func() {
    vector<int> v1 = { 1,2,3,4,5 };
    return vector<int>(v1.begin(), v1.begin() + 2);
}
 
int main() {
    func3();
    while(1){}
    return 0;
}
cs


'Tech Stack > algorithms' 카테고리의 다른 글

Graph DFS, BFS  (0) 2018.04.15
iterative DP  (0) 2018.04.04
부분합 사용하기  (0) 2018.04.02
iterative binary method  (0) 2018.03.31
quick sort, merge sort  (0) 2018.03.28
recursion tecniques  (0) 2018.03.27
Tech Stack/algorithms

iterative binary method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "stdafx.h"
#include <iostream>
#include <vector>
 
using namespace std;
 
 
 
int iterbsearch(vector<int> * data, int target) {
    int low = 0;
    int high = data->size() - 1;
    while (low != high) {
        int mid = (low + high) / 2;
        if (data->at(mid) == target) {
            return mid;
        }
        else if (data->at(mid) > target) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }
    if (data->at(low) != target) {
        return -1;
    }
    else {
        return low;
    }
}
 
int findlowerbound(vector<int> * data, int target) {
    int low = 0;
    int high = data->size() - 1;
    int mid;
    while (low < high-1) {
        //cout << low << " " << high << endl;
        mid = (low + high) / 2;
        if (data->at(mid) == target) {
            return target;
        }
        else if (data->at(mid) > target) {
            high = mid;
        }
        else {
            low = mid;
        }
    }
    if (target < data->at(low)) {
        return -1;
    }
    else if (target > data->at(high)) {
        return data->at(data->size() - 1);
    }
    else {
        return data->at(low);
    }
}
 
int main() {
    vector<int> v1 = { 1,2,4,5,6,8,9,11,13 };
    cout << findlowerbound(&v1,12<< endl;
    cout << iterbsearch(&v1, 11<< endl;
    while(1){}
    return 0;
}
cs


'Tech Stack > algorithms' 카테고리의 다른 글

iterative DP  (0) 2018.04.04
부분합 사용하기  (0) 2018.04.02
iterative binary method  (0) 2018.03.31
quick sort, merge sort  (0) 2018.03.28
recursion tecniques  (0) 2018.03.27
for 루프 재귀호출 구성  (0) 2018.03.26
Tech Stack/algorithms

quick sort, merge sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
include "stdafx.h"
#include <iostream>
#include <map>
#include <unordered_set>
#include <string>
#include <algorithm>
 
using namespace std;
 
void mergesortrec(vector<int> * data, int low, int high) {
    // base case : if one left, return without any work
    if (low == high) {
        return;
    }
    // starting from length 2 ; split with 0 and 1 , 
    int mid = (low + high) / 2;
    mergesortrec(data, low, mid);
    mergesortrec(data, mid + 1, high);
    vector<int> buf;
    buf.reserve(high - low + 1);
    int highit = mid + 1;
    int lowit = low;
    for (int i = low; i <= high; i++) {
        if (lowit <= mid && highit <= high) {
            if (data->at(highit) > data->at(lowit)) {
                buf.push_back(data->at(lowit));
                lowit++;
            }
            else {
                buf.push_back(data->at(highit));
                highit++;
            }
            
        }else if (highit == high + 1) {
            buf.push_back(data->at(lowit));
            lowit++;
        }else if (lowit == mid + 1) {
            buf.push_back(data->at(highit));
            highit++;
        }
    }
    for (int i = low; i <= high; i++) {
        data->at(i) = buf.at(i - low);
    }
}
 
void mergesort(vector<int> * data) {
    mergesortrec(data, 0, data->size() - 1);
}
 
int main() {
    vector<int> v1 = { 5,3,1,9,10,4,2,8,8,7,6 };
    mergesort(&v1);
    for (int i : v1) {
        cout << i << " ";
    }
    while(1){}
    return 0;
}
 
//---
 
void quicksortrec(vector<int> * v1, int low, int high) {
    if (low == high) {
        return;
    }
    vector<int> buf;
    buf.reserve(high - low);
    int pivot = v1->at(high - 1);
    buf.push_back(pivot);
    int count = 0;
    for (int i = low; i < high - 1; i++) {
        if (pivot < v1->at(i)) {
            buf.push_back(v1->at(i));
        }
        else {
            buf.insert(buf.begin(), v1->at(i));
            count++;
        }
    }
    for (int i = low; i < high; i++) {
        v1->at(i) = buf.at(i - low);
    }
    quicksortrec(v1, low, low+count);
    quicksortrec(v1, low+count + 1, high);
}
 
void quicksort(vector<int> * v1) {
    return quicksortrec(v1,0,v1->size());
}
 
int main1212() {
    vector<int> v1 = { 3,1,4,10,3,13,9,8,7 };
    quicksort(&v1);
    for (int i : v1) {
        cout << i << " ";
    }
    while(1){}
    return 0;
}
cs


'Tech Stack > algorithms' 카테고리의 다른 글

부분합 사용하기  (0) 2018.04.02
iterative binary method  (0) 2018.03.31
quick sort, merge sort  (0) 2018.03.28
recursion tecniques  (0) 2018.03.27
for 루프 재귀호출 구성  (0) 2018.03.26
binary search 응용  (0) 2018.03.26
Tech Stack/algorithms

recursion tecniques

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int recfun(int n, int value) {
    if (n == 0) {
        return value;
    }
    int ret = recfun(n - 1, value * 2);
    ret = ret * 3;
    return ret;
}
 
int main() {
    cout << recfun(3, 1) << endl;
    while(1){}
    return 0;
}
cs

연산하면서 아래로 보낼꺼면 인자로 넣으면서 보내고

마지막 값에 터치하면서 리턴

맨 아래서 위로 올리는거면 받아서 연산 후 상위 리턴


'Tech Stack > algorithms' 카테고리의 다른 글

iterative binary method  (0) 2018.03.31
quick sort, merge sort  (0) 2018.03.28
recursion tecniques  (0) 2018.03.27
for 루프 재귀호출 구성  (0) 2018.03.26
binary search 응용  (0) 2018.03.26
sort with same string together  (0) 2018.03.26