걸음마코딩기

KMP 알고리즘이란 ? 최대 접두부를 구현하여 불일치를 감지할 때마다 이전의 일치 문자열로 돌아가 점프하는 방식으로 시간 복잡도는 최악의 경우 O(N) : 문자열 길이 * 패턴 길이 [ 구성 요소 ] lps[] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대길이 저장 pattern[] : 패턴 문자열 text[] : 주어진 문자열 KMP 알고리즘 함수 구현하기 예시 문자열 ) ABAABAB i 문자열 lps[i] 0 A 0 1 AB 0 2 ABA 1 3 ABAA 1 4 ABAAB 2 5 ABAABA 3 6 ABAABAB 2 => lps에 최대길이인 3이 들어감 lps 구현 코드​ void lps_array(string pattern, int M, int lps[]) { int len = 0; //접두..

[ 구현 방법 ] [ vector 이용 ] void Array() { int n, m; cin >> n >> m; vector array; for(int i=0; i> input; array.push_back(input); } for(int i=0; i> input; array.push_back(input); } sort(array.begin(), array.end()); for(auto a : array) cout n >> m; int arr_a[n], arr_b[m], arr[n+m]; for(int i=0; i> arr_a[i]; for(int i=0; i> arr_b[i]; while(check_n + check_m < n + m) { if(check_n == n) cout

[ 구현 방법 ] [ 코드 ] #include #define sync ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); using namespace std; void func() { int n; long binary[90]; binary[0] = 1; binary[1] = 1; cin >> n; for(int i=2; i

각각 10개의 입력으로 정해져 있으므로 크기 10짜리 배열 2개를 만들어 입력을 받아주고 sort함수를 이용하여 내림차순으로 정렬을 해주었다. 높은 점수 순으로 3명의 점수만 합산되므로 3번째까지의 점수를 각각 더해주어서 출력해주었다. #include #include #define sync ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); using namespace std; void Contest(){ int W[10], K[10]; int W_score = 0; int K_score = 0; for(int i=0; i> inp; W[i] = inp; } sort(W, W+10, greater()); for(int i=0; i> inp; K[i]..

원리 퀵정렬은 Divide & Conquer algorithm중 하나로 "pivot"이라는 기준값을 지정하여 pivot을 기점으로 배열을 partitioning하여 정렬하는 알고리즘이다. 보통 pivot은 배열의 맨 앞 원소를 지정하는데 두번째 원소부터 오른쪽으로 pivot보다 큰값을 찾고, 맨 마지막 원소부터 왼쪽으로 pivot보다 작은 값을 찾아나간다. 만약 왼쪽으로 훑던 것이 오른쪽을 추월한다면 pivot과 오른쪽 기준을 swap하고 그렇지 않다면 왼쪽 오른쪽 값을 swap한다. Complexity 모든 원소를 한번씩 훑기때문에 O(n), 배열을 반으로 계속 divide하기 때문에 O(log2n)으로 총 O(nlogn)이라는 빠른 속도를 가진다. 주의사항 - Worst Case ! 배열이 이미 정렬..