내용을 대략적으로 이해하기에는 여기가 좋다. (구현방법도 단계별로 익히기 좋..다고 생각했는데 다시 읽어보니 왜 항상 최단이 되는지 why에 대한 설명이 좀 부족한 느낌이 드네.. 아래 증명란에서 추가 검토하자)

 

플로이드와샬의 시간복잡도는 심플하게 $O(V^3)$이다. 

N이 2000일때 TLE난적이 있으니 참고하자. 

($2000^3 = 2,000,000,000$, 20억 정도니 2~20초 걸리는거니 당연할지도)

 

PS에서 쓰는 내 소스코드는 다음과 같다.

(백준 11404번 문제의 답안이기도 하다.)

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
#include <bits/stdc++.h>
using namespace std;
 
//플로이드 와샬
int n, m, u, v, w, in[101][101];
int main()
{
    const int INF = INT_MAX / 4;
    scanf("%d%d", &n, &m);
    //인접행렬만들자
    fill(&in[0][0], &in[n][n], INF);  // 없는간선은 INF
    for (int i = 0; i < n; i++) in[i][i] = 0;  // 자기자신은 0
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        // 간선이 여러개일경우, 최단거리 단선만 기억
        // 이문제의 경우 1-base index라 1빼줌(문제에 따라 다르게 처리)
        in[u - 1][v - 1] = min(in[u - 1][v - 1], w);
    }
    //정점 i > k > j, 핵심로직
    for (int k = 0; k < n; k++)  // 중간정점을 중심으로, 모든 중간정점을 검토함에 주의
    for (int i = 0; i < n; i++)  // 모든 시작정점
    for (int j = 0; j < n; j++)  // 모든 끝정점
        if (in[i][j] > in[i][k] + in[k][j])  // 현재 최단거리보다 K를 거치는게 더 짧으면
            in[i][j] = in[i][k] + in[k][j];  // 업데이트
 
   //결과출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            // 경로를 못찾았을때 이문제는0으로 바꾸는데, 문제에 따른처리 필요
            printf("%d ", in[i][j] < INF ? in[i][j] : 0);
        printf("\n");
    }
    return 0;
}
 cs

 

 

아래는 주석제거하고 짧은버전

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, w, in[101][101];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if(i-j)in[i][j] = 1e9;
    while(m--) scanf("%d%d%d", &u, &v, &w), in[u-1][v-1] = min(in[u-1][v-1], w);
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        in[i][j] = min(in[i][j], in[i][k] + in[k][j]);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) printf("%d ", in[i][j] < 1e9 ? in[i][j] : 0);  
        printf("\n");
    }
    return 0;
}
 
 cs
 
 

경로를 출력하는 문제에 대해서는, 여기를 참조하면 어렵지 않게 구현하고 풀 수 있다.

 

증명

많은 인터넷 상의 자료들은 증명에는 별로 관심없고, HOW에만 관심이 있는듯 보인다.

일단 증명에 대한 힌트는 그래도 위키피디아 여기에서 엿볼 수 있는데..

최대 $(|V|^{2})$의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 

라는 표현이 있는데, 일견 이해는 되지만, 모든 변의 조합을 1회만 업데이트 하면 옵티멀이 된다는게 뭔가 찜찜하다.

여기에 증명이 나와있는데, 설명이 잘 이해가 안된다. 이 동영상이 그나마 쉽게 접근하고 있는데, 여전히 multiple update가 필요하지 않은 이유에 대해서는 설명이 잘 안된다.

 

어쨌거나, 실제 증명은 다음과 같이 귀납법으로 간단하게 정의된다.

$$\delta^k(i,j)=\begin{cases}
\min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\} & \text{for}\,k\geq 1\\
w(i,j) & \text{for}\,k=0\,\text{(i.e., base case)}, 
\end{cases}$$

 

직관적으로는.. k가 0에서 k가 1로 넘어갈때는 확실한데, k가 1에서 2 이상으로 넘어갈때, 기존 업데이트 된 값들이 최대 k번의 연산 이상으로 업데이트가 필요없다는게 잘 이해가 안된다.

 

 

