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

아이디어

  • BFS로 채널을 누르고, 위아래로 누를때 원하는 채널로 이동하는 최소의 값
  • 버튼 누르는건 어떻게?
    • 1~6번째만, 해당 자리수의 숫자 큐에 넣음
    • 에시 : 2번쨰 누르는 경우엔, 10~99까지
    • 고장난 버튼 : 각 자리에서 고장난 버튼 확인
      • 이떄 BFS이므로 중복체크 해주기

시간복잡도 계산

  • 큐에 최대 들어갈수 있는수(노드) : 5e5
  • 큐에 들어가는 노드에서, 고장난 버튼 확인 : 10
  • 최대 움직일수 있는 수(간선) : 5e5
  • BFS 시간복잡도 : O(V*10+E) : 5e6 + 5e5 = 5.5e6

인트 계산

  • 누르는 횟수 : 최대 5e5

코드

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
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
vector<int> f;
bool chk[1000010];
//bool chk[10000];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int target; cin >> target;
    
    // 중복체크 초기화
//    fill(chk, chk+500010, false);
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int a; cin >> a; f.push_back(a);
    }
    
    queue<int> q;
    q.push(100);
    chk[100] = 1;
    int cnt=0;
    while(!q.empty()) {
        int qsize = q.size();
        while(qsize--) {
            int eq = q.front(); q.pop();
            
            if(eq == target) {
                cout << cnt << '\n';
                return 0;
            }
            
            // 더하고
            if(eq+1 <=500000) {
                if(chk[eq+1] == false) {
                    chk[eq+1] = 1;
                    q.push(eq+1);
                }
            }
            
            // 빼기
            if(eq-1 >=0) {
                if(chk[eq-1] == false) {
                    chk[eq-1] = 1;
                    q.push(eq-1);
                }
            }
            
            
            
        }
        
        if(cnt<6) {
            int st = pow(10,cnt);
            if(st==1) st = 0;
            int en = pow(10,cnt+1)-1;
            
            for(int i=st; i<=en; i++) {
                if(chk[i]) continue;
                bool sw = false;
                // 각 자리수에서 금지된 숫자 있는지 확인
                for(int j=0; j<=cnt; j++) {
                    // 각자리숫자
                    int num = (int)(i/pow(10,j)) % 10;
                    if(find(f.begin(), f.end(), num) != f.end()) {
                        sw = true;
                        break;
                    }
                    
                }
                
                // 금지된 숫자에 걸리는 것이 없다면 큐에 넣기
                if(sw == false){
                    chk[i] = 1;
                    q.push(i);
                }
            }
        }
        
        cnt++;
    }
    
    return 0;
}
 
cs

문제유형

  • BFS - 최소 횟수

비슷한 문제

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

백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1946 신입 사원  (0) 2021.02.15

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


아이디어

  • A,B의 각각 부배열을 구하는 방법
    • 애초에 들어올떄 해당 인덱스까지의 합을 받아옴
    • 각 인덱스 순회하면서 모든 경우의 수를 구함
    • O(N^2)
  • A,B 각각 더해서 값을 구할경우 : O(N^2 * N^2) = O(N^4) = 1e12 > 시간초과
  • A의 값을 고정한다음에, 더해서 0이되는 값을 B에서 이진탐색으로 찾음
  • B 배열에서 같은 값이 여러개일경우에??
    • 이진탐색을 lower bound, upper bound 같이 수행해서 차이만큼 빼기

시간복잡도 계산

  • B 정렬 : N^2lgN^2
  • A순회하면서 이진탐색 :N^2 lgN^2
  • O( N^2lgN^2 + N^2lgN^2) = O( N^2lgN^2) = 1e6 * lg(1e6) = 1e6 * 20 = 2e7

인트 계산

  • 더해서 최악의 캐이스 : N * 1e6 * 2 = 1e3 * 1e6 * 2 = 2e9 > INT 가능
    • 결과값 : 1e6개 * 1e6개 = 1e12개 >> ll 사용

코드

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
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int sumA[1010];
int sumB[1010];
int partA[1000010];
int partB[1000010];
 
int binsearchlower(int st, int en, int target) {
    if(st==en) {
        if(partB[st] == target) return st;
        return -1;
    }
 
    int mid = (st+en)/2;
    if(partB[mid] < target) return binsearchlower(mid+1, en, target);
    else return binsearchlower(st, mid, target);
}
 
