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


아이디어

  • 시작점 * 끝점 모든 경우의 수 구할 떄
    • O(N^2) = 1e10 시간초과
  • 분할정복을 사용
    • 최소값의 양쪽의 사각형의 넓이 중 큰값을 선택
  • 세그먼트 트리로 구현
    • 세그먼트 트리 구성 : 각 노드는 가장 작은값을 가지는 인덱스를 지정
    • 구간에서 가장 작은 값의 인덱스를 찾아서
    • 그 양쪽의 값을 계산해줌

시간복잡도 계산

  • 세그먼트 트리 생성 : O(NlgN)
  • 검색 및 최대값 계산 : O(lgN)
  • 총합 : O(NlgN)

인트 계산

  • 세그먼트 값 : 최소 인덱스 : 최대 1e5, INT 가능
  • 각 히스토그램 크기 : 최대 1e9, INT 가능
  • 사각형 계산 : 최대 1e9 * 1e5 : 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>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
int nums[100010];
vector<int> tree;
int N;
 
int make(int node, int st, int en) {
    if(st==en) return tree[node] = st;
    
    int mid = (st+en)/2;
    int li = make(node*2, st, mid);
    int ri = make(node*2+1, mid+1, en);
    
    // 값 비교후 작은 인덱스 표시
    if( nums[li] <= nums[ri]) return tree[node] = li;
    else return tree[node] = ri;
}
 
int find(int node, int st, int en, int li, int ri) {
    if(ri < st || en < li) return -1;
    if(li <= st && en <=ri) return tree[node];
    
    int mid = (st+en)/2;
    int leftIndex = find(node*2, st, mid, li, ri);
    int rightIndex = find(node*2+1, mid+1, en, li, ri);
    
    if(leftIndex == -1) return rightIndex;
    else if(rightIndex == -1) return leftIndex;
    
    
    if(nums[leftIndex] <= nums[rightIndex]) return leftIndex;
    else return rightIndex;
    
}
 
ll query(int st, int en) {
    if(st > en) return 0;
    
    // 최소값을 기준으로 전체, 좌측, 우측 더 작은 값
    // 전체
    int mi = find(1,0,N-1, st, en);
    ll rs = (ll)(en-st+1) * nums[mi];
    rs = max(rs, query(st, mi-1));
    rs = max(rs, query(mi+1, en));
    return rs;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1) {
        fill(nums, nums+100010, 0);
        
        cin >> N;
        if(N==0) break;
        
        tree.clear();
        int h = ceil(log2(N));
        tree.resize(1<<(h+1));
        
        for(int i=0; i<N; i++) cin >> nums[i];
        // 세그먼트 트리 생성
        make(1,0,N-1);
        
        cout << query(0,N-1) << '\n';
        
    }
    
    
    return 0;
}
 
cs

문제유형

  • 세그먼트 - 연속된 넓이
    • 트리에 규칙에 맞는 인덱스를 넣고
    • 쿼리를 통해 시작점부터 끝점까지 값을 비교

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

백준 10775 공항  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03

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


문제 추상화

  • 음의 간선을 통해 사이클이 생기는지 확인하는 문제

아이디어

  • 밸만 포트만 사용하여 사이클이 생기는지 확인
  • 사이클 확인할경우, 출발점 지정해줄 필요 없음

시간복잡도 계산

  • 테스트캐이스 : O(TC)
  • 밸만 포드만 : O(NM)
  • 총합 : O(TC * N * M) : 5 * 500 * 2500 = 6.25e6 > 가능

인트 계산

  • N * M * T의 최대 수 가능
  • 500 * 2500 * 1e4 = 1.25e6 * e4 = e10 > 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
#include <iostream>
#include <tuple>
#include <vector>
 
 
using namespace std;
typedef long long ll;
typedef tuple<int, int, int> ti3;
 
const ll inf = 2e10;
ll dist[510];
vector<ti3> edge;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int TC; cin >> TC;
    while(TC--) {
        fill(dist, dist+510, 0);
        
        edge.clear();
        int N,M,W; cin >> N >> M >> W;
        for(int i=0; i<M; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge.push_back({a,b,c});
            edge.push_back({b,a,c});
        }
        
        for(int i=0; i<W; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge.push_back({a,b,-c});
        }
        
        // 모든 간선을 거침
        for(int i=0; i<N-1; i++) {
            for(int j=0; j<edge.size(); j++) {
                int a,b,c; tie(a,b,c) = edge[j];
                
                if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
            }
        }
        
        bool sw = false;
        for(int j=0; j<edge.size(); j++) {
            int a,b,c; tie(a,b,c) = edge[j];
            
            if(dist[b] > dist[a] + c ) {
                cout << "YES\n";
                sw = 1;
                break;
            }
        }
        
        if(sw == false) cout << "NO\n";
        
    }
    
    return 0;
}
 