정점 가중치

이 문제를 보면 간선 가중치 뿐 아니라 정점 가중치도 고려해야하는데, 풀어보면 특별히 난이도가 올라가거나 복잡해지진 않았다.

이문제만 그런걸수도 있긴한데, 현재 발견된걸로 그러함.

 

 

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

비트연산  (0) 2020.04.02
사이클 검출(Cycle Detection)  (0) 2020.03.30
SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27

SPFA알고리즘은 벨만포드 알고리즘의 개선판으로, 

벨만-포드 알고리즘이 정점의 개수가 V일때, 모든 정점을 V-1번 갱신하는데 비해, 

SPFA는 queue를 사용해서, 시작점과 연관있는 정점만 갱신해 나가는 아이디어

 

아래는 직접 구현해 본건데 백준11657문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
 
const int INF = INT_MAX / 4;
struct node { int v, w; };
vector<int> SPFA(int max_v, int start_v, vector<vector<node>>&adj_list) {
    vector<int> min_dist(max_v + 1, INF);
    min_dist[start_v] = 0;
    queue<node> q; q.push({ start_v,0 });
    queue<int> qn; qn.push(0);
    while (q.size()) {
        node n = q.front(); q.pop();
        int nn = qn.front(); qn.pop();
        if (nn >= max_v) { printf("-1\n"); exit(0); }//네거티브 사이클
 
        //이 부분, 아래 for문 안쪽이랑 중복같기도 해보이지만 없으면 TLE난다.
        if (min_dist[n.v] < n.w) continue;
        min_dist[n.v] = n.w;
 
        for (node adj : adj_list[n.v]) {
            //최소값으로 업데이트
            if (min_dist[adj.v] <= adj.w + n.w) continue;
            min_dist[adj.v] = adj.w + n.w;
            q.push({ adj.v, adj.w + n.w }), qn.push(nn + 1);
        }
    }
    return min_dist;
}
 
int main()
{
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w });
    }
 
    vector<int> dist = SPFA(N, 1, adj_list);
    for (int i = 2; i <= N; i++) {
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
    }
    return 0;
}
 cs

 

근데 제출해본 결과, 스피드업이 없었다는 문제가? 복잡도로는 벨만포드와 같기도 하고...

근데 보면 볼수록 신기한점은 우선순위큐만 없고, for문안에 continue로직이 추가됐을뿐이지 다익스트라랑 소스코드가 거의 동일하다는 점이다.

그래도 네거티브 사이클을 디텍트할 수 있는건 장점

 

ChatGPT 말로는 위 코드는 SPFA는 아니라는데 ㅋㅋ 나중에 시간날때 검토해보자.

is it SPFA?
No, it is not SPFA (Shortest Path Faster Algorithm). SPFA is also a single-source shortest path algorithm, similar to Bellman-Ford, but it uses a queue to keep track of the current node and its distance from the starting node, whereas Bellman-Ford uses a simple loop. The implementation you provided is the Bellman-Ford algorithm, as it uses queue, it does not check negative-weighted edges and it uses for loop, which is the characteristic of Bellman-Ford algorithm, also it uses the continue in order to check whether the current node is visited or not, which is another characteristic of Bellman-Ford algorithm.
반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

사이클 검출(Cycle Detection)  (0) 2020.03.30
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19

여기 설명이 워낙 좋아서 한 번 보면 이해되고, 그렇게 어려운 알고리즘도 아니다.


다익스트라와 비슷하게, 하나의 정점에서 다른 모든정점으로의 최단거리를 한번에 구해주지만, 

약간은 느린편이고, 

대신 negative edge에 대해서도 처리가 가능하다.


PS용으로 내가 사용하는 코드는 다음과 같다.

(백준11657문제의 답안이기도 하다.)

참고로 정점과 간선의 정보를 표현하는데는 인접행렬과 인접리스트 두 가지 방식이 있는데,

아래는 좀 더 범용적으로 사용할 수 있는 인접리스트 방식을 사용했다.

예를 들어 정점간 간선이 하나가 아니라 여러개일 때는 인접리스트는 표현이 쉽지만 인접행렬은 좀 애매하다.

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
#include <bits/stdc++.h>
using namespace std;
 
