'알고리즘/백준' 카테고리의 글 목록 (7 Page)

알고리즘/백준

백준 2565 전깃줄 쉬운 풀이(C++/CPP) 2021.02.15
백준 1946 신입 사원 2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP) 2021.02.14
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) 2021.02.14
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) 2021.02.14
백준 11657 타임머신 쉬운 풀이(C++/CPP) 2021.02.14
백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) 2021.02.14
백준 11780 플로이드2 풀이(C++/CPP) 2021.02.08
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP) 2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP) 2021.02.07

백준 2565 전깃줄 쉬운 풀이(C++/CPP)

2021. 2. 15. 23:00

문제링크 : https://www.acmicpc.net/problem/2565

문제 추상화

DP로 LCS를 구하는 문제
- LCS : 붙어있지 않고도 점점 증가하는 수열의 최대 개수
- 참조 : https://www.acmicpc.net/problem/9251
LCS인 이유
- 전깃줄이 교차하지 않아야함
- A이나 B중 하나를 정렬하면
- 전깃줄이 교차하지 않으면 나머지 것이 순차적으로 증가와 같음

아이디어

DP로 LCS 풀기
- DP[i] = i번째 위치에서 LCS 개수
- 처음에 DP[i]를 1로 초기화
- DP[i] = for(j=0~i-1) if(num[i] > num[j]) DP[i] = max(Dp[i], DP[j]+1)

시간복잡도 계산

O(N^2) : 1e4
만약 숫자 클경우 이진탐색을 통해서 풀경우 O(NlgN)으로 가능

인트 계산

전깃출 최대 100
위치 최대 500
모두 INT 사용 가능

코드

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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
pair<int, int> nums[110];
int dp[110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(dp, dp+110, 1);
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        nums[i] = make_pair(a,b);
    }
    
    sort(nums, nums+N);
    int maxv= 1;
    for(int i=1; i<N; i++) {
        for(int j=0; j<i; j++) {
            if(nums[i].second > nums[j].second) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxv = max(maxv, dp[i]);
    }
    
    cout << N-maxv << '\n';
    
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

끝에서부터 시작하는 DP
- DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
- 특히 2차원에서 상하좌우를 모두 고려해줘야할 때

비슷한 문제

DP - LCS

'알고리즘 > 백준' 카테고리의 다른 글

백준 1107 리모컨 (1)	2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP) (0)	2021.02.15
백준 1946 신입 사원 (0)	2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP) (0)	2021.02.14
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0)	2021.02.14

백준 1946 신입 사원

2021. 2. 15. 22:41

문제링크 : https://www.acmicpc.net/problem/1946

문제 접근

문제를 추상화 하면
- A와 B 과목에서 하나라도 다른 사람에 비해 떨어지면 안됨
모두 떨어지는 경우를 구하는게 쉬울듯
접근 1 : 각 노드당 모든 노드를 순회하면서 모두 떨어지는 경우를 구할경우
- O(N^2) > e10 시간초과
접근 2 : 하나를 기준으로 나머지 값의 최소값을 갱신
- A,B 과목이 있을때 A 과목을 기준으로 정렬
- A과목의 순위가 가장 높은 지원자의 B과목 순위를 최소값의 초기 셋팅
- A과목 순위가 낮은 것들을 순회
  - A 과목 순위가 낮기 때문에, B과목은 더 순위가 높아야함
  - B과목의 순위를 최소값으로 갱신하면서 순회

시간복잡도 계산

테스트케이스 : T
A과목을 기준으로 정렬 : NlgN
모든 지원자 순회 : N
시간복잡도 : O(T * (NlgN + N)) = O(TNlgN) =20* 1e5 * 20 = 4e7

인트 계산

면접 지원자숫자 최대 1e6 > 인트 가능

코드

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

#include <iostream>
#include <algorithm>
 
using namespace std;
 
pair<int, int> people[100010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T;cin >> T;
    while(T--) {
        int N; cin >> N;
        for(int i=0; i<N; i++) {
            int a,b; cin >> a >> b;
            people[i] = make_pair(a,b);
        }
        
        sort(people, people+N);
        
        int minv= people[0].second;
        int cnt=0;
        for(int i=1; i<N; i++) {
            // A과목 순위가 높은 사람의 B과목 순위도 순위가 높다면 카운트
            if(minv < people[i].second) {
                cnt++;
            }
            // 최소 순위 갱신, 왜냐하면 다음 사람은 최대값과 비교
            minv = min(minv, people[i].second);
        }
        
        cout << N-cnt << '\n';
    }
    return 0;
}
 