cs

문제유형

  • 밸만포드 - 사이클 확인
    • 출발점 없이 사이클만 확인
    • dist 배열 시작점을 0으로 만들고 나머지 inf로 만들고 진행할 경우, 시작점 고립되어있을경우 사이클 확인 불가

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

백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

 

 

아이디어

  • 0-1 BFS 사용해서 동생위치 찾음
    • 처음 좌표 넣을떄 2의배수 모두 추가
    • 중간에 x2배(시간이 0) 다른것보다 먼저 수행해줘야함
    • priority_queue 사용해서 수행

 

시간복잡도 계산

  • 우선순위 큐 사용 : O(NlgN) = 1e5 * 20
  • BFS : O(V+E)
    • 노드 개수 : N
    • 간선 개수 : 최대 N
    • O(N)
  • 총합 : O(NlgN + N) : O(NlgN) > 가능

인트 계산

  • 가장 빠른시간 최대 1e5 > 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
#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
bool chk[100010];
int main() {
    int N,K; cin >> N >> K;
    
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    // 시작값 큐에 넣어줌, 앞에는 시간, 뒤에는 노드
    pq.push(make_pair(0,N));
    fill(chk, chk+100010, 0);
    chk[N] = 1;
    if(N==K) {
        cout << 0 << '\n';
        return 0;
    }
    
    while(!pq.empty()) {
        int et = pq.top().first;
        int en = pq.top().second;
        pq.pop();
        
        if(en == K) {
            cout << et << '\n';
            return 0;
        }
        
        // 2배 먼저 해주기
        int en2 = en * 2;
        while(en2 <= 100000) {
            if(chk[en2]) break;
            
            chk[en2] = 1;
            pq.push(make_pair(et, en2));
            en2 = en2 * 2;
        }
        
        // 1더한것
        if(en+1 <= 100000) {
            if(chk[en+1] == false) {
                chk[en+1] = 1;
                pq.push(make_pair(et+1, en+1));
            }
            
        }
        
        
        // 1뺀것
        if(en-1 >= 0) {
            if(chk[en-1] == false) {
                chk[en-1] = 1;
                pq.push(make_pair(et+1, en-1));
            }
            
        }
    }
    return 0;
}
 
 cs

 

문제유형

  • BFS - 0/1 : 다른 노드보다 우선 수행해줘야하는 조건이 있을때 사용

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

백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

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

문제 추상화

  • 출발점에서 종료점까지 가는데
  • 최대 1000의 거리까지 갈 수 있음
  • 어느 지점 들려서 가면 갈수 있는지 확인

아이디어

  • bfs로 도착지 갈수 있는지확인
    • 그럼 각 점에서 다음 점으로 갈수 있는지는 어떻게 확인?
      • 반경 1000미터를 돌면서 확인하면 되지 않을까?
        • 그러면 정점이 너무 많아짐
        • BFS : O(V+E)
          • V : 모든 정점 : 9e8 > 시간초과
      • 편의점과 펜타포트를 기록해뒀다가 계속 탐색해보자
    • 그래서 펜타포트와 값이 같아지면 종료

시간복잡도 계산

  • 테스트 케이스 O(T)
  • 간선의 개수 : O(N^2)
  • BFS : O(V+E) = O(N^2)
  • 합 : O(T * N^2) > 가능

인트 계산

  • 거리가 될수 있는 최대값 = 32767 * 2 > 인트 가능