const int INF = INT_MAX / 4;
struct node { int v, w; };
 
vector<int> bellman_ford(int max_v, int start_v, vector<vector<node>>&adj_list) {
    //모든 정점의 최단 경로를 무한대로 초기화
    vector<int> dist(max_v+1, INF);
    //시작정점만 0으로 초기화
    dist[start_v] = 0;
    for (int t = 0; t < max_v - 1; t++) {//N-1번 업데이트 수행
        for (int j = 1; j <= max_v; j++) {//모든 노드에 대해
            for (node adj : adj_list[j]) {
                //무한대가 아니면
                if (dist[j] == INF) continue;
                //최소값으로 업데이트
                dist[adj.v] = min(dist[adj.v], dist[j] + adj.w);
                int sfsd = 1;
            }
        }
    }
    //한번더 업데이트 시도해서
    for (int j = 1; j <= max_v; j++) {//모든 노드에 대해
        for (node adj : adj_list[j]) {
            if (dist[j] == INF) continue;  // 고립된건 무한대일수 있음
            //업데이트가 일어나면
            if (dist[adj.v] > dist[j] + adj.w) {
                //네거티브 사이클이 있는것
                printf("-1\n"); exit(0); // 코드 재활용시 이부분 주의
            }
        }
    }
    return dist;
}
 
int main()
{
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w });
    }
 
    vector<int> dist = bellman_ford(N, 1, adj_list);
    for (int i = 2; i <= N; i++) {
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
    }
    return 0;
}
cs


시간복잡도

복잡도는 정점의 개수가 $V$ 이고 간선의 개수가 $E$일때 $O(VE)$가 되며,

directed graph기준으로 모든 정점간 간선이 꽉차있다고 하면 $E = (V-1)^2$이 되어 $O(V^3)$이 된다.

근데 보통 간선이 꽉차있지 않고, undirected라고 하더라도 간선의 개수가 sparse 하지만 않다면, 

복잡도로 치면 $O(E) = O(V^2)$이 되는 경우가 일반적이라서 전체적인 벨만포드의 복잡도는 $O(V^3)$정도로 보면 된다.(다익스트라가 $O(V^2)$미만으로 계산되는데 비해서 비싼편)


반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)  (0) 2020.03.28
SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19

최단거리를 구할때 BFS를 쓰는 경우가 많은데,


만약 정점 간 거리가 일정하지 않다면, 다익스트라를 쓰면된다 (BFS와 기본로직은 비슷하다)


다익스트라는 시작 정점에서 다른 모든 정점으로의 최단거리를 한 번에 구할 수 있다.

(모든 정점에서 다른 모든 정점은 아닌것에 주의, 이걸 원한다면 플로이드 와샬 알고리즘을 써야한다)


주의할점은 정점간 거리에 음수가 있으면 안된다는 점이다.(negative edge)

이때는 벨만-포드 알고리즘을 써야한다.


근데, negative edge가 안되는 버전이 가장빠르고, 하나의 정점을 두번이상 방문하지 않기는 하는데,

> enqueue, dequeue는 여러번 되는데 첫번째 dequeue만 효과를 가지고 나머지는 무시된다는걸 이해하는게 중요하다. visit 배열을 사용해서 두번째 이후 dequeue를 강제로 무시해도 OK. 무시되지 않는 dequeue를 "방문"이라고 생각하면 하나의 정점을 한 번만 방문하는게 맞다. enqueue/dequeue는 오히려 간선관점에서 O(E)안에 포함된다고 보는게 맞을거 같다.

하나의 정점을 여러번 방문할 수 있게 허용하면 negative edge를 가지는 경우에도 쓸 수 있다.

아래 내 소스에서 min_dist[n.v] != INF 이부분을 min_dist[n.v] < n.w 이렇게 바꾸면, 여러번 방문할 수 있게 허용하는 버전이 된다.

이 답변에서 3번 variant가 되는 것

근데 사실 이렇게 재방문을 허용하게 되면 다익스트라만의 complexity 장점이 사라지는 셈이라,

