1. 분할 정복(divide and conquer) 분할 = 큰 문제를 여러 개의 작은 문제로 쪼갠 다음 정복 = 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법 충분히 크기가 큰 문제를 쉽게 해결할 수 있는 부분 문제로 분할해 나가고, 분할된 하위 문제를 해결하여 이 결과를 조합하여 윗단계 문제에 대한 답으로 낸다 2. 방법 정답을 쉽게 도출할 수 있을 때까지 재귀적으로 분할된 단위로 자신을 호출하면서 범위를 조금씩 줄여나감(분할단계) 답을 쉽게 도출하는 단계까지 도달한다면 재귀함수는 정답을 return하고 이렇게 return하면서 이를 이용해 재귀 stack에 쌓인 윗단계 재귀함수의 값을 return해나가는 것이 정복단계 def f(x): if (f(x)가 간단함): return f(x) el..
https://cp-algorithms.com/string/suffix-array.html#definition Suffix Array - Algorithms for Competitive Programming Suffix Array Definition Let $s$ be a string of length $n$. The $i$-th suffix of $s$ is the substring $s[i \ldots n - 1]$. A suffix array will contain integers that represent the starting indexes of the all the suffixes of a given string, after the aforemen cp-algorithms.com https:/..
https://cp-algorithms.com/string/prefix-function.html Prefix function - Knuth-Morris-Pratt - Algorithms for Competitive Programming Prefix function. Knuth–Morris–Pratt algorithm Prefix function definition You are given a string $s$ of length $n$. The prefix function for this string is defined as an array $\pi$ of length $n$, where $\pi[i]$ is the length of the longest proper prefix cp-algorithms..
String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing strings efficiently. The brute force way of doing so is just to compare the letters of both strings, which has a time complexity of $O(\mi cp-algori..
1. 문자열에서 마지막 문자 인덱싱 알파벳으로 이루어진 10개의 문자열과 문자가 하나 주어지면 그 문자로 끝나는 문자열들을 입력에서 주어진 순서대로 출력하는 프로그램을 작성해보세요. string arr[10];으로 string 타입을 원소로 가지는 크기 10의 배열을 선언할 수 있다. 파이썬과 비슷하게 문자열 인덱싱이 가능하지만, 파이썬처럼 s[-1]로 마지막 문자를 가져올 수는 없다.. 음수 인덱스를 사용하지 못한다는 소리 s.length()로 문자열 s의 길이를 가져오고, s.length()-1로 바로 마지막 문자에 접근할 수 있다. #include #include using namespace std; int main() { // 여기에 코드를 작성해주세요. string arr[10]; for(int..
1. 문제 12904번: A와 B (acmicpc.net) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 2. 풀이 S에서 T를 만들려고만 한다면 이 문제가 상당히 어렵다 그냥 왠지 모르지만 어떤 문제든 역으로 시도해볼때 뭔가 보일수도 있다 조금 생각해보면 1) 문자열의 뒤에 A를 추가한다 2) 문자열을 뒤집고 뒤에 B를 추가한다 두 연산만으로 S에서 T가 만들어졌는데 문자열 T가 ABBA인 경우를 생각해보자. ABBA는 이전에 어떤 문자열이었을까? 오직 1가지인 ABB인..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