코드

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 <cmath>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
vector<pi2> v;
bool chk[110];
vector<int> adj[110];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        int N; cin >> N;
        
        v.clear();
        // 출발값
        int sty,stx;
        cin >> sty >> stx;
        v.push_back(make_pair(sty, stx));
        
        // 편의점 위치 배열
        
        for(int i=0; i<N; i++) {
            int ey, ex;
            cin >> ey >> ex;
            v.push_back(make_pair(ey, ex));
        }
        int eny, enx;
        cin >> eny >> enx;
        v.push_back(make_pair(eny, enx));
 
        
        // 인접 리스트 초기화
        for(int i=0; i<110; i++) adj[i].clear();
 
        for(int i=0; i<=N+1; i++) {
            int ey = v[i].first;
            int ex = v[i].second;
            
            for(int j=0; j<=N+1; j++) {
                if(i==j) continue;
                int ny = v[j].first;
                int nx = v[j].second;
                if(abs(ey - ny) + abs(ex - nx) <= 1000) {
                    adj[i].push_back(j);
                }
                
                
            }
 
        }
        
        // st에서부터 bfs 시작해 en도착하면 종료
        fill(chk, chk+110, 0);
        
        queue<int> q;
        q.push(0);
        chk[0] = 1;
        
        bool sw = false;
        
        while(!q.empty()) {
            int eq = q.front(); q.pop();
            if(eq == N+1) {
                cout << "happy\n";
                sw = 1;
                break;
            }
            
            for(auto x : adj[eq]) {
                if(chk[x] == 1) continue;
                q.push(x);
                chk[x] = 1;
            }
        }
        
        if(sw == false) cout << "sad\n";
        
        
        
    }
    return 0;
}
 
cs

문제유형

  • BFS - 조건
    • 특정 거리 이하의 경우에만 이동할 수 있는 경우
    • 해당 조건에 만족하는 경우만 간선에 추가한 뒤 BFS 수행

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

백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

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


아이디어

  • 모든 행성을 터널로 연결 >> MST
    • Kruscal 사용해서 MST 구하자
  • 간선의 개수 : E = N(N+1)/2 = 1e10/2 = 5e9
    • MST 시간복잡도 : O(ElgE) > 시간초과
    • 간선을 모두 넣는 경우에는 시간초과가 발생
  • 문제 중 비용 = min(x, y, z)을 이용
    • x,y,z 좌표의 차이를 각각 넣고, 이중 최소값만 사용하면됨
      • 크루스칼에서 자연스럽게 최소의 간선만 적용될 것임
    • 모든 노드의 간선을 넣지말고. 정렬한뒤 근접한 것만 적용
      • 어짜피 최소값만 MST에서 살아남게됨
      • 그러므로 정렬 시킨다음에 인접한 것이 가장 작은 값

시간복잡도 계산

  • x,y,z 좌표에 대해서 각각 정렬 : O(3 * NlgN)
    • 인접한 노드에 대해서 간선 추가 : O(3 * N)
    • MST 시간복잡도 : ElgE
      • 간선의 개수(E): 3N
      • 3Nlg3N
    • 총합 : O(3NlgN + 3N + 3Nlg3N) = O(NlgN)

인트 계산

  • 간선 의 길이 최대값 : 2e9 > INT 가능
  • 최소비용 : 2e9 *N-1 >> 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
#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef pair<int, int> pi2;
typedef long long ll;
 
vector<ti3> edge;
int p[100010];
vector<pi2> xnode;
vector<pi2> ynode;
vector<pi2> znode;
 
int N;
 
int find(int v) {
    if(p[v] < 0) return v;
    return p[v] = find(p[v]);
}
 
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] < 0) p[v2] = v1;
    else p[v1] = v2;
    return 1;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(p, p+100010, -1);
    cin >> N;
    
    // 각 좌표 넣기
    // 이때 노드 인덱스랑 같이 넣어줌 정렬후 확인하기 위해
    for(int i=0; i<N; i++) {
        int ex, ey, ez;
        cin >> ex >> ey >> ez;
        xnode.push_back(make_pair(ex, i));
        ynode.push_back(make_pair(ey, i));
        znode.push_back(make_pair(ez, i));
    }
    
    // 간선수 줄이기위해 정렬
    sort(xnode.begin(), xnode.end());
    sort(ynode.begin(), ynode.end());
    sort(znode.begin(), znode.end());
    
    // 인접한 노드를 엣지에 추가
    for(int i=0; i<N-1; i++) {
        edge.push_back({abs(xnode[i].first - xnode[i+1].first),xnode[i].second,xnode[i+1].second});
        edge.push_back({abs(ynode[i].first - ynode[i+1].first),ynode[i].second,ynode[i+1].second});
        edge.push_back({abs(znode[i].first - znode[i+1].first),znode[i].second,znode[i+1].second});
    }
    
    // 간선들 정렬
    sort(edge.begin(), edge.end());
    
    int cnt=0;
    ll ans=0;
    // Kruscal 수행
    for(int i=0; i<edge.size(); i++) {
        int cost, a,b; tie(cost,a,b) = edge[i];
        if(!is_diff_group(a,b)) continue;
        
        cnt++;
        ans += cost;
        if(cnt==N-1) break;
    }
    
    cout << ans << '\n';
    
    
    return 0;
}
 
