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


원형 큐입니다.


원형 큐를 이해하기 위해서는 %(나머지) 개념을 잘 이해하시면 됩니다.


empty : 큐가 비었음을 의미하는 함수입니다. front와 rear가 같다면 큐는 비어있는 것입니다.

full : (rear + 1) % MAX_SIZE == front라면 큐가 꽉차 있음을 의미합니다.


다른 부분은 일반 큐와 같습니다.


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
#include <stdio.h>
 
#define MAX_SIZE 100
 
typedef struct round_queue {
    int queue[MAX_SIZE];
    int front, rear;
    int size;
 
    round_queue() {
        size = 0;
        front = 0;
        rear = 0;
    }
 
    int empty() {
        return front == rear;
    }
 
    int push(int value) {
        if ((rear + 1) % MAX_SIZE == front) {
            return 0;
        }
        size++;
        rear = (rear + 1) % MAX_SIZE;
        queue[rear] = value;
    }
 
    int pop() {
        if (empty()) {
            return -1;
        }
        size--;
        front = (front + 1) % MAX_SIZE;
        return queue[front];
    }
}round_queue;
 
 
int main(int argc, char* argv[])
{
    int T, N;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
 
        round_queue rq;
 
        for (int i = 0; i < N; i++)
        {
            int value;
            scanf("%d", &value);
            rq.push(value);
        }
 
        printf("#%d\n", test_case);
        while(!rq.empty()) printf("%d ", rq.pop());
    
        printf("\n");
    }
 
    return 0;
}
 
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[1918] 후위표기식  (0) 2017.11.27
[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
[2263] 트리의 순회  (1) 2017.08.27
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13

C언어의 구조체를 이용해서 우선순위 큐를 만들었습니다.


구조체는 아래처럼 정의했습니다.

1
2
3
4
5
6
7
8
9
typedef struct priority_queue {
    int heap[MAX_SIZE];
    int size;
    priority_queue();
    void swap(int *a, int *b);
    int push(int value);
    int pop();
    int empty();
}
cs


데이터를 저장할 heap과

heap의 사이즈를 나타낼 변수

그리고 데이터 swap함수

우선순위큐 push, pop, empty


입니다.


최대 힙으로 구현했고, 최소 힙은 부등호만 바꿔주면 됩니다.

양수에 대해서만 작동하는 힙입니다. 이유는 pop할 때 size == 0이면 -1을 리턴하게 했기 때문입니다.


input)

2

10

10 49 38 17 56 92 8 1 13 55

13 

4 22 50 13 5 1 22 35 21 7 99 100 14


출력결과)

2

10

10 49 38 17 56 92 8 1 13 55

#1

92 56 55 49 38 17 13 10 8 1

13

4 22 50 13 5 1 22 35 21 7 99 100 14

#2

100 99 50 35 22 22 21 14 13 7 5 4 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
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
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
 
#define MAX_SIZE 100
 
typedef struct priority_queue {
    int heap[MAX_SIZE];
    int size;
 
    priority_queue() {
        size = 0;
    }
 
    void swap(int *a, int *b) {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
 
    int push(int value) {
        if (size + 1 > MAX_SIZE) {
            return 0;
        }
 
        heap[size] = value;
 
        int current = size;
        int parent = (size - 1) / 2;
 
        while (current > 0 && heap[current] > heap[parent]) {
            swap(&heap[current], &heap[parent]);
            current = parent;
            parent = (parent - 1) / 2;
        }
 
        size++;
 
        return 1;
    }
 
    int pop() {
        if (size <= 0) return -1;
 
        int ret = heap[0];
        size--;
 
        heap[0] = heap[size];
        int current = 0;
        int leftChild = current * 2 + 1;
        int rightChild = current * 2 + 2;
        int maxNode = current;
 
        while (leftChild < size) {
            if (heap[maxNode] < heap[leftChild]) {
                maxNode = leftChild;
            }
            if (rightChild < size && heap[maxNode] < heap[rightChild]) {
                maxNode = rightChild;
            }
 
            if (maxNode == current) {
                break;
            }
            else {
                swap(&heap[current], &heap[maxNode]);
                current = maxNode;
                leftChild = current * 2 + 1;
                rightChild = current * 2 + 2;
            }
        }
        
        return ret;
    }
 
    int empty() {
        if (size == 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}priority_queue;
 
 
int main(int argc, char* argv[])
{
    int T, N;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
 
        priority_queue pq;
 
        for (int i = 0; i < N; i++)
        {
            int value;
            scanf("%d", &value);
            pq.push(value);
        }
 
        printf("#%d\n", test_case);
        while(!pq.empty()) printf("%d ", pq.pop());
    
        printf("\n");
    }
 
    return 0;
}
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[1918] 후위표기식  (0) 2017.11.27
[C언어] 원형 큐(라운드 큐)  (0) 2017.09.07
[2263] 트리의 순회  (1) 2017.08.27
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13

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

+ Recent posts

티스토리툴바