문제링크 : 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/14725


아이디어

  • 계층구조 trie로 표현한다음
  • 규칙에 맞도록 출력(DFS)
    • 출력할떄 알파벳순서로 어떻게 정렬하지?
    • child가 map 순서대로를 이용

시간복잡도 계산

  • trie생성
    • 모든 입력에 대해 : O(N)
    • 모든 먹이개수에 대해 trie 생성: O(K)
    • 총합 : O(NK)
  • trie 출력, DFS
    • DFS 출력 : O(V+E)
    • V : 노드개수 : NK
    • E : 노드간선개수 : NK
    • O(NK)
  • 합 : O(NK) : 1.5e4

인트 계산

  • 노드 인덱스 : 최대 NK

코드

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
#include <iostream>
#include <vector>
#include <map>
#include <string>
 
using namespace std;
 
struct node {
    bool fin;
    map<string, int> child;
    string cur;
    node(string s) {
        fin = false;
        cur = s;
        child.clear();
    }
};
 
vector<node> trie;
 
int insert(int nodi, string s) {
    
    if(trie[nodi].child[s] == 0) {
        trie[nodi].child[s] = trie.size();
        trie.push_back(s);
    }
    
    return trie[nodi].child[s];
}
 
void dfs(int cur, int depth) {
    if(cur != 0) {
        for(int i=0; i<depth-1; i++) cout << "--";
        cout << trie[cur].cur <<'\n';
    }
    for(auto it = trie[cur].child.begin(); it!=trie[cur].child.end(); it++) {
        dfs(it->second, depth+1);
    }
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    
    trie.push_back(node(""));
    
    while(N--) {
        int en; cin >> en;
        int pre = 0;
        while(en--) {
            string es; cin >> es;
            pre = insert(pre, es);
        }
    }
    
    dfs(0,0);
    
    return 0;
}
 
cs

문제유형

  • TRIE - 여러글자
    • 일반 TRIE가 한글자씩 정보 저장
    • 여러글자를 가지고 TRIE
    • node의 child에 알파벳이나 숫자갯수만큼 저장하는 것이 아닌
    • map을 가지고 다음 노드를 관리

+ Recent posts

티스토리툴바