코딩/알고리즘 (67) 썸네일형 리스트형 백준 11478 서로 다른 부분 문자열의 개수 http://deque.tistory.com/82 위를 통해 lcp를 구한다. 그리고 주어진 string이 가질 수 있는 모든 부분 문자열의 갯수에서 lcp의 총 합을 뺀다.그것이 정답인 이유는 다음과 같다. 1. 어떤 부분 문자열은 어떤 접미사의 접두사이다.2. 그런데 어떤 두 접미사끼리 서로 접두사가 같은 부분이 있다면 그 부분은 부분문자열중 생김새가 같은 문자열이다.3. 따라서 총 부분문자열의 갯수에서 생김새가 같은 문자열(lcp)의 모든 갯수(lcp의 합)을 뺀다. ababc를 예로 들어보자ababc의 접미사는 ababcabcbabcbcc이다.따라서 모든 부분문자열은 ababc => a, ab, aba, abab, ababcabc => a, ab, abcbabc => b, ba, bab, babc.. 백준 9248 Suffix Array https://kks227.blog.me/221028710658https://stackoverflow.com/questions/17761704/suffix-array-algorithm 링크와 주석으로 설명을 대체한다#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; const int MAX = 1000000; int sa[MAX], temp[MAX], pos[MAX], N, delta, lcp[MAX]; char S[MAX]; //pos[x] : S[x:-1]의 그룹 번호 //sa[x] : suffix들을 정렬했을때, x번째 suffix의 index //temp[x] : suffix들을 정렬했을때, x번째 suff.. 백준 4354 문자열 제곱 KMP알고리즘을 수행하면 계산되는 pi배열 ( 다른말로 실패함수)를 이용한다. 다음과 같은 표를 살펴보자(len은 문자열의 길이를 의미) 문자열 pi[len] abab 2 ababab 4 abcabc 3 aaaa 3 asd 0 pi[len]은 문자열의 접두사 = 접미사인 index +1을 가리킨다.즉, pi[len]은 반복되는 문자열의 길이가 반복될 수 있는 최대 길이를 의미한다.이 말은 다른 말로, len - pi[len]이 문자열에서 반복되는 부분문자열의 최소 길이이다.그런데 만약 len-pi[len]이 len으로 나누어 떨어진다면? len은 위에서 말한 부분문자열로만 이루어져있는 것이다.따라서 위의 예시처럼 text[0~len-pi[len]]만큼의 부분문자열이 반복되는 것을 볼수 있다. 한편, le.. 백준 1701 Cubeditor KMP알고리즘을 수행할 때 pi를 구한다.그런데 만약 pattern에 2번 이상 반복되는 부분 문자열이 있다면 pi에 그 부분문자열의 길이가 기록 된다. 예를들어 pattern이 aabcaa라고 하자.그렇다면 index가 6일때 접두사와 접미사가 같은 부분이 나오고, pi[6] = 2로 기록된다.그런데 이 값은 접두사와 접미사가 같은 부분의 길이를 의미하기도 한다. 따라서 pi[6]의 값은 pi[0~6]의 최대 길이 중복 부분 문자열의 길이(우리가 구하고 싶은 값)가 된다. 또 다른 예로 pattern을 aabcaabxx라고 하자.이 패턴에서는 index가 6일때 마찬가지로 접두사와 접미사가 같은 부분이 나오고, index가 7일때 또 한번 나온다. (pi[6] = 2, pi[7] = 3)따라서 pi의 .. [python3] 백준 1786 찾기 KMP알고리즘으로 풀면 된다. http://deque.tistory.com/78 text = input() pattern = input() pi = [0 for i in range(0, len(pattern))] result = list() count = 0 j=0 for i in range(1,len(pattern)): while(j > 0 and pattern[i] != pattern[j]): j = pi[j - 1] if(pattern[i] == pattern[j]): j+=1 pi[i] = j j = 0; patternLength = len(pattern) textLength = len(text) for i in range(0, textLength): while(j > 0 and text[i] !.. 백준 1015 수열 정렬 //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include using namespace std; vector sortArr; vector prevArr; vector isFill; int main() { int N; scanf("%d", &N); int temp; for (int i = 0; i < N ; i++) { scanf("%d", &temp); sortArr.push_back(temp); prevArr.push_back(temp); isFill.push_back(false); } sort.. 백준 1016 제곱 ㄴㄴ수 에라토스테네스의 체 문제이다 만약, "min에서 max까지 순회하면서 각 값이 2~백만의 값의 제곱수로 나누어 떨어질경우 pass" 하는 식으로 알고리즘을 짜면 n^2이 되기때문에 시간초과가 난다. 따라서 백만짜리 배열을 선언하고 # "i"는 2~max까지 순회하며 다음을 반복 ## (i*i) * j 는 제곱 YES수이므로 배열[(i*i) * j]를 true로 바꾼다. 다만 (i*i) * j의 값을 min~max 사이로 해싱한다 민다 j+=1. ## # 마지막에 배열에서 false가 몇개인지 샌다 # 와 같은 알고리즘은 배열의 값을 중복해서 체크하는 경우가 거의 없기 때문에 시간복잡도를 n으로 봐도 되므로(즉, 백만) 시간 안에 해결 가능하다. #include using namespace std; boo.. 백준 10217 KCM Travel 분명 풀기는 다풀었는데어이없이 몇번이고 시간초과가 났다.원인은 cmp.....템플릿에 cmp를 넣다보니 뒤죽박죽으로 섞여서 cmp가 제대로 구현이 안됐는데, 예제는 잘돌아가서 문제인지도 모르고 막 제출했다..이거 하나때문에 2시간을... 알고리즘을 할땐 내가 뭘 만들려고 하지말고 조용히 pair를 애용하자 다익스트라알고리즘을 수행하되, 다음과 같이 memo를 한다.memo[i][j] = i번째 노드에 j의 cost로 도달 할 수 있는 최소의 거리그리고if (memo[now][edge.Cost] M) continue;등으로 적당히 가지를 쳐주면 된다. //.. 이전 1 2 3 4 5 6 ··· 9 다음