SPFA를 쓰는게 더 좋은경우가 생기는걸 보았다.

실제로 발생하면 SPFA쪽을 사용하자.


내가 작성한 PS에서 사용하는 다익스트라 로직은 다음과 같다.

(백준 1753 문제의 답안이기도 하다)

근데 여기에 따르면 아래구현은 이미 방문한 정점을 다시 방문시 TLE로 만들 수 있으며

q.pop()한다음에 if(n.w > min_dist[n.v]) continue; 이 코드를 넣어줘야 한다고 한다. 나중에 체크해보자.

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
#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
bool operator<(node l, node r) { if (l.w == r.w)return l.v > r.v; return l.w > r.w; }
using vi = vector<int>;
using vvn = vector<vector<node>>;
const int INF = INT_MAX / 4;
vi Dijkstra(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    if (base1) max_v++;
    vi min_dist(max_v, INF);  // 거리 무한대로 초기화
    priority_queue<node> q;
    q.push({ start_v, 0 });  // 거리 0으로 시작정점 enqueue
    min_dist[start_v] = 0;   // 시작점 스스로의 거리는 0 (문제에 따라 중요한 경우 있음)
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            // min_dist를 통한 visit 처리(enqueue하기 전에 visit처리해주는게 중요하다)
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w });
            }
        }
    }
    return min_dist;
}
 
int main()
{
    //V:정점개수, E:간선개수, K:시작점
    int V, E, K; scanf("%d%d%d", &V, &E, &K);
    vector<vector<node>> adj_list(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    vector<int> d = Dijkstra(V, K, adj_list, true);
    for (int i = 1; i <= V; i++)
        if (d[i] == INF)puts("INF");
        else printf("%d\n", d[i]);
    return 0;
}
cs




Tip1

최단거리 이외에 비용등의 추가 constraint가 붙을 경우 min_dist가 현재 1차원 배열인데 2차원으로 차원을 늘리면 풀릴 수 있다. (백준 10217번이 그 예)

참고로 위 소스에서 min_dist는 int min_dist[max_v + 1]; 로 해도 되지만 max_v가 상수가 아닌 변수여서 vector로 해놓은건데,

차원이 늘어나서 int min_dist[max_v + 1][M + 1]; 과 같은 형태가 된다면 vector of vector가 필요하다. 

이때는 약간 복잡해보일수는 있으나, 다음과 같이 코딩하면 된다.

1
2
    vector<vector<int>> min_dist(max_v + 1, vector<int>(M+1, INF));
 
cs


최대값을 상수값으로 적는대신 변수값으로 가변적으로 세팅할 수 있는 장점(이때문에 문제마다 최대값에 따라 101, 2001등 수정할 필요가 없어진다) 이외에, 덤으로 초기값을 INF로 별도 loop없이 편하게 줄 수 있는 장점도 있다.


경로추적

경로추적이 필요한 경우에는 아래 소스처럼 from 배열을 하나 운영하면 된다. 이 문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;
struct node { int v, w; };
bool operator<(node l, node r){if(l.w==r.w)return l.v>r.v; return l.w>r.w;}
int n, m, s, e;
typedef vector<vector<node>> vvn;
typedef vector<int> vi;
vector<int> Dijkstra(int max_v, int start_v, vvn& adj_list, vi& from) {
    vector<int> min_dist(max_v + 1, INF);
    priority_queue<node> q;
    q.push({ start_v, 0 });
    min_dist[start_v] = 0;
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w }), from[adj.v] = n.v;  // 경로 기록
            }
        }
    }
    return min_dist;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    vvn adj_list(n + 1);
    vi from(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    scanf("%d%d", &s, &e);
    vi d = Dijkstra(n, s, adj_list, from);
    printf("%d\n", d[e]);
    if (s == e) {
        printf("1\n%d\n", s);
        return 0;
    }
    deque<int> dq;
    while (e != s && from[e] != -1)dq.push_front(e), e = from[e];
    dq.push_front(s);
    printf("%d\n", dq.size());
    for (auto a : dq)printf("%d ", a); puts("");
 
    return 0;
}
cs




복잡도

