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


처음에 단순히 dfs로 해결했습니다.

간단하지만 런타임 시간이 꽤 오래 걸리더군요.

일단 다 풀고나서 다른 분들이 어떻게 풀었나 봤더니


disjoint-set(union-find)로 푸셨더라구요!


그래서 저도 다시 풀어보았습니다.


간단했습니다. 우선 연결되어있다면 union을 해서 같은 그룹으로 묶습니다.

union을 한다고 모든 노드에서의 부모가 바뀌는 것은 아닙니다.

x와 y를 유니온 하면 x와 y의 부모만 바뀌는 것이므로

다시한번 find를 해줘야 완전히 갱신이 됩니다.

아무튼!! 이것은 union-find에 대해서 공부하시면 알게되실겁니다.


그리고 나서 모든 노드에 대해 그루핑이 끝났다면!


그룹이 몇개인지 세어줘야합니다!

저는 간단하게 노드 3천개에 대한 tmp 배열을 만들어서

해당 노드의 부모가 tmp배열에서 true라면 이미 센 그룹이므로 넘어가고 

false라면 안센 그룹이므로 tmp배열을 갱신시켜주고

그룹의 개수를 늘려줍니다.


uinon-find 코드입니다.

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
#include <iostream>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
 
int parent[3000];
int n;
 
bool isConneted(int a, int b) {
    int x = pos[a].first - pos[b].first;
    int y = pos[a].second - pos[b].second;
    int z = r[a] + r[b];
 
    return (x * x + y * y) <= z * z;
}
 
int Find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
 
    if (x != y) {
        parent[x] = y;
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        for (int i = 0; i < n; i++) parent[i] = i;
        
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (isConneted(i, j) && parent[i] != parent[j]) {
                    Union(i, j);
                }
            }
        }
 
        bool tmp[3000] = { 0, };
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            int p = Find(i);
            if (!tmp[p]) {
                tmp[p] = 1;
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
cs



dfs코드입니다.

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
bool visit[3000];
int n;
 
int calcDistance(pii a, pii b) {
    int  x = (a.first - b.first);
    int y = (a.second - b.second);
    return x * x + y * y;
}
 
void dfs(int idx) {
    for (int i = 0; i < n; i++) {
        int rSum = r[idx] + r[i];
        if (idx == i || visit[i] || calcDistance(pos[idx], pos[i]) > rSum * rSum) continue;
        visit[i] = 1;
        dfs(i);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                dfs(i);
                ret++;
            }
                
        }
        cout << ret << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2178] 미로 탐색  (0) 2017.09.15
[2667] 단지번호붙이기  (0) 2017.09.15
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


운영체제 스케줄링 기법을 이용하면 되는 문제입니다..

(어떤건지는 까먹음..)


분류는 그리디 알고리즘이며,

문제 해결 절차는 이렇습니다.


1. 내가 사용할 아이템(장비???)가 꽂혀있는지 확인합니다.

2. 1에서 꽂혀있으면 다음 장비로 넘어갑니다.

3. 1에서 꽂혀있지 않으면 비어있는 포트가 있는지 확인한다.

4. 3에서 빈 포트가 있으면 그냥 꽂는다.

5. 3에서 빈 포트가 없으면 현재 꽂혀 있는 아이템 중에 나중에 가장 늦게 사용하는 아이템 포트를 뺸다.

