시간복잡도
빅오 표기법
안에 숫자가 더클수록 느리다.
알고리즘 평가 지표
1)시간복잡도
2)메모리 사용량
왜쓰냐?
어떤 알고리즘을 사용할지 힌트를 얻기 위해서
즉, 빨리 코테 풀기 위함,
많이쓰는 거
1) O(logn) -> O(1)
2) O(nlogn) -> O(n)
log의 밑 지수를 10 이 아니고 2라고 생각한다!
O(1)
order 1 은 n값이 몇이든 한번 반복한다고 생각한다.
O(nlogn)
[문제1]
n이 1억이면 몇번 반복?
27번!
힌트를 알아내고 그범위 안에서 ,,,문제를 해결
[문제2]
시간제한 5초
n 20,000번
[정답]
2중 for문
[문제3]
시간제한 3초
n 500
[정답]
3중for문
힌트 확인 방법
1) n=15 다 -> 백트래킹, 재귀,,
재귀가 무조건 답이 아니고 재귀를 먼저 생각해 보는것이 좋다,,
2)n이 100,00 이다 숫자가 크다,,
-> 재귀는 생각도 하지 마라
3)n= 50~100 ,2중 for문 최솟값 BFS
메모리
1) int : 4Byte
2) char : 1Byte
3) int * : 8Byte
32bit - 4Byte
64bit - 8Byte
1Byte=8bit
#include <iostream>
using namespace std;
int v[1000];
char g[400];
char* p[50];
int main() {
return 0;
}
[정답]
4800Byte
메모리 빈공간을 둔다
왜냐? cpu가 변수를 읽기위해서는 한번만 읽어야하는데,잘려져 있으면 2번 읽어야하기때문에, 가장 큰 변수를 가로 크기로 두고, 변수를 읽을때 한번만 읽을수 있도록
->패딩전략
[문제]
#include <iostream>
using namespace std;
struct Node {
char b;
int a;
int* p;
};
int main() {
Node v;
cout << sizeof(v);
return 0;
}
[출력]
16
메모리 배우는 이유
메모리는 하지 말아야하는것을 알려준다.
슬라이딩 윈도우
#include <iostream>
using namespace std;
int arr[11] = { 4,5,1,1,5,4,-3,-13,9,20,13 };
int getSum(int idx) {
int sum = 0;
/*for (int i = idx; i < idx + 5; i++) {
sum += arr[i];
}*/
for (int i = 0; i < 5; i++) {
sum += arr[idx + i];
}
return sum;
}
int main() {
cout << getSum(1);
return 0;
}[정답]
6
[문제]
가장 max값이 나오는 값 출력
#include <iostream>
using namespace std;
int arr[11] = { 4,5,1,1,5,4,-3,-13,9,20,13 };
int getSum(int idx) {
int sum = 0;
/*for (int i = idx; i < idx + 5; i++) {
sum += arr[i];
}*/
for (int i = 0; i < 5; i++) {
sum += arr[idx + i];
}
return sum;
}
int main() {
int maxIdx;
int maxN = -1000;
for (int i = 0; i < 6; i++) {
int ret = getSum(i);
if (ret > maxN) {
ret = maxN;
maxIdx = i;
}
}
cout << maxIdx;
return 0;
}
vect 배열 N칸개
연속된 구간 R개 연속
->O(RN) == 간단하게 O(n제곱)
여기서!! 슬라이딩 윈도우 사용하면, O(N)으로 줄일수 있다.
슬라이딩 윈도우 사용법
내가 생각한고 맞네~><
#include <iostream>
using namespace std;
int arr[11] = { 4,5,1,1,5,4,-3,-13,9,20,13 };
int sum = 0;
int main() {
for (int i = 0; i < 5; i++) {
sum += arr[i];
}
cout << sum << "\n";
for (int i = 1; i < 6; i++) {
sum = sum - arr[i - 1] + arr[i + 5];
cout << sum << "\n";
}
return 0;
}
[코드]
#include <iostream>
using namespace std;
int arr[11] = { 4,5,1,1,5,4,-3,-13,9,20,13 };
int sum = 0;
int getSum(int idx) {
for (int i = 0; i < 5; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int sum = getSum(0);
int maxN = sum;
int maxIdx = 0;
for (int i = 0; i <= 11 - 5; i++) {
if (maxN < sum) {
maxN = sum;
maxIdx = i;
}
if (i == 11 - 5)break;
//다음것 미리 준비
sum -= arr[i];
sum += arr[i + 5];
}
cout << maxN << " " << maxIdx;
return 0;
}
슬라이딩 윈도우 할때 바운더리 조심하기!
런타임 에러 날수도 있음
슬라이딩 윈도우 for문 횟수는?
배열칸-구하고싶은숫자 갯수
for(int i=0;i<=배열칸-구하고싶은숫자갯수;i++)
슬라이딩 윈도우 연습
string 클래스 사용법
#include <iostream>
#include <string>
using namespace std;
int main() {
string a = "ABA";
//추가하는거
a += "D";
cout << a << "\n";
//지우는거
//0 번 index부터 1개
a.erase(0, 1);
cout << a << "\n";
return 0;
}[문제]
#include <iostream>
#include <string>
using namespace std;
int cnt = 0;
string a = "ABABTABCABABAACD";
string temp;
string arr = "ABA";
string isCheck(int idx) {
temp = a.substr(idx, 3);
return temp;
}
int main() {
temp = isCheck(0);
for (int i = 0; i <= a.length() - 3; i++) {
if (temp == arr)cnt++;
if (i == a.length() - 3)break;
temp.erase(0, 1);
temp += a[i + 3];
}
cout << cnt;
return 0;
}
[출력]
3
[코드]
#include <iostream>
#include <string>
using namespace std;
string a = "ABBABQAADAA";
int main() {
int dat[100] = {0};
string sum = a.substr(0, 4);
for (int i = 0; i < 4; i++) {
dat[sum[i]]++;
}
int maxn = 0;
int limit = a.length() - 4;
for (int i = 0; i <= limit; i++) {
cout << sum << "\n";
if (i == limit)break;
//갱신하기
sum.erase(0, 1);
sum += a[i + 4];
}
return 0;
}
[깨달은고!!!]
아아아 내가한고는 O(n제곱)된다.
계속 의문 들었던거..
슬라이딩 윈도우는 O(n)인데!!!!!
준비할때 바로 dat에 ++하면 된다!
할슈이땨!
[출력]
3
2)아이디어 코드
->요거 사용하기
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string a = "ABBABQAADAA";
int main() {
int dat[100] = { 0 };
//dat에 바로 적용!!!!
for (int i = 0; i < 4; i++) {
dat[a[i]]++;
}
int maxN = 0;
int limit = a.length() - 4;
for (int i = 0; i <= limit; i++) {
if (maxN < dat['A'])maxN = dat['A'];
if (i == limit)break;
dat[a[i]]--;
dat[a[i + 4]]++;
}
cout << maxN << "\n";
return 0;
}
[출력]
3
[문제]
1)코드
#include <iostream>
using namespace std;
int arr[15] = { 4,5,6,1,1,3,2,6,9,1,1,2,0,3,2 };
int idx;
void go() {
for (int i = 14; i > 0; i--) {
int n = i;
int sum = 0;
for (int x = 0; x < n; x++) {
sum += arr[x];
}
int limit = 15 - n;
for (int j = 0; j <= limit; j++) {
if (sum == 7) {
idx = n;
cout << idx << "\n";
return;
}
if (j == limit)break;
sum -= arr[j];
sum += arr[j + n];
}
}
}
int main() {
go();
return 0;
}
[출력]
5
2)코드
#include <iostream>
#include <vector>
using namespace std;
vector<int>v = { 4,5,6,1,1,3,2,6,9,1,1,2,0,3,2 };
int isSeven(int n) {
//n은 구간이다.
int sum = 0;
for (int x = 0; x < n; x++) {
sum += v[x];
}
int limit = v.size() - n;
for (int i = 0; i <= limit; i++) {
if (sum == 7)return 1;
if (i == limit)break;
sum -= v[i];
sum += v[i + n];
}
return 0;
}
void go() {
for (int i = v.size() - 1; i >= 0; i--) {
int ret = isSeven(i);
if (ret == 1) {
cout << i << "\n";
return;
}
}
}
int main() {
go();
return 0;
}
BOSS문제!!
유일하게못푼고 ㅠㅠ힝
[문제]
[아이디어]
신규추가된것을 갱신해준다!!!!!!
#include <iostream>
#include <string>
using namespace std;
//a가 나온 횟수
string a = "BAQRRGGVAQZAACT";
int dat[100] = { 0 };
int main() {
//둘다 갱신해줌
int maxCnt = 0;
char ch;
for (int i = 0; i < 5; i++) {
dat[a[i]]++;
if (dat[a[i]] > maxCnt) {
maxCnt = dat[a[i]];
ch = a[i];
}
}
int limit = a.length() - 5;
for (int i = 0; i <= limit; i++) {
dat[a[i]]--;
dat[a[i + 5]]++;//<--이 아이가 신규 추가 된것
//max 갱신해 준다.
if (maxCnt < dat[a[i + 5]]) {
maxCnt = dat[a[i + 5]];
ch = a[i + 5];
}
if (i == limit)break;
}
cout << ch << "\n";
return 0;
}
[출력]
A
computer_log