BFS의 복잡도가 $O(E+V)$ 인데 반해서 다익스트라의 복잡도는 $O((V+E)\times log(V))$이다. 왜 다익스트라가 더 높냐구? 다익스트라는 BFS와 다르게 간선거리를 고려해야하므로, priority queue를 써야하고 그에 따라 $log(V)$가 추가되는 것.BFS는 그냥 queue를 쓰므로 $O(1)$. 

보통은 아무리 sparse해도 정점이 간선보다 많은 경우는 문제로 잘 안주어진다 따라서 $E >= V$인 경우가 대부분이고 이렇게 되면 복잡도가 $O(E \times log(V))$이다. 이것 때문에 다익스트라 복잡도를 보통 이걸로 얘기하는 것. 트리의 경우는 $E=V-1$이지만, dense한 그래프의 경우 $E \sim V^2$이므로 이 경우는 $O(V^2log(V))$정도로 심플하게 봐도 좋다. 


반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

SPFA (Shortest Path Faster Algorithm)  (0) 2020.03.27
벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09

DFS는 탐색기법의 하나로, 트리인 경우 아래처럼 말단 노드까지 쭉 내려가본 다음, 다시 올라오면서(back track) 안가본 노드를 가보는 식으로 동작한다.


동작기법이 재귀호출과 유사하여, 재귀로 많이 구현하는 편


재귀를 사용하는 경우 시스템 스택의 제한을 받아서 탐색공간이 너무 크면 stack overflow가 발생할 수 있는 단점이 있다.


시간복잡도

V개의 정점, E개의 간선으로 이루어진 그래프의 경우에..

여기에 잘 나와있는데, 인접행렬로 구현했을 경우 다음 간선으로 가는데 V루프를 돌리므로, 시간복잡도는 $O(V^2)$이 되고(E에 상관없음에 주의),

인접리스트로 구현할 경우 랜덤액세스 형식으로 다음 간선으로 접근하므로 $O(V+E)$가 된다. (근데 간선이 굉장히 많은 경우는 $E \sim V^2$개 근처까지 가므로 이때는 $O(V+V^2) = O(V^2)$ 이렇게 되기는 한다.)

그래서 인접리스트로 구현하는게 인접행렬보다 좋은 어프로치다.





반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

벨만-포드 알고리즘(Bellman-Ford’s algorithm)  (0) 2020.03.27
다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09
냅색DP(knapsack DP)  (0) 2020.03.07


너비우선탐색(BFS)는 다음처럼 물결이 퍼지듯 가까운 경로 후보부터 탐색하는 방법이다

한쪽 길을 끝까지 먼저 탐색하는 깊이우선탐색(DFS)과 비교된다



이런걸 왜쓰냐면 

1 최단경로를 구할때, 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있는 장점이 있어 DFS에 비해 빠른경우가 많고

2 보통 재귀를 통해 시스템스택을 사용하는 DFS에 비해 queue를 사용하기 때문에 스택오버플로에서 비교적 자유롭고 힙공간을 넓게 쓸 수 있어 좀 더 넓은 범위 탐색에 유리하다.


S에서 E로 최단경로를 참색하는 아래 예제를 보자



시간복잡도

DFS와 마찬가지로 BFS도 인접행렬로 구현하면 $O(V^2)$이고 인접리스트로 구현하면 $O(V+E)$인것 같다. 
조금 헷갈리는건 간선이 많아도 결국 V개 노드만 방문하는데 O(E)가 어디서 소모되는지?.. 어쨌든 visted 정도라도 체크하니까 그런것일까? ㅎ

경로찍기 & 람다(lambda)함수 사용

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
#include <bits/stdc++.h>
using namespace std;
int N, K, x, c, visit[100001], from[100001];
deque<int> seq;
int main(void) {
    fill(from, from + 100001, -1);
    scanf("%d%d", &N, &K);
    queue<int> qx, qc;     qx.push(N), qc.push(0);
    while (qx.size()) {
        x = qx.front(); qx.pop();
        c = qc.front(); qc.pop();
        if (x == K) {
            printf("%d\n", c); break;
        }
        auto enqueue = [&](int v) {
            if (v <= 100000 && v >= 0 && visit[v] == 0) 
                visit[v] = 1, qx.push(v), qc.push(c + 1), from[v] = x;
        };
        enqueue(2 * x);
        enqueue(x - 1);
        enqueue(x + 1);
    }
    for (int i = 0; i <= c; i++) seq.push_front(K), K = from[K]; 
    for (auto a : seq)printf("%d ", a); printf("\n");
    return 0;
 }