6. 1~5를 반복한다.


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
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdio>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[100];
bool use[100];
int tab[100];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, nn;
    cin >> n >> nn;
 
    for (int i = 0; i < nn; i++) {
        cin >> arr[i];
        arr[i]--;
    }
 
    int ret = 0;
    int tabIdx = 0;
 
    for (int i = 0; i < nn; i++) {
 
        if (use[arr[i]]) continue; //사용하던 아이템임        
                                   //멀티탭 공간이 남음
        else if (tabIdx < n) {
            tab[tabIdx++] = arr[i];
            use[arr[i]] = 1;
            continue;
        }
 
 
        ret++; // 위 두가지 경우를 제외하고는 뽑을 수 밖에 없음.
 
        int port = 0;
        int farDistance = 0;
 
        //멀티탭에 꽂혀있는 것을 검사
        for (int j = 0; j < n; j++) {
            int distance = INF;
 
            for (int k = i + 1; k < nn; k++) {
                if (tab[j] == arr[k]) {
                    distance = k;
                    break;
                }
            }
 
            if (distance > farDistance) {
                port = j;
                farDistance = distance;
            }
        }
 
        //현재 꽂혀있는 것 중에 가장 먼 아이템을 포트에서 제거
        use[tab[port]] = 0;
        use[arr[i]] = 1;
        tab[port] = arr[i];
    }
 
    cout << ret;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[12845] 모두의 마블  (0) 2017.08.26
[12841] 정보대 등산  (0) 2017.08.23
[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27

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


기본적으로 네트워크 이론이 좀 필요한 문제입니다.


서브넷 마스크 & ip 주소 = 네트워크 주소


라는 것을 알아야하며..

가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

라는 조건이 중요합니다.


모든 ip에 대해서 공통된 부분을 찾습니다.

모든 ip에 대해서 공통된 부분(왼쪽 비트 부터 시작해서 오른쪽 비트로 갈 때)

만약 다른 부분이 있으면 멈춰야합니다.


ip에서 네트워크 주소나 서브넷을 따질 때

nnnn.nnnn.nnnn.nnhh

이런식으로 n은 이어져야합니다.(n은 네트워크 h는 호스트)


무튼... 기본 이론은 이러합니당..


공통된 부분은 전부 1로 가득채워서 서브넷 마스크를 구하면

서브넷 마스크 & 임의의 ip주소 = 네트워크 주소 를 출력할 수 있습니다.


코드입니다.


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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int ip[1000];
 
void print(int mask) {
    int shift = 24;
    for (int i = 0; i < 4; i++, shift -= 8) {
        cout << ((mask >> shift) & (1 << 8) - 1);
        if (i != 3) cout << '.';
    }
    cout << '\n';
}
 
int main() {
    int n;
    cin >> n;
 
    //ip입력받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            int a;
            cin >> a;
            ip[i] <<= 8;
            ip[i] |= a;
            getchar();
        }
    }
 
    //서브넷
    int subnet = 0;
 
    //0번째 ip와 틀린부분 찾기
    //찾으면 탈출해서 틀린부분 전까지는 전부 1로 채우기.
    for (int i = 31; i >= 0; i--) {
        int bit = 1 << i;
        bool end = 0;
 
        for (int j = 1; j < n; j++) {
            if ((ip[0] & bit) != (ip[j] & bit)) {
                end = 1;
                break;
            }
        }
 
        if (end) break;
        else subnet |= bit;
    }
 
    //네트워크 주소 출력하기
    print(ip[0] & subnet);
    //서브넷 주소 출력하기
    print(subnet);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 비트마스크' 카테고리의 다른 글

[1322] X와 K  (0) 2017.08.01
[13701] 중복 제거  (1) 2017.07.06

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


범위 안보고 그냥 풀었다가 시간초과...ㅎㅎㅎㅎ...

K값이 20억까지인데 그렇다면 K의 시간으로는 해결할 수 없습니다.


X + Y = X | Y

+연산과 OR연산이 같을 조건은

생각해보면 금방 알 수 있습니다.


OR은

0 0 0

0 1 1

1 0 1

1 1 1


입니다.


그러므로 X를 비트로 바꿨을 때 0인 digit??을 1로 바꿔준다면 같아질 수 있습니다.


예를 들어 보겠습니다.


1001(9)라는 수가 있습니다.

이 이진수에 2 혹은 4 혹은 6 등등을 더하면 덧셈과 OR연산이 같아지는 것을 볼 수 있습니다.