cs

문제유형

  • MST - 간선의 특수 조건
    • 간선의 비용이 특수한 경우
    • 일반적으로 하면 간선의 개수가 많아서 시간초과 발생
    • 간선의 조건 활용해 그리디하게 사용 가능

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

백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28

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


아이디어

  • 팰린드롬 개념

    • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
    • 문자열에서 접두사와 접미사가 겹치는 부분이 발생(이때 홀수로 겹쳐서 대칭되어야함)
    • 구하는 방법 :
      • KMP
        • 접두사와 접미사가 같은 길이(f[s.size()-1])에서 반복하는 문자열(s.size()-f[s.size()-1])으로 나누어 떨어지지 않을때
        • f[s.size()-1] % (s,size() - f[s.size()-1])
      • DP
        • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
        • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우(arr[st-1] == arr[en+1]) dp[st-1][en+1] = true
    • KMP 사용할 경우
      • 1부터 계산하는건 문제가 안됨
      • 중간부터 계산하는 건 어떻게 진행?
      • 매번 KMP를 다시구할경우
        • O(M * N) = 2e9 > 시간초과
      • KMP 사용해서는 불가
    • DP 사용할 경우
      • 숫자들에 대해 미리 DP를 구해놓고
      • 각각의 요청에 따라 DP 값 출력

시간복잡도 계산

  • DP 구하기 : O(N^2)
  • 요청에라 확인 : O(M)
  • 합 : O(N^2+M) : 4e6 + 1e6

인트 계산

  • 입력 숫자값 최대 1e5
    • DP 값 : true, false

코드

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
#include <iostream>
 
using namespace std;
 
int arr[2010];
int dp[2010][2010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >>arr[i];
    
    fill(&dp[0][0], &dp[2009][2010], 0);
    
    // 길이 1일때
    for(int i=0; i<N; i++) dp[i][i] = 1;
    
    // 길이 2일때
    for(int i=0; i<N-1; i++) if(arr[i] == arr[i+1]) dp[i][i+1] = 1;
    
    // 길이 3이상
    // 각 길이 케이스에서
    for(int l=2; l<N; l++) {
        // 시작하는 곳
        for(int i=0; i<N-l; i++) {
            if(arr[i] == arr[i+l] && dp[i+1][i+l-1]) dp[i][i+l] = 1;
        }
    }
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int j,k; cin >> j >> k;
        cout << dp[j-1][k-1] << '\n';
    }
    
    return 0;
}
 
cs

문제유형

  • DP - 팰린드롬
    • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
    • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
    • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우 팰린드롬
    • 문자길이 1,2, 3이상일때 각각 나눠서 수행

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

백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

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


문제 추상화

  • 각 문자가 몇번 반복되는지 찾아야함
  • 근데 연속해서 반복되어야함, 겹치거나 띄어서 반복되면안됨(일반 KMP와 다름)

아이디어

  • 문자열의 앞에서부터 자른다음 연속하는지 확인

    • 앞에서부터 자르는건 약수인지 확인
    • 다음 문자부터 문자열길이 단위만큼 비교
    • 시간복잡도 계산
      • 문자열 자르기 , 약수개수: O(M)
      • 문자열 길이 단위만큼 비교 : O(M)
      • O(M*M) : 1e12 시간초과
    • KMP 사용
      • KMP의 fail 배열 : 해당 인덱스에서 접두사와 접미사가 같은것의 개수
      • 각 문자열의 fail 배열을 구할경우, 마지막 값을 통해 몇번 반복되는지 확인할 수 있음
        • fail배열의 마지막값 : 해당 문자열의 접두사와 접미사가 같은 최대의 길이
        • 전체 문자열의 길이에서 이 최대의 길이뺀 값이 전체 문자열에서 반복하는 문자열
      • 단, 접두사와 접미사가 중간에 겹치는경우(팰린드롬 제외)

시간복잡도 계산

  • 모든 문자열에 대해서 O(10)
  • fail 함수 구함 : O(M)
  • 합 : O(M) = 1e6

인트 계산

  • 접두사와 접미사가 같은 최대 길이 : 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
