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


LIS 문제입니다.

꼬이지 않으려면 내가 연결한 전봇대 보다 번호가 더 큰 전봇대만 선택해야하기 때문입니다.

N^2의 방법으로 해결하려고 했으나,  N이 너무 큽니다.


NlogN으로 해결하는 Lower Bound LIS로 해결해야합니다.

저도 처음해봤는데..


우선 로워바운드는 해당 숫자 이상의 수 중에서 가장 가까운 인덱스를 리턴하는 함수입니다.

(정렬이 되어있을 떄만 가능합니다. 이분 탐색을 응용한 것이기 떄문입니다.)


a배열은 입력들어오는 배열이고

b배열은 정렬된 수가 들어가 있는 배열입니다.

주의할 점은 b배열이 lis의 부분수열이 들어가있는 배열이 아니라는 점입니다.


로워 바운드는 자기보다 작거나 같은 경우 b배열에서 수행해서 자기의 위치를 찾아서 대입합니다.


예를 들어 10 20 30 1 2 3 4 5

라는 수열이 있으면


b배열에 10 20 30 이렇게 들어갈 것입니다.

허나 1을 만나면 10 20 30 이 들어있는 수열에서

로워바운드를 하여 자기 이상의 수 중 가장 인덱스를 찾겠죠.

네 value:10, idx:0 입니다.

그러면 b 배열은 1 20 30으로 바뀌게 됩니다.


또 2를 만나면 자기보다 큰 수를 찾겠죠. 네 20입니다.

1 2 30 으로 바뀌게 됩니다.


3을 만나면

1 2 3으로 바뀌겠죠.

4와 5는 b배열의 3보다 크므로 그냥 삽입하면 됩니다.


b배열은 1 2 3 4 5가 완성이 됩니다.

결국 lis값은 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
#include <stdio.h>
 
using namespace std;
int a[(int)1e5];
int b[(int)1e5];
 
int lower_bound(int s, int e, int value) {
    
    while (s <= e) {
        int mid = (s + e) / 2;
 
        if (b[mid] >= value) e = mid - 1;
        else s = mid + 1;
    }
 
    return s;
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
        
    int size = 1;
    b[0] = a[0];
    
    for (int i = 1; i < n; i++) {
        if (b[size - 1] < a[i]) {
            b[size] = a[i];
            size++;
            continue;
        }
 
        b[lower_bound(0, size - 1, a[i])] = a[i];
    }
    
    printf("%d", n - size);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1890] 점프  (0) 2017.09.15
[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

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


가장 쉬운 bfs문제입니다.

최소의 칸 수를 구하라? 즉 bfs를 이용해서 가장 먼저 도달하는 너비를 출력하라는 말입니다.

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
#include <stdio.h>
 
const int QUEUE_SIZE = 100 * 100 * 4;
 
typedef struct qs {
    int x, y, b;
}qs;
 
 
typedef struct queue {
    qs data[QUEUE_SIZE];
    int front, rear;
 
    queue() {
        front = rear = 0;
    }
 
    int empty() {
        return front == rear;
    }
 
    void push(qs d) {
        rear = (rear + 1) % QUEUE_SIZE;
        data[rear] = d;
    }
 
    qs pop() {
        front = (front + 1) % QUEUE_SIZE;
        return data[front];
    }
}queue;
 
 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
char map[100][100];
int visit[100][100];
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
 
    getchar();
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    queue q;
    q.push(qs{0, 0, 1});
    visit[0][0] = 1;
    
    while (!q.empty()) {
        qs front = q.pop();
 
        if (front.x == m - 1 && front.y == n - 1) {
            printf("%d", front.b);
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            int nx = front.x + dx[i];
            int ny = front.y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
            if (map[nx][ny] == '0') continue;
 
            visit[nx][ny] = 1;
            q.push(qs{ nx, ny, front.b + 1 });
        }
 
    }
 
    return 0;
}
cs


저작자표시

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

[2667] 단지번호붙이기  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


이 문제는 어렵지 않았습니다.

dp라고 알 수 있는 부분은 이 문제가 경우의 수이고, 정답이 2^63이라면 DP를 제외하고는 시간안에 풀 수 없습니다.


dp라는 것만 안다면 어렵지 않은 문제입니다.


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
#include <iostream>
 
using namespace std;
 
typedef long long ll;
 
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
 
int map[100][100];
ll dp[100][100];
 
int n;
 
ll f(int x, int y) {
    if (x == n - 1 && y == n - 1) {
        return 1;
    }
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i] * map[x][y];
        int ny = y + dy[i] * map[x][y];
        if (nx >= n || ny >= n) continue;
 
        ret += f(nx, ny);
    }
 
    return ret;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
 
    cout << f(0, 0);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1365] 꼬인 전깃줄  (0) 2017.09.16
[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

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


STL을 자꾸 쓰니까 실력이 줄어드는 것 같아서..

STL없이 구현해보려고 노력하고 있습니다.


동서남북으로 연결된 지역은 같은 단지로 취급합니다.

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
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <string>
 
using namespace std;
 
string map[25];
bool visit[25][25];
 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int n;
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int dfs(int x, int y) {
    if (visit[x][y]) return 0;
    visit[x][y] = 1;
 
    int ret = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || ny < 0 || nx >= n || ny >= n || map[nx][ny] == '0') continue;
        ret += dfs(nx, ny);
    }
 
    return ret;
}
 
