C++ 코딩테스트 Week 01

시간, 공간 복잡도

복잡도는 시간복잡도와 공간복잡도로 나뉜다.

시간 복잡도(Time complexity)

---

입력 크기에 대해 알고리즘이 실행되는데 걸리는 시간

주요 로직의 반복횟수를 중점으로 측정된다

빅오 표기법으로 복잡도에 가장 영향을 많이 끼치는 항을 나타낸다

재귀함수에서의 메인로직은 시간복잡도가 어느정도 큰 주요로직이다

자료구조에 대한 시간복잡도는 아래와 같다

배열(Array)

- 참조 : O(1)

- 탐색 : O(n)

배열(vector)

- 참조 : O(1)

- 탐색 : O(n)

- 맨 끝, 앞에 삽입/삭제 : O(1)

- 중간에 삽입 / 삭제 : O(n)

스택(stack)

- n번째 참조 : O(n)

- 가장 앞부분 참조 : O(1)

- 탐색 : O(n)

- 삽입 / 삭제(n번째 제외) : O(1)

큐(queue)

- n번째 참조 : O(n)

- 가장 앞부분 참조 : O(1)

- 탐색 : O(n)

- 삽입 / 삭제(n번째 제외) : O(1)

연결리스트(doubly linked list)

- 참조 : O(n)

- 탐색 : O(n)

- 삽입 / 삭제 : O(1)

맵(map)

- 참조 : O(logn)

- 탐색 : O(logn)

- 삽입 / 삭제 : O(logn)

[출처] [알고리즘 강의] 1주차. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현

작성자 큰돌

참고로 Map 자료구조는

Key와 Value의 쌍으로 이루어진 자료구조를 말한다

레드 블랙 트리 자료구조를 기반으로 형성되기 때문에 logn의 시간이 든다

---

공간 복잡도 (Space Complexity)

---

입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양을 말하는데,

정적 변수말고도 동적으로 재귀함수로 인해 필요한 공간등의 모든 메모리의 공간을 의미한다

일반적으로 10^8 까지는 쓸 수 있고, 일반적으로 공간 복잡도에 의하여 제한사항에 걸리는 경우는 잘 없다

문제를 풀때, 배열의 크기가 천만이면 배열의 크기를 다시 고려해보아야 한다

---

누적합

누적합이란 말 그대로 배열의 누적된 합을 의미하고, 누적합으로 배열을 생성한 것을 말한다

앞에서부터 더하는 prefix sum, 뒤부터 더하는 suffix sum이 있다

이렇게 아예 적분하듯이 누적합을 구해놓으면 구간쿼리에 대해 대응하기가 쉽다

문제를 풀때 구간에 대한 많은 쿼리가 나올때 트리, 누적합을 생각해라

여기서 트리는 세그먼트, 펜윅트리를 말한다

그리고 만일 구간안의 요소들이 변하지 않는 정적 요소라면 누적합을 쓰면 된다

예시 코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100004], b, c, psum[100004], n ,m;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	// 배열 만들기 - 1번째 요소부터 만들어야지 arr[i-1]에서 에러가 안남
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		psum[i] = psum[i - 1] + a[i];
	}
  // 부분합 구하기
	for(int i = 0 ; i < m; i++){
		cin >> b >> c;
		cout << psum[c] - psum[b - 1] << "\n";
	}
	return 0;
}
[출처] [알고리즘 강의] 1주차. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현|작성자 큰돌