Colored by Color Scripter

cs

문제유형

그리디 - 두과목 모두 낮은 경우
- A 과목을 기준으로 정렬한 후
- A가 가장 높은 사람의 B 점수를 기록
- A 과목을 순회하면서 B점수를 보다 높은값으로 갱신하며
- 두과목 모두 낮은 경우 조회

'알고리즘 > 백준' 카테고리의 다른 글

백준 2143 두 배열의 합 쉬운 풀이(C++/CPP) (0)	2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP) (0)	2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP) (0)	2021.02.14
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0)	2021.02.14

백준 1937 욕심쟁이 판다 풀이(C++/CPP)

2021. 2. 14. 18:41

문제링크 : https://www.acmicpc.net/problem/1937

문제 접근

각 노드에서 DFS로 모든 경우의 수 사용할 경우
- 모든 노드 : O(N^2)
- 각 노드에서 DFS할경우, O(V+E) : O(N^2 + 4 * N^2) : O(5*N^2)
- O(N^2 * 5N^2) = O(5N^4) = 5*625 * e8 > 시간초과
  - DP를 사용, 각 노드 : 판다가 최대한 살수 있는 일수
- 각 노드에서 값 구하기 위해 DFS 사용
- 4방향에서 현재보다 값 작을경우, DP 값있으면 반환하고, 없으면 다시 DFS
- O(V+E) : O(5*N^2)

시간복잡도 계산

DP 사용하면, 가장 높은 값을 갖는곳으로부터 DFS 한것과 같은 효과
- O(V+E) = O(N^2 + 4N^2) = O(5*N^2)

인트 계산

대나무 양 : 1e6보다 작음 > INT 가능
DP 값 : 25e4보다 작음 > 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
#include <iostream>
 
using namespace std;
 
int map[510][510];
int dp[510][510];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int get_dp(int y, int x) {
    if(dp[y][x] != 0) return dp[y][x];
    
    int rs=0;
    for(int k=0; k<4; k++) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        if(map[y][x] < map[ny][nx]) rs = max(rs, get_dp(ny, nx));
    }
    
    return dp[y][x] = rs+1;
}
int main() {
    int N; cin >> N;
    
    fill(&dp[0][0], &dp[509][510], 0);
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            cin >> map[j][i];
        }
    }
    
    int rs=0;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            rs = max(rs, get_dp(j,i));
        }
    }
    
    cout << rs << '\n';
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

DP - DFS
- DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
- 특히 2차원에서 상하좌우를 모두 고려해줘야할 때

비슷한 문제

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

'알고리즘 > 백준' 카테고리의 다른 글

백준 2565 전깃줄 쉬운 풀이(C++/CPP) (0)	2021.02.15
백준 1946 신입 사원 (0)	2021.02.15
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11657 타임머신 쉬운 풀이(C++/CPP) (0)	2021.02.14

백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP)

2021. 2. 14. 18:20

문제링크 : https://www.acmicpc.net/problem/10999

문제 접근

세그먼트 트리 응용 문제
- 세그먼트 트리 기본 개념: https://dev-jango.tistory.com/30
- 수정이 구간으로 이루어질경우 lazy 사용
- lazy : 해당 노드에 대해서 업데이트 해줘야 할 값
- 해당 노드를 조회하거나 업데이트처럼 직접 사용할때 한번에 처리
- 그 전까지는 작업을 뒤로 미뤄둠

시간복잡도 계산

처음 세그먼트 트리 생성 : N * lgN
M+K번 의 수정 및 출력 : (M+K)*lgN
O((N+M+K) * lgN) = 1e6 * 20 = 2e7

인트 계산

세그먼트 트리 값 : 최대값인 2^63이 1e6개 있을경우 제일 상단값은 2^63 * 1e6 = e18 * e6 = e24 >> long long
입력으로 들어오는값 모두 최대 2^63 > long long

코드

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
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
vector<ll> lazy;
ll nums[1000010];
 
ll make(int node, int st, int en) {
    if(st==en) return tree[node] = nums[st];
    
    int mid = (st+en)/2;
    ll rsl = make(node*2, st, mid);
    ll rsr = make(node*2+1, mid+1, en);
    
    return tree[node] = rsl + rsr;
}
 