cs

최단거리 뿐 아니라 그 경로도 찍고 싶다면 위처럼 글로벌하게 from배열을 하나 운용하면 된다.

람다함수 사용도 잘 봐두자. 위 코드는 이 문제에 대한 답안이기도 하다.

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

다익스트라 알고리즘 Dijkstra  (0) 2020.03.27
깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09
냅색DP(knapsack DP)  (0) 2020.03.07
이진탐색/이분탐색 (Binary Search) 알고리즘  (0) 2019.12.09

여기 참조

 

CentOS기준.

 

CentOS7에서는 sudo systemctl start supervisord 하면 supervisor 서비스 시작할 수 있다.

CentOS6에서는 sudo /etc/init.d/supervisord start

 

sudo supervisorctl 해서 사용

 

가끔 supervisor.sock no such file 이라는 오류가 나면,

/etc/supervisor/conf.d/안에 있는 config파일이 오류일수 있다.

오류나는 파일을 제거하고

sudo systemctl restart supervisord하면 됨

 

supervisor.sock refused connection이라고 뜨면 재시작시도해보고 supervisord.pid문제로 기다린다고 뜨면

해당 pid를 강제로 지워주고 재시작하면 된다.

 

program등록법

/etc/supervisor.conf 또는 /etc/supervisor/conf.d/ 밑에 있는 conf들에서 [program] 섹션에 있는것들이 등록된다.

등록후 아래 명령어를 통해 갱신해줘야 적용된다.

sudo supervisorctl reread
sudo supervisorctl update

sudo 암호입력없이 쓰는법

 

sudo visudo를 해서 /etc/sudoers에 계정을 추가해주면되는데

sevity  ALL=(ALL:ALL) NOPASSWD: /usr/bin/supervisorctl

 

주의할점은 맨 아래다 하지 않으면 아래와 같은 경우 덮어써진다는 점이다.

# sevity가 sudo그룹에 속할 경우 
# 규칙은 가장 마지막에 적혀있는 sudo에 대한 규칙이 적용됩니다
sevity  ALL:(ALL) NOPASSWD: ALL
%sudo    ALL:(ALL) ALL


NOPASSWD부분은 무시돼 버린다.

/var/run/supervisor.sock 파일에 아래내용을 넣으면 sudo를 항상 생략하고 쓸 수 있다.

[unix_http_server]
file=/var/run/supervisor.sock
chown=sevity:sevity
chmod=02770

chmod=02770는 파일 또는 디렉토리의 그룹에게만 모든 권한을 부여(77부분)

 

로그보는법

/var/log/supervisor/에 가면 로그들 모여있다.

 

docker와 함께 운용하는법

docker는 supervisorctl stop을 해도 docker stop이 잘 되지 않는다. (일반 프로세스와 좀 다른듯하다)

supervisor는 command는 지원하지만 stopcommand는 지원하지 않아서 종료시에 명령어를 명시적으로 주기 어렵다.

그래서 command 안에다가 다음처럼 bash로 trap을 설정해두면 이건 잘 동작한다.

$ cat docker_run.sh

#!/bin/bash

PORT=$1
trap 'docker stop frontend-service' EXIT
docker run --rm\
  --name frontend-service\
  --network host \
  -p $PORT:$PORT \
  -e PORT=$PORT \
  frontend-service
반응형
저작자표시

'Programming > Linux' 카테고리의 다른 글

리눅스 퍼미션 개념(파일 권한 관련)  (0) 2020.04.10
NTP설정  (0) 2020.03.30
ssh 자동로그인(ssh-keygen)  (0) 2020.03.10
scp관련  (0) 2019.12.05
mount관련  (0) 2019.12.05