int binsearchupper(int st, int en, int target) {
    if(st==en) {
        if(partB[st] == target) return st;
        return -1;
    }
 
    int mid = (st+en+1)/2;
    if(partB[mid] <= target) return binsearchupper(mid, en, target);
    else return binsearchupper(st, mid-1, target);
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T; cin >> T;
    int N; cin >> N;
    cin >> sumA[0];
    partA[0] = sumA[0];
    for(int i=1; i<N; i++) {
        cin >> sumA[i];
        // 이전값이랑 합함
        sumA[i] += sumA[i-1];
    }
 
    int cntA=0;
    for(int j=0; j<N; j++) {
        partA[cntA] = sumA[j];
        cntA++;
        for(int i=0; i<j; i++) {
            partA[cntA] = sumA[j] - sumA[i];
            cntA++;
        }
    }
 
 
    int M; cin >> M;
    cin >> sumB[0];
    partB[0] = sumA[0];
    for(int i=1; i<M; i++) {
        cin >> sumB[i];
        // 이전값이랑 합함
        sumB[i] += sumB[i-1];
    }
 
    int cntB=0;
    for(int j=0; j<M; j++) {
        partB[cntB] = sumB[j];
        cntB++;
        for(int i=0; i<j; i++) {
            partB[cntB] = sumB[j] - sumB[i];
            cntB++;
        }
    }
 
    sort(partB, partB+cntB);
 
    ll rs=0;
    for(int i=0; i<cntA; i++) {
        int tar = T - partA[i];
        // 같은 값을 나오는걸 어떻게 할까 >> lower, upper 둘다 구해서 인덱스 더하자
        int st = binsearchlower(0,cntB-1,tar);
        if(st != -1) {
            int en =binsearchupper(0,cntB-1,tar);
            rs += (en-st+1);
        }
    }
 
    cout << rs << '\n';
    
    return 0;
 
}
 
 
 
cs

문제유형

  • 이진탐색 - 모든케이스에서 이진탐색

비슷한 문제

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

백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 1107 리모컨  (1) 2021.02.16
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1946 신입 사원  (0) 2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP)  (0) 2021.02.14

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


문제 추상화

  • DP로 LCS를 구하는 문제
  • 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;
}
 
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

문제링크 : 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;
}
 
 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

문제링크 : 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;
}
 
cs

문제유형

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

비슷한 문제

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

백준 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

문제링크 : 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;
}
 
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

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


문제 접근


시간복잡도 계산

  • 처음 세그먼트 트리 생성 : 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;
}
 
cs

문제유형

  • 세그먼트 트리

비슷한 문제

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

백준 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

문제 정의

  • 구간의 합을 여러번 구하고, 수정할때
    • 그냥 구간의 합을 구할 경우 : N개를 탐색 >> O(N)
    • 세그먼트 사용할 경우 : O(NlgN)

문제 접근

  • segment tree의 빈 리스트를 먼저 만듬
    • 재귀함수를 통해 초기 세그먼트 트리 만들때, 업데이트할때, 구간합 구할때를 만들어줌

시간복잡도

  • 구간 합 구하기, 수정하기 : O(lgN)

대표예제 : 백준 2042 구간 합 구하기

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;
}
 
cs

문제 유형

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Bellman Ford, 벨만 포드 알고리즘  (0) 2021.02.14
[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

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


문제 접근


시간복잡도 계산

  • 모든 간선을 : 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;
}
 
 
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

문제 정의

  • 한개의 노드에서 다른 노드까지의 최소 비용 구할때
    • 밸만 포드 : O(VE)
    • 문제의 유형에 따라서 적합한 알고리즘 선택
    • Floyd를 사용할경우 O(V^3)
    • 다익스트라 : O(ElgE)
      • 음수의 간선 확인 가능
  • 음수로 인한 거리 무한감소 사이클 확인 가능

문제 접근

  • 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)
  • dist배열의 시작 노드값을 0으로 만듬
  • 모든 간선에 대해서, 간선을 지나는 경우 비용이 더 감소할 경우 업데이트
  • 위 과정을 노드의 개수만큼 반복
  • 마지막 한번 모든 간선에 대해서, 위 과정을 반복
    • 이때 비용이 더 감소하는 경우가 있다면 >> 무한 사이클 확인

시간복잡도

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

대표예제 : 백준 11657 타임머신

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;
}
 
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Segment Tree, 세그먼트 트리 알고리즘  (0) 2021.02.14
[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

+ Recent posts

티스토리툴바