// 해당 노드에 있는 lazy를 적용하고 lazy를 비워줌
void lazy_update(int node, int st, int en) {
    if(lazy[node] != 0) {
        tree[node] += (en-st+1) * lazy[node];
        
        if(st != en) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        
        lazy[node] = 0;
    }
}
 
void update(int node, int st, int en, int li, int ri, ll diff) {
    // lazy 업데이트 먼저 수행
    lazy_update(node, st, en);
    
    if(ri < st || en < li) return;
    if(li <= st && en <= ri) {
        // 구하려는 구간 안에 노드가 있으면 업데이트 반영
        tree[node] += (en-st+1) * diff;
        if(st != en) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    
    int mid = (st+en)/2;
    update(node*2, st, mid, li, ri, diff);
    update(node*2+1, mid+1, en, li, ri, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
}
 
ll sumt(int node, int st, int en, int li, int ri) {
    lazy_update(node, st, en);
    if(ri < st || en < li) return 0;
    if(li <= st && en <= ri) return tree[node];
    
    int mid = (st+en)/2;
    ll rsl = sumt(node*2, st, mid, li, ri);
    ll rsr = sumt(node*2+1, mid+1, en, li, ri);
    return rsl + rsr;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M,K; cin >> N >> M >> K;
    
    
    for(int i=0; i<N; i++) cin >> nums[i];
    
    // tree, lazy, 초기화
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    lazy.resize(1<<(h+1));
    
    make(1,0,N-1);
    
    for(int i=0; i<M+K; i++) {
        int a,b,c; cin >> a >> b >> c;
        if(a==1) {
            ll d; cin >> d;
            update(1,0,N-1,b-1,c-1,d);
        } else {
            cout << sumt(1,0,N-1,b-1,c-1) << '\n';
        }
        
        
    }
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

세그먼트 트리 - lazy

'알고리즘 > 백준' 카테고리의 다른 글

백준 1946 신입 사원 (0)	2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP) (0)	2021.02.14
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11657 타임머신 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) (0)	2021.02.14

백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP)

2021. 2. 14. 17:53

문제링크 : https://www.acmicpc.net/problem/2042

문제 접근

세그먼트 트리 문제 : https://dev-jango.tistory.com/30

시간복잡도 계산

처음 세그먼트 트리 생성 : N * lgN
M+K번 의 수정 및 출력 : (M+K)*lgN
O((N+M+K) * lgN) = 1e6 * 20 = 2e7

인트 계산

세그먼트 트리 값 : 최대값인 2^63이 1e6개 있을경우 제일 상단값은 2^63 * 1e6 = e18 * e6 = e24 >> long long
입력으로 들어오는값 모두 최대 2^63 > long long

코드

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
#include <iostream>
#include <queue>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
int nums[1000010];
 
ll make(int node, int st, int en) {
    // 시작값과 끝값이 같으면 종료
    if(st == en) return tree[node] = nums[st];
    
    int mid = (st+en)/2;
    ll rsl = make(node*2, st, mid);
    ll rsr = make(node*2+1, mid+1, en);
    // st ~ mid, mid+1 ~ en 의 합으로 리턴
    return tree[node] = rsl + rsr;
}
 
void update(int node, int st, int en, int idx, ll diff) {
    if(idx < st || en < idx) return;
    tree[node] += diff;
    if(st != en) {
        int mid = (st+en)/2;
        update(node*2, st, mid, idx, diff);
        update(node*2+1, mid+1, en, idx, diff);
    }
    return;
}
 