문제는 여기






퀸은 배치된 칸을 기준으로 가로,세로, 그리고 대각선 이동이 가능한 가장 가치있는 말로 다음 빨간선과 같이 움직인다.





다음은 N이 8일때 해 중의 하나이다.



만약 모든 경우의 수에 대해서 재귀를 통해 브루트포스 방식으로 구한다음에 해인지 아닌지를 말단에서 체크하게 되면, DFS가 되는데, 

N=8인 경우 체스판의 칸 개수가 8x8=64개이고 이중에 8개를 고르는 조합의 수가 되므로 $_{64}C_8 = 4,426,165,368$이 되어 44억이 넘어갑니다. 이중에 92개만이 정답이죠.


가로로 겹치지 않게 한줄에 하나의 queen만 놓는식으로 가지치기(백트래킹)를 하게되면 $8^8 = 16,777,216$으로 줄어듭니다. (천6백만)


세로로도 겹치지 않게 permutation을 사용하는 백트래킹의 경우 $8! = 40,320$이 되어 훨씬 줄어듭니다.


다음과 같이 한줄씩 보면서 가로,세로,대각선 모두에 대해 백트래킹을 사용하면 5,508정도로 더 줄어듭니다.


이 문제의 경우 이정도 가지치기를 하면 제한시간내에 맞았습니다를 받을 수 있습니다.





소스코드는 다음과 같습니다.

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
#include <bits/stdc++.h>
using namespace std;
 
int N;
int vx[15+1], vy[15+1];
 
int go(int y, int x)
{
    //check valid (back tracking)
    for (int i = 0; i < y; i++) {
        if (y == vy[i] || x == vx[i]) return 0;  //직선겹침
        if (abs(x - vx[i]) == abs(y - vy[i])) return 0; //대각겹침
    }
 
    //terminal condition
    if (y == N - 1) return 1;
 
    //now record position
    vy[y] = y, vx[y] = x;
 
    //loop
    int r = 0;
    for (int i = 0; i < N; i++) {
        r += go(y + 1, i);
    }
 
    return r;
}
 
int main(void)
{
    scanf("%d", &N);
    int r = 0;
    for (int i = 0; i < N; i++) r += go(0, i);
    printf("%d\n", r);
    return 0;
}
cs






반응형
저작자표시

'Programming > Problem Solving' 카테고리의 다른 글

코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (0) 2020.03.30
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 팁모음  (0) 2019.03.18

여기 잘 나와있다.

 

아래 방법은 client side가 윈도우11일때도 잘 됨을 확인

 

먼저 client side에서 ssh-keygen -t rsa 라고 쳐서 공개/비공개 키를 만든다.

 

 

그담에 서버측으로 ssh를 복사해줘야 하는데

방법1. 자동

ssh-copy-id id@server.com

방법2. 수동

scp ~/.ssh/id_rsa.pub id@sever.com:id_rsa.pub 이렇게 해서 server side에 복사한다.

 

그다음 server side에서

cat ~/id_rsa.pub >> ~/.ssh/authorized_keys 이걸로 server쪽 공개키 허용목록에 추가해준다.

 

이때 chmod 600 으로 파일들을 본인만 read/write 가능하게 해주는게 좋다(아니면 에러나는 경우가 있음)

반응형
저작자표시

'Programming > Linux' 카테고리의 다른 글

NTP설정  (0) 2020.03.30
supervisor  (0) 2020.03.18
scp관련  (0) 2019.12.05
mount관련  (0) 2019.12.05
리눅스 비밀번호 틀린 횟수 초과 대응방법  (0) 2019.10.07

백트래킹 : DFS + 가지치기(break or continue)


모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break 나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라 한다.


대표적인 문제로는 N-Queen이 있다.



반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

깊이 우선 탐색(depth-first search: DFS)  (0) 2020.03.19
너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19
냅색DP(knapsack DP)  (0) 2020.03.07
이진탐색/이분탐색 (Binary Search) 알고리즘  (0) 2019.12.09
소수(prime)  (0) 2019.03.30

+ Recent posts

티스토리툴바