출처:
10주완성 C++ 코딩테스트 | 알고리즘 IT취업 - 인프런 | 강의
수업을 듣고 정리한 글입니다.
시간 복잡도
시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며
주요로직의 반복횟수를 중점으로 측정한다.
몇 번 반복되었는지
빅오 표기법
영향을 많이 끼치는 항을 기준으로 구한다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
상수시간 시간복잡도 O(1)
입력과 출력
ex) cin, cout, scanf, printf
곱하기, 나누기, 나머지연산, 빼기
a[2] *= 2;
간단한 비교 if문
if(a[2] == 2)
배열의 인덱스 참조
int a[3] = {1, 2, 3}; int b = a[2];
시간복잡도가 헷갈릴때
cnt로 몇번 반복되는지 디버깅 한 후, 표를 그려서 시간복잡도를 유추한다.
Q1. 다음 코드의 시간복잡도는?
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
int a = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
a += i + j;
}
}
cout << a << '\\n';
return 0;
}
O(n^2)
Q2.
#include<bits/stdc++.h>
using namespace std;
int N, M;
void solve(int N, int M){
int a = 1;
for (int i = 0; i < N; i++) {
a *= i;
}
for (int j = 0; j < M; j++) {
a *= j;
}
cout << a << "\\n";
}
int main(){
cin >> N >> M;
solve(N, M);
return 0;
}
O(N+M)
입력값 변수 여러개일때 나열하기(O(N*M)도 가능)
N^2+N+M^2+M일때 → O(N^2+M^2)
Q3.
#include<bits/stdc++.h>
using namespace std;
int n, a[1004], cnt;
int go(int l, int r){
if(l == r) return a[l];
int mid = (l + r) / 2;
int sum = go(l, mid) + go(mid + 1, r);
return sum;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
a[i - 1] = i;
}
int sum = go(0, n - 1);
cout << sum << '\\n';
}
O(n)
한 함수당 2번 호출(2^n) 그런데 수는 절반으로 줄어듬(log2n) ⇒ O(n) 추측가능
반복횟수 cnt로 디버깅하기
#include<bits/stdc++.h>
using namespace std;
int n, a[1004], cnt;
int go(int l, int r){
cnt++;
if(l == r) return a[l];
int mid = (l + r) / 2;
int sum = go(l, mid) + go(mid + 1, r);
return sum;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
a[i - 1] = i;
}
int sum = go(0, n - 1);
cout << sum << '\\n';
cout << cnt;
}
Q4.
#include<bits/stdc++.h>
using namespace std;
int N;
void solve(int N){
int a = 0, i = N;
while (i > 0) {
a += i;
i /= 2;
}
cout << a << '\\n';
}
int main(){
cin >> N;
solve(N);
return 0;
}
계속해서 나눈다.
O(logN)
재귀함수의 시간복잡도: Main Logic * 몇번 호출되었는지
Q5.
#include<bits/stdc++.h>
using namespace std;
int N, cnt;
void solve(int N){
//main logic은 O(1)
cnt++;
cout << cnt << '\\n';
if(N == 0) return;
//한번 호출시마다 3번 함수 호출
for(int i = 0; i < 3; i++){
solve(N - 1);
}
return;
}
int main(){
cin >> N;
solve(N);
return 0;
}
O(1) * O(3^n) ⇒ O(3^n)
함수 하나당 3번 호출되면 → 3^n
함수 하나당 4번 호출되면 → 4^n
⇒ 자신이 짠 코드의 시간복잡도를 계산해서 시간초과 가능성이 있는지 확인하기.
자료구조의 시간복잡도
작업을 할때 시간이 적게 걸리는 자료구조를 사용하자.
배열(Array)
- 참조 : O(1)
- 탐색 : O(n)
벡터(vector)
- 참조 : O(1)
- 탐색 : O(n)
- 맨 끝, 앞에 삽입/삭제 : O(1)
- 중간에 삽입 / 삭제 : O(n)
스택(stack)
- 참조 : O(n)
- 탐색 : O(n)
- 삽입 / 삭제 : O(1)
큐(queue)
- 참조 : O(n)
- 탐색 : O(n)
- 삽입 / 삭제 : O(1)
연결리스트(doubly linked list)
- 참조 : O(n)
- 탐색 : O(n)
- 삽입 / 삭제 : O(1)
맵(map)
- 참조 : O(nlogn)
- 탐색 : O(nlogn)
- 삽입 / 삭제 : O(O(nlogn)
공간 복잡도
입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양
→ 문제를 풀 때 잘 사용하지 않는다.
배열의 범위
문제의 1. 최대 범위 2. 메모리 제한을 고려한다
ex) 512MB → 512,000,000 /4 = int a[128,000,000]
근데 메모리 제한은 거의 고려하지않고(그럴 시간이 없음) 최대 범위를 고려하는데.
1000만이 상한선이라고 볼 수 있다(1000만을 필요로 하는 알고리즘은 잘못되었을 가능성이 높음)
누적합
요소들의 누적된 합,
어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것
앞에서부터 더하는 prefix sum을 많이 사용한다.
문제를 풀 때 "구간"에 대한 많은 "쿼리"가 나올 때 생각해야 될 것은 트리 또는 누적합입니다.
여기서 트리는 세그먼트, 펜윅트리를 뜻합니다.
이 때 그 구간 안에 있는 요소들이 변하지 않는 정적 요소라면 누적합을 쓰면 됩니다.
**예시문제**
승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주며 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해보자.
**입력**
수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. 수는 100 이하의 자연수. 그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다.
**출력**
M개의 줄에 A부터 B까지의 합을 구하라.
**범위**
1 <= N <= 100,000
1 <= M <= 100,000
1 <= A <= B <= N
**예제입력**
8 3
1 2 3 4 5 6 7 8
1 4
1 5
3 5
**예제출력**
10
15
12
시간초과가 날 수 있는 구현
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100004], b, c, psum[100004], n ,m;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 0 ; i < m; i++){
cin >> b >> c;
int sum = 0;
for(int j = b; j <= c; j++) sum += a[j];
cout << sum << '\\n';
}
return 0;
}
이렇게 구현했을때 시간복잡도는 O(n^2)이 나오게 되고,
N과 M은 10만까지 범위이므로 100억번 반복가능하다(시간초과 발생)
⇒ 정적배열(배열의 요소들이 변하지 않으므로) 누적합 사용하기
누적합 logic
매번 반복문을 사용해서 구간의 합을 구하는 것이 아닌 누적합 배열 원소끼리의 뺄셈으로 구할 수 있다.
구간이 b~c라면 psum[c]-psum[b-1]이다.
시간복잡도 : 10만 * 1(뺄셈이므로)
구현
누적합 배열을 구할때는 한 원소마다 누적합을 구해서 더하는 것이 아닌,
그 전 원소의 누적합에 지금 위치의 원소를 더해 “누적으로 구한다”.
psum[2]= psum[1]+a[2]
⇒ psum[i] = psum[i-1] + a[i]
- i-1이므로 i는 1부터 시작해야한다.
- 전역변수로 psum을 선언한다면 모든 원소는 0으로 초기화되어있을것이므로 psum[0]=0이다.
- 배열의 범위는 N,M이 100000이므로 100004정도로 선언한다.
#include <bits/stdc++.h>
using namespace std;
int a[100004],b,c,psum[100004],n,m;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//n: 수의 개수, m: 합을 구해야하는 횟수(구간 개수)
cin >> n >> m;
//숫자 입력받고 누적합 구하기
for(int i=1;i<=n;i++){
cin >> a[i];
psum[i] = psum[i-1]+a[i];
}
//m개의 구간 입력받아 구하기
for(int i=0;i<m;i++){
cin >> b >> c;
cout << psum[c]-psum[b-1] << "\\n";
}
}
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);는 실행속도를 높이기 위해 작성한다.
(c의 stdio와 c++ iostream 동기화하지않고, cin과 cout 묶음 풀기)
참고로 endl은 출력과 함께 출력버퍼를 비우므로 지연이 발생한다. “\n”을 사용하자.
Significance of ios_base::sync_with_stdio(false); cin.tie(NULL);
ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유
글 읽기 - 추가 설명 및 다른 언어 빠른 입출력 방법
구현과 문제를 푸는 방법의 기초
문제를 나눠서 주석을 달고, 하나하나 풀면 된다.
string dopa = "umzunsik";
Q1. 앞에서부터 3개의 문자열을 출력하라
Q2. 해당 문자열을 거꾸로 해서 출력하라.
Q3. 해당 문자열 끝에 "umzunsik"이란 문자열을 추가하라.#include <bits/stdc++.h>
using namespace std;
string dopa = "abcde";
int main(){
cout << dopa << "\\n";
//1. 앞에서부터 3개의 문자열 출력
cout << dopa.substr(0,3) << "\\n";
//2. 문자열 거꾸로 출력
reverse(dopa.begin(), dopa.end());
cout << dopa << "\\n";
//3. 해당 문자열 끝에 엄준식 추가
cout << dopa + " umzunsik";
return 0;
}
- 문제를 보고
- 문제를 해석하고 (범위, 어떤 자료구조, 어떤 단계를 거칠지 생각)
- 코드를 짠다
문제를 풀때 생각할 점
- 최대, 최소 범위 파악
- 단순 구현이라면 구현
- 무식하게 풀 수 있다면 무식하게 풀자(brute force부터 해보기).
- 아니라면 다른 알고리즘을 생각하자(greedy,dp,최단거리..)
- 제출하기전, 반례를 항상 생각하자.(외부 TC 맞아도 내부 TC에서 틀릴 수 있다.)
'알고리즘 > C++' 카테고리의 다른 글
| string STL (0) | 2022.12.28 |
|---|---|
| C++ 기본 (0) | 2022.12.28 |
| 알고리즘 암기할 코드들 (0) | 2022.12.27 |
| 0주차: 재귀, 순열, 조합, split (1) | 2022.12.27 |
| std::deque(덱) (0) | 2022.12.26 |