ll sumt(int node, int st, int en, int li, int ri) {
    if (ri < st || en < li) return 0;
    if(li <= st && en <= ri) return tree[node];
    
    int mid = (st+en)/2;
    ll rsl = sumt(node*2, st, mid, li, ri);
    ll rsr = sumt(node*2+1, mid+1, en, li, ri);
    
    return rsl + rsr;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M,K; cin >> N >> M >> K;
    for(int i=0; i<N; i++) cin >> nums[i];
    
    // 세그먼트 크기 초기화
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    // 초기 세그먼트 트리 생성
    make(1,0,N-1);
    
    for(int i=0; i<M+K; i++) {
        int a,b; cin >> a >> b;
        ll c; cin >> c;
        if(a==1) {
            ll diff = c - nums[b-1];
            nums[b-1] = c;
            // 구간 업데이트
            update(1,0,N-1,b-1, diff);
        } else {
            // 구간합 구함
            cout << sumt(1,0,N-1,b-1,c-1) << '\n';
        }
    }
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

세그먼트 트리

비슷한 문제

세그먼트 lazy : https://www.acmicpc.net/problem/10999

'알고리즘 > 백준' 카테고리의 다른 글

백준 1937 욕심쟁이 판다 풀이(C++/CPP) (0)	2021.02.14
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11657 타임머신 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11780 플로이드2 풀이(C++/CPP) (0)	2021.02.08

백준 11657 타임머신 쉬운 풀이(C++/CPP)

2021. 2. 14. 17:25

문제링크 : https://www.acmicpc.net/problem/11657

문제 접근

벨만포드 기본 문제 : https://dev-jango.tistory.com/28

시간복잡도 계산

모든 간선을 : O(E)
노드의 개수만큼 반복 : O(V)
O(V*E)

인트 계산

거리의 최대값
- 최악의 경우 노드 개수(V) * 간선 개수(E) * 최대 비용
- 500 * 6000 * 1e4 = 3e10
- long long 사용

코드

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 <iostream>
#include <tuple>
#include <vector>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef long long ll;
 
const int inf = 1e8+10;
 
// 거리배열 생성
ll dist[510];
ti3 edge[6010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    fill(dist, dist+510, inf);
    
    for(int i=0; i<E; i++){
        int a,b,c; cin >> a >>b >> c;
        edge[i] = {a,b,c};
    }
    
    // 시작노드 0으로 초기화
    dist[1] = 0;
    
    // 모든 간선을 노드 갯수만큼 반복
    for(int j=0; j<V; j++) {
        for(int i=0; i<E; i++) {
            int a,b,c; tie(a,b,c) = edge[i];
            
            // 아직 거치지 않은 점일경우
            if(dist[a] == inf) continue;
            // a점을 거친 경우 거리가 더 작아질경우
            if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
        }
    }
    
    // 사이클 확인
    for(int i=0; i<E; i++) {
        int a,b,c; tie(a,b,c) = edge[i];
        
        if(dist[a] == inf) continue;
        // a점을 거친 후 거리가 작아질경우 사이클
        if(dist[b] > dist[a] + c) {
            cout << -1 << '\n';
            return 0;
        }
    }
    
    for(int i=2; i<=V; i++) {
        if(dist[i] == inf) cout << -1 << '\n';
        else {
            cout << dist[i] << '\n';
        }
    }
    
    return 0;
}
 
 
Colored by Color Scripter
cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11780 플로이드2 풀이(C++/CPP) (0)	2021.02.08
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP) (0)	2021.02.08

백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP)

2021. 2. 14. 15:02

문제링크 : https://www.acmicpc.net/problem/11779

문제 접근

다익스트라 응용문제
다익스트라 개념 참조 : https://dev-jango.tistory.com/26
경로를 구하는 조건이 추가됨 > 이전 경로를 추적하기 위해 pre 배열 사용 : 해당 노드에 도착하기 이전 노드

시간복잡도 계산

다익스트라 시간복잡도 : O(ElgE)
20 * 1e5 = 2e6

인트 계산

거리
- 거리가 나올수 있는 최대값 = 모든 도시를 최대 비용으로 거치는경우
- 1000 * e5 = e8 > INT 사용 가능

코드

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 <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int inf = 1e8+10;
// 시작점에서부터 해당 노드까지의 거리
int dist[1010];
// 인접 간선 리스트
vector<pair<int, int>> adj[1010];
// 이전 노드값
int pre[1010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 거리 배열 무한값으로 초기화
    fill(dist, dist+1010, inf);
    
    int N,M; cin >> N >> M;
    while(M--) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
    }
    int st, en; cin >> st >> en;
    
    // 시작 노드는 거리 0
    dist[st] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[st], st));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
                // 이전 노드값 추가
                pre[ni] = ei;
            }
        }
    }
    
    cout << dist[en] << '\n';
    vector<int> path;
    int cur = en;
    while(cur != st) {
        path.push_back(cur);
        cur = pre[cur];
    }
    path.push_back(cur);
    
    cout << path.size() << '\n';
    reverse(path.begin(), path.end());
    for(int x : path) cout << x << ' ';
    
    
    return 0;
}
 
 
Colored by Color Scripter
cs

