BOJ : https://www.acmicpc.net/problem/2623

 

 
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
#include <cstdio>
#include <vector>
using namespace std;
 
vector<int> v[1001];
vector<int> seq;
int N, M, many, arr[101][1001];
int check[1001];
bool check_false;
 
void finder(int start) {
    if (check[start] == 1)
        return;
 
    for (int i = 0; i < v[start].size(); i++) {
        if (check[v[start][i]] == 1)
            continue;
        else if (check[v[start][i]] == 2) {
            check_false = true;
            return;
        }
        else {
            check[v[start][i]] = 2;
            finder(v[start][i]);
            if (check_false == true)
                return;
        }
    }
 
    seq.push_back(start);
    check[start] = 1;
 
}
 
 
int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        scanf("%d", &many);
        for (int j = 0; j < many; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 1000; j++) {
            if (arr[i][j] == 0) break;
            int num = arr[i][j];
            for (int k = 0; k < j; k++) {
                bool check_insert = false;
                for (int a = 0; a < v[num].size(); a++) {
                    if (v[num][a] == arr[i][k]) {
                        check_insert = true;
                        break;
                    }
                }
                if (check_insert == true)
                    continue;
                v[num].push_back(arr[i][k]);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        finder(i);
        if (check_false == true)
            break;
    }
 
    if (check_false == false) {
        for (int i = 0; i < N; i++) {
            printf("%d\n", seq[i]);
        }
    }
    else
        printf("0");
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

백준 2529번 : 부등호 Junnnho  (0) 2019.05.17
BOJ 2252번 줄세우기  (0) 2019.05.17
백준 : 1516번 - 게임 개발 Junnnho  (0) 2019.05.14
2568번 : 전깃줄2 - Junnnho  (0) 2019.04.08
BOJ 2352번 반도체 설계  (0) 2019.04.08

BOJ : https://www.acmicpc.net/problem/1516

 

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

문제 해결에 필요한 알고리즘 : 정렬

난이도 : 최하

 

힌트를 보니까 위상정렬이라고 적혀있던데

사실 위상정렬이 뭔지 모르고 개인적 방법으로 풀었다

위상정렬,,, 뭔지 모르겠다 몰라도 쉽게 금방 풀 수 있다

 

이 문제를 풀면서 처음 알게 된 사실인데

pair 안에 vector 컨테이너가 또 삽입될 수 있다는걸;

건물 번호를 벡터로 받아질 수 있을까 그냥 적어봤는데 되길래 엄청 신기했다

 

정렬 순서

1. 필요한 건물 순서대로 정렬

ex) 첫 벡터가 1 ,10, (4, 3, 2) 이렇게 온다면 1, 10, (2,3,4) 이런 식으로 정렬

 

2. 입력 전체 벡터를 필요 건물 순서의 벡터를 기준으로 서로 비교해가면서 정렬

ex)

2 4 5

2 3 4

----------

2 3 4

2 4 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
78
79
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, Array[501];
vector<pair<int, pair<int, vector<int> > > > arr;
 
