잡블로그 :: 잡블로그

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

주어진 수열 중 최소값의 인덱스를 찾는다.
최소값의 인덱스를 맨 앞에 위치한 값과 교체한다.
이 과정을 마지막 인덱스 바로 전까지 진행한다.

시간복잡도는 O(N^2) 이다.

참고 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

[C++11 source code]

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
#include<iostream>
#include<vector>
using namespace std;
 
void print_v(vector<int>& v) {
    for (auto it : v) {
        printf("%d ", it);
    }
    puts("");
}
 
int main() {
    int n;
    vector<int> v;
    cin >> n;
    v = vector<int>(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    } // input
    
    for (int pivot = 0; pivot < n - 1; pivot++) {
        int change_index = pivot;
        
        for (int there = pivot + 1; there < n; there++) {
            if (v[change_index] > v[there]) {
                change_index = there;
            }
        }
 
        if (change_index == pivot) continue;
        int temp = v[pivot];
        v[pivot] = v[change_index];
        v[change_index] = temp;
    } // selection sort
 
    print_v(v);
 
    return 0;
}
/*
input format
N ~ # of numbers
v[0] ... v[N-1]
*/
Colored by Color Scripter
cs

저작자표시

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

기수정렬(Radix sort) (0)	2017.12.05
삽입정렬(Insertion sort) (0)	2017.12.02
버블정렬(Bubble Sort) (0)	2017.11.18
네트워크플로우, 에드몬드 카프(Edmonds-Karp) 알고리즘 (0)	2017.11.15
구간트리(세그먼트트리;Segment tree) (0)	2017.09.27

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

https://www.acmicpc.net/problem/6086

[문제풀이]

이미 그래프의 구성이 주어져 있고 source, sink가 정해져있기 때문에 그래프 모델링에 신경을 쓰지 않고 에드몬드카프 알고리즘을 바로 사용할 수 있던 문제였다.

[C++ source code]

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
#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX_V = 111;
const int INF = 1 << 30;
 
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int parent[MAX_V];
 
int residual(int here, int there) {
    return c[here][there] - f[here][there];
}
 
int min2(int a, int b) {
    return (a > b) ? b : a;
}
 
int ford_fulkerson(int source, int sink) {
    int total = 0;
    while (true) {
        memset(parent, -1, sizeof(parent));
        queue<int> Q;
        Q.push(source);
        parent[source] = source;
        while (!Q.empty()) {
            int here = Q.front();
            Q.pop();
            for (int there = 0; there < MAX_V; there++) {
                if (residual(here, there) > 0 && parent[there] == -1) { 
                    parent[there] = here;
                    Q.push(there);
                }
            }
        }
        
        if (parent[sink] == -1) break;
 
        int mn = INF;
        for (int p = sink; p != source; p = parent[p]) {
            mn = min2(c[parent[p]][p] - f[parent[p]][p], mn);
        }
 
        for (int p = sink; p != source; p = parent[p]) {
            f[parent[p]][p] += mn;
            f[p][parent[p]] -= mn;
        }
        total += mn;
    }
    return total;
}
 
int select_node(char V) {
    if ('A' <= V && V <= 'Z') {
        return V - 'A';
    }
    return V - 'a' + 26;
}
 
int main() {
    int n;
    char u, v;
    int capacity;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%*c%c%*c%c%*c%d", &u, &v, &capacity);
        c[select_node(u)][select_node(v)] += capacity;
    } // input
        
    int ans = ford_fulkerson(select_node('A'), select_node('Z'));
    printf("%d\n", ans);
    return 0;
}
Colored by Color Scripter
cs

저작자표시

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

[BOJ-2470]두용액 (0)	2018.05.25
[BOJ-10974]모든순열 (0)	2017.11.22
[BOJ-14731]謎紛芥索紀(Large)미분개색기 (0)	2017.11.18
[BOJ-13415]정렬게임 (0)	2017.11.15
[BOJ-1219]오민식의 고민 (0)	2017.11.11

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

https://www.acmicpc.net/problem/14731

[문제요약]

F(x) 함수가 주어지면, F'(2) 값을 구하는 문제이다.

이때 항의 개수는 [1, 1e5]

항의 계수 Coef~[1,100]

항의 차수 expo~[1, 1e9] 항의 차수와 관계없이 무작위로 주어진다.

[문제풀이]

[C++ source Code]

저작자표시

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

[BOJ-10974]모든순열 (0)	2017.11.22
[BOJ-6086]최대유량 (0)	2017.11.18
[BOJ-13415]정렬게임 (0)	2017.11.15
[BOJ-1219]오민식의 고민 (0)	2017.11.11
[BOJ-2665]미로만들기 (0)	2017.10.26

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

버블정렬

인접한 데이터를 비교하여 정렬시킨다. 시간복잡도는 O(N^2) 이다.

처음 N개 데이터를 인접한 데이터끼리 N-1번 비교하여 인덱스 끝에 정렬시킨 데이터를 넣는다.

이후 N-1개 데이터로 인접한 데이터 비교를 N-2번 ... 이 과정을 반복한다.

(N-1) + (N-2) + .... + 2 + 1 = (N-1)*(N-2) / 2 = O(N^2)

코드는 단순하다.

가장 마지막 위치부터 정렬시킨다.