문제유형

다익스트라 - 경로
- pre 배열을 사용해서 경로를 추적

'알고리즘 > 백준' 카테고리의 다른 글

백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11657 타임머신 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11780 플로이드2 풀이(C++/CPP) (0)	2021.02.08
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP) (0)	2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP) (0)	2021.02.07

백준 11780 플로이드2 풀이(C++/CPP)

2021. 2. 8. 22:52

문제링크 : https://www.acmicpc.net/problem/11780

문제 접근

기본 플로이드 문제와 유사
단 경로를 구하는 문제가 다름
- 현재 노드에서 다음 경로를 기록할 nxt 배열을 추가
- nxt 배열을 갱신할때
  - 처음에 경로 map 배열에 초기화할떄
  - map[j][i] > map[j][k] + map[k][i] 인경우, nxt[j][i] = nxt[j][k]로 갱신
  - 이때 다음 노드는 k가 아닌, j에서 k로 가는 노드로 대체

시간복잡도 계산

O(V^3) >> 1e6

인트 계산

버스 최대 비용 : 1e5
도시 최대 거치는 개수 : 1e2
최대 비용 : 1e5*1e2 = 1e7 >> INT 사용 가능

코드

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 <vector>
 
using namespace std;
 
const int inf = 1e8+10;
int map[110][110];
int nxt[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&map[0][0], &map[109][110], inf);
    
    int V,E; cin >> V >> E;
    
    // 자기 자신으로 가는 비용은 0으로 초기화
    for(int i=1; i<=V; i++) map[i][i] = 0;
    
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        map[a][b] = min(c, map[a][b]);
        nxt[a][b] = b;
    }
    
    
    for(int k=1; k<=V; k++) {
        for(int j=1; j<=V; j++) {
            for(int i=1; i<=V; i++) {
                // k를 거치는 경우 더 비용이 작으면 갱신
                // 이때 다음 노드는 k가 아닌, j에서 k로 가는 노드로 대체
                if(map[j][i] > map[j][k] + map[k][i]) {
                    map[j][i] = map[j][k] + map[k][i];
                    nxt[j][i] = nxt[j][k];
                }
            }
        }
    }
    
    for(int j=1; j<=V; j++) {
        for(int i=1; i<=V; i++) {
            if(map[j][i] == inf) cout << 0 << ' ';
            else cout << map[j][i] << ' ';
        }
        cout << '\n';
    }
    
    for(int j=1; j<=V; j++) {
        for(int i=1; i<=V; i++) {
            if(map[j][i] == inf || map[j][i] == 0) {
                cout << 0 << '\n';
                continue;
            }
            
            vector<int> v;
            // 출발지부터 nxt따라가면서 경로 추가
            int cur = j;
            
            while(cur != i) {
                v.push_back(cur);
                cur = nxt[cur][i];
            }
            v.push_back(cur);
            
            cout << v.size() << ' ';
            for(int x : v) cout << x << ' ';
            cout << '\n';
        }
    }
    
    
    return 0;
    
}
 
 
 
Colored by Color Scripter
cs

문제유형

플로이드 - 경로구하기

'알고리즘 > 백준' 카테고리의 다른 글

백준 11657 타임머신 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP) (0)	2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP) (0)	2021.02.07

백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP)

2021. 2. 8. 22:19

문제링크 : https://www.acmicpc.net/problem/1197

문제 접근

최소 스패닝 트리 기본 문제
개념 참조 : https://dev-jango.tistory.com/22

시간복잡도 계산

최소스패닝트리 Kruscal : O(ElgE)

코드

Kruscal로 해결

#include <iostream>
#include <tuple>
#include <algorithm>
 
using namespace std;
typedef tuple<int, int, int> ti3;
 
int p[10010];
ti3 edge[100010];
 
int find(int v) {
    if(p[v] < 0) return v;
    return p[v] = find(p[v]);
}
 