2 -> 10

4 -> 100

6 -> 110


아 그렇다면 0인 부분(부분? 자리??)에서 K번째 수를 찾으면 된다는 이야기입니다.


위에서 예를들면 K = 1이면 2가 되고, 2라면 4가 됩니다. 3이라면 6이됩니다.

4라면 16이 되겠지요.


00000000000000000000001001이라는 수는 9인데 이 비트들에서 1을 제외하고 K번쨰 수 인 값을 찾으면 되는 것입니다.


주의할 것은 쉬프트 연산을 할 때 롱롱으로 캐스팅하는 것을 잊으면 안됩니다.(엄청 틀렸음..ㅠㅠ)


코드입니다.


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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main() {
    long long x, k;
    cin >> x >> k;
 
    bool binX[64] = { 0, };
    bool binK[64] = { 0, };
 
    int i = 0;
 
    //2진수로 바꿔서 배열에 저장(2진수 리버스임)
    while (x || k) {
        binX[i] = x % 2;
        binK[i] = k % 2;
        x /= 2;
        k /= 2;
        i++;
    }
 
    int ki = 0;
    int xi = 0;
    long long ret = 0;
 
    while (ki < i) {
        //0인 비트를 해당 자리 수 만큼 쉬프트한다.
        if (binX[xi] == 0) {
            ret |= (1LL << xi) * binK[ki++];
        }
        xi++;
    }
    
    cout << ret;
    
    return 0;
}
 
 
cs


저작자표시

'알고리즘 > 비트마스크' 카테고리의 다른 글

[2064] IP 주소  (0) 2017.08.01
[13701] 중복 제거  (1) 2017.07.06

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


이 문제는 재귀로 쉽게 해결할 수 있습니다.


문제 해결 순서는


1. 해당 범위의 값이 같은지 확인한다.

2. 1에서 같으면 그 값을 출력한다.

3. 1에서 다르면 '('를 출력하고 재귀를 통해 해당 영역을 4개로 나눈다.

4. 재귀로 들어가서 1 ~ 3까지 순서를 반복한다.

5. 재귀호출이 끝나고 ')'를 출력한다.


풀 코드입니다.

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
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[1 << 6][1 << 6 + 1];
 
bool isSame(int x1, int y1, int x2, int y2) {
    char tmp = map[x1][y1];
 
    for (int i = x1; i <= x2; i++) {
        for (int j = y1; j <= y2; j++) {
            if (tmp != map[i][j]) return 0;
        }
    }
 
    return 1;
}
 