참고 : https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

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
#include<iostream>
#include<vector>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   vector<int> v = vector<int>(n, 0);
   for (int i = 0; i < n; i++) {
      cin >> v[i];
   } // input
 
   for (int ith = 0; ith < n-1; ith++) {
      for (int here = 0; here < n - 1 - ith; here++) {
         int there = here + 1;
         if (v[here] > v[there]) {
            int temp = v[here];
            v[here] = v[there];
            v[there] = temp;
         }
      }
      cout << "["<<ith << "th] ";
      for (auto it : v) {
         cout << it << " ";
      }
      puts("");
   } // bubble sort
 
   for (auto it : v) {
      cout << it << " ";
   }
 
   return 0;
}
/*
input format
N
A[0] A[1] .... A[N-1]
*/
Colored by Color Scripter
cs

저작자표시

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

삽입정렬(Insertion sort) (0)	2017.12.02
선택정렬(Selection Sort) (0)	2017.11.19
네트워크플로우, 에드몬드 카프(Edmonds-Karp) 알고리즘 (0)	2017.11.15
구간트리(세그먼트트리;Segment tree) (0)	2017.09.27
SCC-코사라주 알고리즘(Kosaraju's Algorithm) (2)	2017.07.23

336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

BFS를 이용하여 네트워크플로우 source에서 sink까지 흘러들어가는 총 유량을 구할 수 있는 에드몬드 카프(Edmonds-Karp) 알고리즘

정점 A에서 B로 들어가는 간선은 E(A,B) 로 표현하면, 간선은 용량(capacity), 유량(flow) 값을 가진다.

유량을 구현하지 위해서는 3가지 조건이 충족되어야 한다.

1) 유량 제한 속성

C(A,B) - F(A,B) >= 0

2) 유량 대칭성

F(A,B) = -F(B,A)

3) 유량 보존

유량을 흘려보내는 시작점 source, 유량의 도착지 sink 를 제외한 정점에서의 들어오는 유량과 나가는 유량은 같아야한다. 즉, 들어오는 유량 == 나가는 유량 이어야 한다.

이러한 3가지 조건을 충족해서 유량을 흘려보내야한다.

아래 그림으로 해당 조건을 지키고 있는지 볼 수 있다.

source는 들어오는 간선이 없고, sink는 나가는 간선이 없다. 나머지 노드또한 그러할 수 있으나, 흘러오는 유량이 없다면 나가는 유량도 없으므로 유량보존을 시킬 수 있다.

임의적으로 유량을 흘려보낸다고 하자. 만약에 아래와 같은 식으로 유량이 흘러간다면,

source->1->sink 로 가는 길을 막게 된다. 이를 해결하기 위해서 유량의 대칭성을 이용할 수 있다.

아래 그림과 같이 유량의 대칭성을 이용하여 F(2,1) = -F(1,2) 로 유량이 들어왔다는 표시를 할 수 있다. 이때 다른 간선에도 유량의 대칭성이 표시되어야 하지만 설명에는 정점 1과 2를 잇는 간선의 유량이 중요하므로 다른 유량의 대칭성으로 인한 역간선은 추가하지 않았다.

이렇게 대칭성으로 만들어진 F(1,2) 의 유량은 아래와 같이 이용될 수 있다. C(1,2) - F(1,2) = 0 - (-2) > 0 이므로 2의 유량을 흘려보낼 수 있음을 알 수 있다. 대칭성으로 이러한 방법이 만들어진다.

source -> 1 -> sink 로 가는 길이 없어졌지만, 역간선을 이용하여 source -> 1 -> 2 -> sink로 유량을 흘려보낼 수 있음을 볼 수 있다.

이렇게 유량을 모두 흘려보내게 되면, 아래와 같이 sink에 총 4의 유량을 흘려보낼 수 있다.

이런 성질을 이용하여 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
#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX_V = 111;
const int INF = 1 << 30;
 
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int parent[MAX_V];
 
int residual(int here, int there) {
    return c[here][there] - f[here][there];
}
 
int min2(int a, int b) {
    return (a > b) ? b : a;
}
 
int edmonds_karp(int source, int sink) {
    int total = 0;
    while (true) {
        memset(parent, -1, sizeof(parent));
        queue<int> Q;
        Q.push(source);
        parent[source] = source;
        while (!Q.empty() && parent[sink] == -1) {
            int here = Q.front();
            Q.pop();
            for (int there = 0; there < MAX_V; there++) {
                if (residual(here, there) > 0 && parent[there] == -1) { 
                    parent[there] = here;
                    Q.push(there);
                }
            }
        }
        
        if (parent[sink] == -1) break;
 
        int mn = INF;
        for (int p = sink; p != source; p = parent[p]) {
            mn = min2(c[parent[p]][p] - f[parent[p]][p], mn);
        }
 
        for (int p = sink; p != source; p = parent[p]) {
            f[parent[p]][p] += mn;
            f[p][parent[p]] -= mn;
        }
        total += mn;
    }
    return total;
}
Colored by Color Scripter
cs

저작자표시

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

선택정렬(Selection Sort) (0)	2017.11.19
버블정렬(Bubble Sort) (0)	2017.11.18
구간트리(세그먼트트리;Segment tree) (0)	2017.09.27
SCC-코사라주 알고리즘(Kosaraju's Algorithm) (2)	2017.07.23
강한연결요소(SCC ; Strongly Connected Component) (0)	2017.07.22

잡블로그

선택정렬(Selection Sort)

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

[BOJ-6086]최대유량

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

[BOJ-14731]謎紛芥索紀(Large)미분개색기

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

버블정렬(Bubble Sort)

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

네트워크플로우, 에드몬드 카프(Edmonds-Karp) 알고리즘

'PSNote > 알고리즘정리해봊' 카테고리의 다른 글

+ Recent posts

티스토리툴바