// union find
bool is_diff_group(int v1, int v2) {
    // 각 부모노드를 찾음
    v1 = find(v1); v2 = find(v2);
    
    // 부모가 같은 노드라면 종료
    if(v1==v2) return 0;
    
    if(p[v1] == p[v2]) p[v1]--;
    if(p[v1] < p[v2]) p[v2] =v1;
    else p[v1] = v2;
    return 1;
    
    
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    fill(p, p+10010, -1);
    
    // E개의 간선 추가
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        edge[i] = {c,a,b};
    }
    sort(edge, edge+E);
    
    int cnt=1;
    int ans=0;
    for(int i=0; i<E; i++) {
        int a,b,c; tie(c,a,b) = edge[i];
        
        // 둘이 같은 그룹이라면 건너뜀
        if(!is_diff_group(a,b)) continue;
        
        // 다른그룹이라면
        cnt++;
        ans+=c;
        
        // 모든 노드 추가되면 종료
        if(cnt == V) break;
        
    }
    
    cout << ans << '\n';
    
    
    
    return 0;
}
 

Colored by Color Scripter

문제유형

최소 스패닝 트리

'알고리즘 > 백준' 카테고리의 다른 글

백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP) (0)	2021.02.14
백준 11780 플로이드2 풀이(C++/CPP) (0)	2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP) (0)	2021.02.07

백준 1786 찾기 쉬운 풀이(C++/CPP)

2021. 2. 7. 23:52

문제링크 : https://www.acmicpc.net/problem/1786

문제 접근

KMP, Rabin-Karp 기본문제
개념 참조 : https://dev-jango.tistory.com/20

시간복잡도 계산

KMP, Rabin-Karp : O(M+N)
- M : 첫번째 문자열 길이
- N : 두번쨰 문자열 길이

인트 계산

최대 숫자 : 최대 문자열 길이 : 1e6

코드(KMP 풀이)

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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<int> fail(string& s) {
    vector<int> f(s.size());
    int j=0;
    for(int i=1; i<s.size(); i++) {
        while(j>0 && s[j] != s[i]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
    return f;
}
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    vector<int> f = fail(P);
    
    int j=0;
    vector<int> rs;
    for(int i=0; i<T.size(); i++) {
        while(j>0 && T[i] != P[j]) j = f[j-1];
        if(T[i] == P[j]) j++;
        if(j==P.size()) {
            rs.push_back(i+2-P.size());
            j = f[j-1];
        }
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    return 0;
}
 
 
Colored by Color Scripter
cs

코드(Rabin Karp 풀이)

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 <string>
 
using namespace std;
typedef long long ll;
 
ll a = 302;
ll p = 1e9+7;
ll powa[1000010];
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    int lenT = T.size();
    int lenP = P.size();
    if(lenT < lenP) {
        cout << 0 << '\n';
        return 0;
    }
    
    
    // a의 제곱값을 미리 구해놓음
    powa[0] = 1;
    for(int i=1; i<P.size(); i++) {
        powa[i] = powa[i-1] * a %p;
    }
    
    // 각각 P길이만큼 해시값 구함
    ll hashT = 0;
    ll hashP = 0;
    
    for(int i=0; i<P.size(); i++) {
        hashT = (hashT + T[i] * powa[P.size()-1-i]) %p;
        hashP = (hashP + P[i] * powa[P.size()-1-i]) %p;
    }
    
    vector<int> rs;
    if(hashT == hashP) rs.push_back(1);
    
    for(int i=1; i<=(T.size()-P.size()); i++) {
        // 앞글자 빼고, a만큼 곱해서 한자리씩 올리고, 새로 한글자 추가
        hashT = (hashT - T[i-1] * powa[P.size()-1])%p;
        // 음수인경우 확인
        if(hashT < 0) hashT += p;
        hashT = hashT * a % p;
        hashT = (hashT + T[i+P.size()-1] ) % p;
        if(hashT == hashP) rs.push_back(i+1);
        
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    
    return 0;
}
 
 
Colored by Color Scripter
cs

문제유형

KMP
Rabin Karp

'알고리즘 > 백준' 카테고리의 다른 글

백준 11780 플로이드2 풀이(C++/CPP) (0)	2021.02.08
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP) (0)	2021.02.08
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP) (0)	2021.02.07

PREV 1 ···4 5 6 7 8 NEXT

알고리즘/백준

문제 추상화

아이디어

시간복잡도 계산

인트 계산

코드

문제유형

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

코드

문제유형

'알고리즘 > 백준' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드(KMP 풀이)

코드(Rabin Karp 풀이)

문제유형

'알고리즘 > 백준' 카테고리의 다른 글

티스토리툴바