void f(int x1, int y1, int x2, int y2) {
 
    if (isSame(x1, y1, x2, y2)) cout << map[x1][y1];
    else {
        cout << '(';
        int midX = (x1 + x2) / 2;
        int midY = (y1 + y2) / 2;
 
        f(x1, y1, midX, midY);
        f(x1, midY + 1, midX, y2);
        f(midX + 1, y1, x2, midY);
        f(midX + 1, midY + 1, x2, y2);
        cout << ')';
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) cin >> map[i];
    
    f(0, 0, n - 1, n - 1);
    
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[12841] 정보대 등산  (0) 2017.08.23
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27
[14649] 문홍안  (0) 2017.07.27

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


처음에

모든 친구들에 대해서 만족하는 점을 찾으면 되겠다고 생각했습니다.

그래서 이분탐색으로 접근을 했습니다.

하지만 1차원 선상에서 소수(double)에서도 모일 수 있으므로

이분탐색을 사용하기가 애매했습니다.


그래서 다시 생각했는데 

구현하는 것이 정말 단순했습니다.


그냥 N의 시간으로 가면서 모든 학생들이 모일 수 있는 포인트로 좁혀가다가

그 포인트에 벗어나는 학생이 있으면 홍수에 당하는 것이고 아니라면 만날 수 있는 것이라고 생각했습니다.


minPos와 maxPos가 모든 학생들이 접근할 수 있는 범위입니다.


for문안에서 left와 right는 시간 * 속력으로 이동할 수 있는 거리를 구하여 현재 위치에서 더하고 빼서 

움직일 수 있는 범위를 나타냅니다.


첫번째 if문이 있는 경우가 아니라면 모일 수 있는 것입니다.


풀코드입니다.

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 <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
 
pii v[(int)5e5];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    double t;
 
    cin >> n >> t;
 
    for (int i = 0; i < n; i++) {
        cin >> v[i].first ;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> v[i].second;
    }
 
    double minPos = 0, maxPos = INF;
 
    for (int i = 0; i < n; i++) {
        double left = v[i].first - v[i].second * t;
        double right = v[i].first + v[i].second * t;
 
        if (maxPos < left || right < minPos) {
            puts("0");
            return 0;
        }
        
        maxPos = min(maxPos, right);
        minPos = max(minPos, left);
    }
 
    puts("1");
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30
[1913] 달팽이  (0) 2017.07.27
[14649] 문홍안  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24

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


이 문제는 사실 N이 크지 않아서

숫자 1이 있는 곳 부터 차례대로 배열에 숫자를 채워나가도 됩니다.


하지만 저는 y=x와 y=-x의 직선으로 4칸으로 나눠서 문제를 해결했습니다.


toNum()함수를 사용하면 1의 시간으로 해당 위치의 숫자를 찾아낼 수 있습니다.


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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int abs(int n) {
    return n >= 0 ? n : -n;
}
 
int toNum(int i, int j) {
    if (abs(i) <= j) return 4 * j * j - j + i + 1;
    else if (abs(i) <= -j) return 4 * j * j - 3 * j - i + 1;
    else if (abs(j) <= -i) return 4 * i * i + 3 * i + j + 1;
    else return 4 * i * i + i - j + 1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    n /= 2;
 
    int k;
    cin >> k;
 
    pii pos;
 
    for (int i = -n; i <= n; i++) {
        for (int j = -n; j <= n; j++) {
            //toNum함수를 이용하여 1의 시간으로 해당 좌표의 숫자를 알아낼 수 있음.
            int ret = toNum(i, j);
            cout << ret << ' ';
 
            //입력받은 k와 같으면 pos변수에 저장
            if (ret == k) {
                pos.first = i, pos.second = j;
            }
        }
        cout << '\n';
    }
 
    cout << pos.first + n + 1 << ' ' << pos.second + n + 1;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29
[14649] 문홍안  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13

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


단순 구현 문제입니다.


N이 100이기 때문에 시간복잡도 N^2으로 해결할 수 있습니다.


그냥 한번씩 다 밟아보면서 카운트하고

mod를 이용하여 어떤 색인지 판별하면 되겠습니다.


코드입니다.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int pos[100];
char direct[100];
 
int cnt[101];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int p;
    cin >> p;
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> direct[i];
    }
 
    //N^2의 복잡도로 돌 
    for (int i = 0; i < n; i++) {
        int d = (direct[i] == 'L' ? -1 : 1);
 
        for (int j = pos[i] + d; j > 0 && j <= 100; j += d) {
            cnt[j]++;
        }
    }
 
    int b, r, g;
    b = r = g = 0;
    
    //나머지 연산을 이용하여 개수 체킹
    for (int i = 1; i <= 100; i++) {
        int mod = cnt[i] % 3;
        if (mod == 0) b++;
        else if (mod == 1) r++;
        else g++;
    }
 
    //2자리로 고정하기
    cout << fixed;
    cout.precision(2);
    cout << ((double)b / 100) * p << '\n';
    cout << ((double)r / 100) * p << '\n';
    cout << ((double)g / 100) * p << '\n';
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13
[5527] 전구 장식  (0) 2017.07.05

+ Recent posts

티스토리툴바