37
38
39
#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[i] != s[j]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
    
    return f;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
    while(1) {
        string s; cin >> s;
        if(s == ".") break;
        
        int maxv = 0;
        vector<int> f = fail(s);
        
        
        if(f[s.size()-1] % (s.size() - f[s.size()-1])) cout << 1 << '\n';
        else cout <<s.size()/(s.size()-f[s.size()-1]) << '\n';
    }
    return 0;
}
 
cs

문제유형

  • KMP - 문자열 제곱
    • 문자열 안에서 작은 문자열이 최대 몇개 반복되는지 확인
    • 문자열 길이 - fail 함수의 마지막 인덱스 = 반복되는 문자 길이
    • 단, 접두사와 접미사가 중간에 겹치는 경우 확인(팰린드롬)

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

백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

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


아이디어

  • 자료구조 map 사용
  • 각 나무를 맵에 넣은다음에 추가될때마다 카운트 증가
    • 나무의 키들을 뽑아 정렬
    • 전체 개수중에 각 나무의 카운트를 출력

시간복잡도 계산

  • 맵에 넣기 O(M)
  • 맵 키 정렬O(NlgN)
  • 각 나무의 카운트를 출력

인트 계산

  • 최대 나무개수 e6 가능

코드

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
#include <iostream>
#include <string>
#include <map>
#include <cmath>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    map<string, int> tree;
    int cnt=0;
    
    string s;
    while(getline(cin, s)) {
        cnt++;
        tree[s]++;
        
    }
    cout <<fixed;
    cout.precision(4);
    
    for(auto it = tree.begin(); it !=tree.end(); it++) {
        cout << it->first << ' ' << round(it->second/(double)cnt*1000000)/10000 << '\n';
    }
    return 0;
}
 
 
 
cs

문제유형

  • 자료구조 - map

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

백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

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


아이디어

  • 랜선의 길이를 정한다음, K개의 랜선에 각각 나눠보면서 N개 이상이 되는 최대의 개수를 구하면됨
    • 정답이 되는 랜선의 길이를 가지고 이진 탐색 수행
      • 구하려는 랜선길이 이분탐색
      • 이분탐색할때 K개에 대해서 나눠줌
      • N개 이상이 되는 최대 길이를 구함 > upper bound

시간복잡도 계산

  • 구하려는 랜선길이 이분탐색 : lg(2^31)
    • 이분탐색할때 K개에 대해서 나눠줌 : O(K)
    • O(lg(2^31) * K) = 31 * 1e4 = 3e5

인트 계산

  • 이미 가지고 있는 랜선길이 : 1~2^31 = int 가능
  • 자를수 있는 갯수 계산할때 :
    • 제일 작은 1로 자른다고 쳤을때
    • 최대값 : 2^31 * K >> 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
#include <iostream>
#include <algorithm>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
int K,N;
int nums[10010];
 
//
ll cal(int mid) {
    ll rs=0;
    for(int i=0; i<K; i++) rs+=nums[i]/mid;
    
    return rs;
}
int binsearch(ll st, int en, int tar) {
    if(st==en) {
        return st;
    }
    
    int mid = (st+en+1)/2;
    if(cal(mid) >= tar) {
        return binsearch(mid, en, tar);
    }
    else return binsearch(st, mid-1, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K >> N;
    for(int i=0; i<K; i++) cin >> nums[i];
    
    cout << binsearch(1,pow(2,31)-1, N) << '\n';
}
 
cs

문제유형

  • 이분탐새 - 케이스를 이분탐색

비슷한 문제

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

백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21

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



아이디어

  • 포함하고있는지 확인 >> 이분탐색

시간복잡도 계산

  • N개에 대해 정렬 : O(NlgN)
  • M개에 대해 이분 탐색 : O(M * lgK )
  • 합 : O(NlgN + MlgK)

인트 계산

  • 각 숫자의 최소 -1e7, 최대 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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int nums[500010];
 
 
void binsearch(int st, int en, int tar) {
    if(st==en) {
        if(nums[st] == tar) cout << 1 << ' ';
        else cout << 0 << ' ';
        return;
    }
    
    int mid = (st+en)/2;
    
    if(nums[mid] < tar) binsearch(mid+1, en, tar);
    else binsearch(st, mid, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> nums[i];
    
    sort(nums, nums+N);
    
    int M; cin >> M;
    for(int i=0; i<M; i++){
        int a; cin >> a;
        binsearch(0,N-1,a);
    }
}
 
cs

문제유형

  • 이분탐색 기본

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

백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

+ Recent posts

티스토리툴바