bool cmp(pair<int, pair<int, vector<int> > > &a , pair<int, pair<int, vector<int> > > &b) {
    int len = min(a.second.second.size(), b.second.second.size());
    if (len == 0) {
        if (a.second.second.size() == b.second.second.size())
            return a.first < b.first;
        else
            return a.second.second.size() < b.second.second.size();
    }
    for (int i = 0; i < len; i++) {
            continue;
        else
            return a.second.second[i] < b.second.second[i];
    }
    if (a.second.second[len - 1] == b.second.second[len - 1])
        return a.first < b.first;
}
 
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        Array[i] = -1;
 
    for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &arr[i].second.first);
        arr[i].first = i+1;
        while (1) {
            scanf("%d", &num);
            if (num == -1) break;
            else {
                arr[i].second.second.push_back(num);
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        sort(arr[i].second.second.begin(), arr[i].second.second.end());
    }
 
    sort(arr.begin(), arr.end(), cmp);
    int N_size = N;
    while (1) {
        for (int i = 0; i < N; i++) {
            if (N_size == 0) break;
            int size = arr[i].second.first;
            int MAX = 0;
            bool check = false;
            if (Array[arr[i].first] == -1) {
                for (int j = 0; j < arr[i].second.second.size(); j++) {
                    if (Array[arr[i].second.second[j]] == -1) {
                        check = true;
                        break;
                    }
                    MAX = max(MAX, Array[arr[i].second.second[j]]);
                }
                if (check == false) {
                    size += MAX;
                    Array[arr[i].first] = size;
                    N_size--;
                }
            }
        }
        if (N_size == 0) break;
    }
 
    for (int i = 1; i <= N; i++)
        printf("%d\n", Array[i]);
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none; color:white">cs

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2252번 줄세우기  (0) 2019.05.17
백준 2623번 - 음악프로그램 Junnnho  (0) 2019.05.15
2568번 : 전깃줄2 - Junnnho  (0) 2019.04.08
BOJ 2352번 반도체 설계  (0) 2019.04.08
BOJ 2565번 전깃줄  (0) 2019.04.08

BOJ : https://www.acmicpc.net/problem/2568

 

2568번: 전깃줄 - 2

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 

www.acmicpc.net

문제 해결을 위한 알고리즘 : lis

2007년도 지역본선 중등부3번 문제

 

가장 긴 증가하는 부분수열4 : https://junho0956.tistory.com/9?category=825556 

이 문제에서 언급했듯이 lis 알고리즘의 문제점은 lis 배열의 정확한 값을 찾을 수 없다는 것이다.

그러므로 이 문제를 해결하기 위해서는 lis 알고리즘 뿐만 아니라 정확한 값을 찾아가는 추적 알고리즘이 필요하다.

 

lis 알고리즘을 사용하면 사용한 전깃줄에 대한 정보를 가지게 되므로,

사용하지 않은 전깃줄을 출력하기 위해서 bool의 visit 배열을 사용하였다.

 

방식은 일단 먼저 입력되는 전깃줄은 전부 true를 시킨 후에

lis 추적 알고리즘으로 사용된 전깃줄을 다시 false 시키면

결국 남아있게 되는 visit 배열의 true 값을 가진 인덱스가 사용하지 않은 전깃줄이 되게 된다.

 

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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<pair<int, int> > arr;
vector<pair<int, int> > v;
bool visit[500001];
int lis[500001];
int n, f, s, cnt, L;
 
int _lower_bound(int start, int end, int key) {
    int mid;
    while (start < end) {
        mid = (start + end) / 2;
        if (lis[mid] < key)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &f, &s);
        v.push_back(make_pair(f, s));
        visit[f] = true;
    }
    sort(v.begin(), v.end());
 
    lis[0] = v[0].second;
    arr.push_back({ 0,v[0].first });
 
    for (int i = 1; i < n; i++) {
        if (lis[L] < v[i].second) {
            lis[++L] = v[i].second;
 
            arr.push_back({ L,v[i].first });
        }
        else {
            int ans = _lower_bound(0, L, v[i].second);
            lis[ans - 1] = v[i].second;
 
            arr.push_back({ ans - 1, v[i].first });
            cnt++;
        }
    }
    
    for (int i = arr.size(); i >= 0; i--) {
        if (arr[i - 1].first == L) {
            L--, visit[arr[i - 1].second] = false;
        }
        if (L == -1) break;
    }
 
    printf("%d\n", cnt);
    for (int i = 1; i < 500001; i++) {
        if (visit[i] == true)
            printf("%d\n", i), cnt--;
        if (cnt == 0) break;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

위 소스는 직접 lower_bound를 만들어서 사용한 예제이고 아래는 algorithm 헤더로 함수를 바로 사용해본 소스이다.

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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<pair<int, int> > arr;
vector<pair<int, int> > v;
bool visit[500001];
vector<int> lis;
int n, f, s, cnt, L;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &f, &s);
        v.push_back(make_pair(f, s));
        visit[f] = true;
    }
    sort(v.begin(), v.end());
 
    lis.push_back(v[0].second);
    arr.push_back({ 0,v[0].first});
 
    for (int i = 1; i < n; i++) {
        if (lis[L] < v[i].second) {
            lis.push_back(v[i].second);
 
            arr.push_back({ ++L,v[i].first });
        }
        else {
            vector<int>::iterator ans = lower_bound(lis.begin(), lis.end(), v[i].second);
            int answer = lower_bound(lis.begin(), lis.end(), v[i].second) - lis.begin() + 1;
            *ans = v[i].second;
 
            arr.push_back({ answer - 1, v[i].first });
            cnt++;
        }
    }
    
    for (int i = arr.size(); i >= 0; i--) {
        if (arr[i - 1].first == L) {
            L--, visit[arr[i - 1].second] = false;
        }
        if (L == -1) break;
    }
 
    printf("%d\n", cnt);
    for (int i = 1; i < 500001; i++) {
        if (visit[i] == true)
            printf("%d\n", i), cnt--;
        if (cnt == 0) break;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

algorithm 헤더에 있는 lower_bound 의 사용법

1. iterator 을 사용하는 경우

auto or iterator x = lower_bound(start iterator, end iterator, key);

iterator을 사용하면 주소를 반환하게 된다.

2. index를 사용하는 경우

int val = lower_bound(start iterator, end iterator, key) - start iterator + 1;

이런식으로 사용하면 찾은 값의 인덱스를 return 값으로 반환하게 된다.

 

헤더파일을 사용하니 메모리 사용량이 감소하는 것으로 나타났다.

'algorithm > BOJ' 카테고리의 다른 글

백준 2623번 - 음악프로그램 Junnnho  (0) 2019.05.15
백준 : 1516번 - 게임 개발 Junnnho  (0) 2019.05.14
BOJ 2352번 반도체 설계  (0) 2019.04.08
BOJ 2565번 전깃줄  (0) 2019.04.08
BOJ 14501번 퇴사  (0) 2019.04.07

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

github : https://github.com/junho0956/Algorithm/blob/master/11568/11568/%EC%86%8C%EC%8A%A4.cpp

 

문제 해결을 위한 알고리즘 : lis, dp, greedy

lis 알고리즘을 이용하여 문제를 해결하였고

꼬이지않은 lis 배열 안에 들어간 size 가 최대한 연결할 수 있는 포트가 된다.

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef vector<int> LIS;
LIS lis;
int main() {
    int n, arr[40001], L;
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    L = 0, lis.push_back(arr[0]);
 
    for (int i = 1; i < n; i++) {
        if (arr[i] > lis[L])
            lis.push_back(arr[i]), L++;
        else {
            vector<int>::iterator ans = lower_bound(lis.begin(), lis.end(), arr[i]);
            *ans = arr[i];
        }
    }
 
    printf("%d", lis.size());
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습 20.02.10

'algorithm > BOJ' 카테고리의 다른 글

백준 : 1516번 - 게임 개발 Junnnho  (0) 2019.05.14
2568번 : 전깃줄2 - Junnnho  (0) 2019.04.08
BOJ 2565번 전깃줄  (0) 2019.04.08
BOJ 14501번 퇴사  (0) 2019.04.07
6603번 : 로또 - junnnho  (0) 2019.04.07

+ Recent posts

티스토리툴바