시간복잡도
- c++에서는 1억번의 연산 = 1초의 수행시간
시간 복잡도 유형
- 빅 오메가 : 최선일때 연산횟수(운이 좋은 것)
- 빅 세타 : 보통일때 연산횟수
- 빅오 : 최악일때 연산횟수, 빅오를 기준으로 수행시간을 계산하는 게 좋다.
알고리즘 선택의 기준으로 사용하기
- 버블 정렬 : 시간 복잡도 O(n^2)
- 병합 정렬 : 시간 복잡도 O(nlogn)
시간 제한이 2초면, 2억번 이하 연산으로 문제를 해결해야한다.
따라서 시간제한, 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야할지 알 수 있다.
**
**
연산횟수 계산방법
- 연산횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입해서 도출할 수 있다.
시간제한 : 2초, 데이터의 최대 크기 : 100만일때
버블정렬
- (1000000)^2 = 1000000000000 > 200000000 : 부적합 알고리즘이다.
병합정렬
- 1000000log(1000000) = 20000000 < 200000000 : 적합 알고리즘이다.
시간복잡도를 바탕으로 코드로직 개선하기
🌟🌟🌟
시간복잡도
1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행횟수가 시간 복잡도의 기준이 된다.
3. 알고리즘 선택 기준이 된다.
4. 시간초과시 내 비효율적 코드가 어딘지 판단 기준이 된다.
5. 시간복잡도는 최악의 케이스를 기준으로 계산해야한다.
[예제1]
for(int i = 0; i < N; i++){
cout << "연산 횟수" << cnt++ << "\n";
}
for(int i = 0; i < N; i++){
cout << "연산 횟수" << cnt++ << "\n";
}
for(int i = 0; i < N; i++){
cout << "연산 횟수" << cnt++ << "\n";
}일반 for문 3개 ⇒ 시간 복잡도 not 3N(상수는 제외하기에) , yes N
for(int i = 0; i < N; i++){
for(int i = 0; i < N; i++){
cout << "연산 횟수" << cnt++ << "\n";
}
}[예제2]
이중 for 문 : N^2
만약, 이중 for문이 10개 있어도 : N^2
디버깅
- 특정 코테에서는 디버깅 못하는데 공부해야하나..?
: 디버깅은 중요하다. 디버깅 많이 하면 컴퓨터의 프로세스대로 어떻게 동작하는지 이해도가 높아진다.
벡터🌟
- 배열의 특징을 가지면서 배열의 단점을 보완(초기 사이즈 정하면 바꾸지 못함)한 동적 배열의 형태
- 동적으로 원소를 추가할 수 있다.(크기가 자동으로 늘어남)
- 맨 뒤 위치에 삽입, 삭제시 문제가 없다. 중간 데이터의 삽입, 삭제는 배열같은 매커니즘으로 동작한다.
- 인덱스를 이용해 데이터에 직접 접근할 수 있다.
- 코테에서 가장 많이 사용한다.
- 기본 사용법 :
#include<vector>필요 vector<자료형> name으로 지정
#include <iostream>
#include <vector>
using namespace std;
void main() {
ios_base::sync_with_stdio(false); // 동기화해제
cin.tie(NULL); // 입력, 출력 버퍼 비우기
vector<int> A;
A.push_back(10);
A.push_back(30);
A.push_back(5);
A.push_back(8);
A.push_back(6);
A.push_back(1);
A.insert(A.begin(), 7);
A.insert(A.begin()+2, 7);
A[4] = -5;
A.pop_back(); //마지막 값 삭제
A.erase(A.begin() + 3);
cout << A.size() << "\n";
cout << A.front() << "\n"; // 처음 값
cout << A.back() << "\n"; // 마지막 값
cout << A[3] << "\n";
cout << A.at(5) << "\n";
A.clear(); // 모든값 삭제
}