Taene's

슬라이딩 윈도우범위를 지정하고, 범위를 유지한 채로 이동하며 문제를 해결한다.투 포인터 알고리즘과 비슷하다.슬라이딩 윈도우의 크기(탐색 범위)는 일정하다. 관련 문제들백준 12891 (실버2)#include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int s, p; cin >> s >> p; //dna문자열의 길이 s, 비밀번호로 사용할 부분 문자열의 길이 p string dnaString; cin >> dnaString; char ACGT[4] = { 'A','C','G','T' }; int ACGTNum['Z'] = {}; // A,C,G,T 각각의..

투 포인터2개의 포인터를 이용해 알고리즘의 시간 복잡도를 최적화한다.시간 복잡도에서 N의 최댓값이 10,000,000 처럼 매우 크게 잡혀 있는 경우, O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 하는데, 이런 경우 투 포인터 알고리즘을 자주 사용한다. 관련 문제들백준 2018 (실버5)#include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; int start_index = 1; int end_index = 1; int cnt = 1; int sum = 1; while (end_ind..

구간 합의 핵심 이론합 배열 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] ( 배열 A의 0~i까지의 합 배열 S)합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) -> O(1)로 감소한다.합 배열 S를 만드는 공식S[i] = S[i-1] + A[i]구간 합을 구하는 공식S[j] - S[i-1] ( i~j까지의 구간 합) 관련 문제들백준 11659 (실버3)#include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M; int k; cin >> N >> M; int sum[100001] = {};..

1. 재귀로 배열의 합 구하기#include using namespace std;int Sum(int* arr, int n){ int s = 0; for (int i = 0; i  2. 피보나치 수열//

- 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘이다. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀함수, 반복문, STL의 3가지 방법을 이용해 이분 탐색(Binary Search)을 실행할 수 있다. - 시간복잡도 : O(log N) 1. int left, int right - 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수이다. - left는 시작점을, right는 끝점의 인덱스를 가리킨다. 2. int mid - 검사 범위 (left ~ right)내에서 실질적으로 검사하는 인덱스를 가리키는 변수이다. - 검사하는 값은 검사 범위의 중간 값이다. - 이 값(mid)과..

- 문자열 문제에 삽입정렬과 선택정렬을 접목시켜보았다. #include using namespace std; int StartCount(char* arr, int size, int startIndex) { int count = 0; int i = startIndex; for (; arr[startIndex] == arr[i++]; count++); return count; } int SortArrayCount(char* arr, int size, int index) { return StartCount(arr, size, index); } void InsertionSort(char* arr, int size) { for (int i = 0; i ar..