void sort(int *arr, int size, int value) {
    int i = size - 1;
    while (i >= 0 && arr[i] > value) {
        arr[i + 1] = arr[i];
        i--;
    }
 
    arr[++i] = value;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
 
    int ret = 0;
    int cnt[25 * 25];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == '0') continue;
 
            int tmp = dfs(i, j);
            if (tmp) {
                sort(cnt, ret, tmp);
                ret++;
            }
        }
    }
 
    cout << ret<<'\n';
 
    for (int i = 0; i < ret; i++) {
        cout << cnt[i] << '\n';
    }
 
    return 0;
}
cs


저작자표시

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

[2178] 미로 탐색  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


입력 받은 N의 쌍을 먼저 만듭니다.


ex) N = 30 이라면.. (1, 30) ... (30, 1) 까지의 쌍이 있겠죠

하지만 (1, 30) (30, 1)은 같은 쌍이고, (2, 15), (15, 2)는 같은 쌍입니다.


그렇기 때문에 sqrt(N)까지만 쌍을 만들면 해결할 수 있습니다.


여기서 주의할 것은 약수라고 무조건 카운트하면 안됩니다.

두 쌍의 최대공약수가 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
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int test;
    cin >> test;
 
    while (test--) {
        int n;
        cin >> n;
 
        int ret = 0;
 
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0 && get_gcd(i, n / i) == 1) {
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 수학' 카테고리의 다른 글

[2436] 공약수  (2) 2017.09.01
[1740] 거듭 제곱  (0) 2017.06.21

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


LIS문제라는 것을 눈치채지 못한 저는 바보입니다.


LIS입니다..


전형적인 DP문제죠...


dp[n] : 인덱스 n까지의 최대 연결 수


라고 정의하면 됩니다.


이렇게 하면 N^2의 시간복잡도로 해결할 수 있습니다.


관련 문제..

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

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


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 <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int edge[501];
int dp[501];
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a] = b;
    }
 
    int ret = 0;
 
    for (int i = 1; i <= 500; i++) {
        if (edge[i] == 0) continue;
 
        dp[i] = 1;
 
        for (int j = 1; j < i; j++) {
            if (edge[j] < edge[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
 
        ret = max(ret, dp[i]);
    }
    
    cout << n - ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1365] 꼬인 전깃줄  (0) 2017.09.16
[1890] 점프  (0) 2017.09.15
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

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


문제에서 인풋으로 GCD와 LCM을 줍니다.

우리는 그렇다면

어떤 수 a, b가 있다고 존재할 때

A = a / GCD

B = b / GCD

라고 한다면


LCM = GCD * A * B

라는 것을 알 수 있습니다.


여기서 가장 중요한 조건 ! A와 B는 서로소여야만 한다는 것입니다.

서로소라는 것은 두 수는 약수를 1만을 가진다는 것인데요.


이 조건을 만족하지 않으면 A와 B는 후보가 될 수 없습니다.

예륻 들어 GCD가 4라는 인풋이 들어왔는데 A가 2 B가 4라면

더 나눌 수 있는 수가 존재하므로 후보가 아니라는 말이죠.


그 외에는 어려운 부분은 없었습니다.

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 <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    int gcd, lcm;
    cin >> gcd >> lcm;
 
    int tmp = lcm / gcd;
 
    int left = 0, right = 0;
 
    for (int i = 1; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            if (get_gcd(i, tmp / i) == 1) {
                left = i;
                right = tmp / i;
            }
        }
    }
 
    if (left > right) swap(left, right);
 
    cout << left * gcd << ' ' << right * gcd;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 수학' 카테고리의 다른 글

[13412] 서로소 쌍  (0) 2017.09.07
[1740] 거듭 제곱  (0) 2017.06.21

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


문제 이해를 잘못해서.. 해결하는데 엄청난 시간이 걸렸습니다.


이 문제는 (0, 0)에서 입력 받은 K이하의 노드를 거쳐서  (10000, 10000)으로 이동할 때 드는 연료의 최대값의 최솟값을 구하는 문제입니다.


(0, 0)을 A라고 가정하고 (10000, 10000)을 D라고 가정했을 때, A - B(임의의 노드)로 가는 연료가 1000이고 B - C(임의의 노드)로 가는 연료가 100이라면


A - B구간에서 1000만큼 필요했으므로 답은 1000이 나와야합니다.


이것을 모든 노드에 대해서 실행해보면 됩니다.


이분탐색을 이용해서 해당 비용만을 이용해서 (0, 0)에서 (10000, 10000) 목적지로 이동할 수 있는지를 계속해서 실행하면 됩니다.(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
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
vii pos;
bool visit[(int)1e3 + 2];
 
int d(pii a, pii b) {
    int x = b.first - a.first;
    int y = b.second - a.second;
 
    return (int)ceil(sqrt(x * x + y * y) / 10);
}
 
bool bfs(int max_cost, int n, int k) {
    memset(visit, 0, sizeof(visit));
 
    queue<pii> q;
    q.push(mp(0, 0)); // from, k
 
    while (!q.empty()) {
        int from = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (from == pos.size() - 1) {
            if (cnt <= k + 1) return 1;
            else return 0;
        }
 
        for (int i = 1; i < pos.size(); i++) {
            if (visit[i]) continue;
 
            if (d(pos[i], pos[from]) <= max_cost) {
                visit[i] = 1;
                q.push(mp(i, cnt + 1));
            }
        }
    }
    
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    pos.push_back(mp(0, 0));
 
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
 
        pos.push_back(mp(a, b));
    }
 
    pos.push_back(mp(1e4, 1e4));
 
    int left = 1, right = d(mp(0, 0), mp(1e4, 1e4));
 
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (bfs(mid, n, k)) right = mid - 1;
        else left = mid + 1;
    }
 
    cout << left;
 
    return 0;
}
cs


저작자표시

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

[12842] 튀김 소보루  (0) 2017.08.23
[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19

+ Recent posts

티스토리툴바