1주차-0. 기초 개념 : 개념 강의

시간복잡도

• 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

for (int i = 0; i < 10; i++)
	for (int j = 0; j < n; j++)
		for (int k = 0; j < n ; k++)
			if (true) cout << k << '\n';

• 이 식의 구체적인 연산량은 10n² + n이다.
• 가장 영향을 많이 끼치는 항의 계수를 빼고 나머지 항을 없앤 것이 빅-오 표기법이다.
• 대표적으로 입력 크기가 커질수록 연산의 양이 커지는 항을 꼽는다.

시간복잡도는 효율적인 코드로 개선하는데 쓰이는 척도가 된다.

• n의 크기가 10만이라면 n²은 10억인데, 10억은 안된다고 보면 된다.
• 이럴 때 다른 로직을 생각해야 하나? 라는 생각을 할 수 있게 해준다.

C++ STL 컨테이너별 시간복잡도

https://blog.naver.com/yoochansong/221739086178

C++ STL container 시간 복잡도 및 특징 비교.

 

자주 쓰이는 STL 함수 시간복잡도

sort : n log n
lower_bound, upper_bound : n log n
find : n
fill : n
unique : n

 

---

공간복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원의 양
• 동적으로 재귀적인 함수 내부에서 할당하는 것도 포함

배열의 경우 1000만은 안된다고 보면 됨.

 

 

 

 

 

 

---

재귀함수

• 함수를 정의할 때 자신을 재참조하는 함수를 뜻한다.
• 계속해서 자기 자신을 호출하며 인덱스를 변화시키며 같은 로직을 반복 진행하는 경우
• 기저사례(종료 조건)와 메인 로직으로 나누어진다.
• 대표적인 예로 피보나치, 팩토리얼
• 기저사례를 작성하지 않으면 무한루프에 빠지므로 처음에 작성하는 것이 좋다.

int fibonacci(int n)
{
    if (n < 2) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

 

 

 

 

---

누적합

• 미리 요소들의 합을 저장해 두는 누적된 수의 합을 의미
• 앞에서 더하는 prefix sum과 뒤에서 더하는 suffix sum이 있다.

원본     : 0  ->  1  ->  2  ->  3  ->  4  ->  5  -> ...
누적합 : 0  ->  1  ->  3   ->  6 ->  10 -> 15-> ...

• 이렇게 저장해두면 누적합[3] 요소가 원본[0~3]까지 더한 수가 된다
• 따라서 누적합을 사용하려면 이전 것(i-1)과 현재 것(i)을 저장해야 하므로 인덱스는 1부터 시작하는 것이 좋다.
• prefixSum[i] = original[i-1] + original[i];
• 0부터 시작할 경우 original[i-1] 이 부분이 -1이 되기 때문

 

 

 

---

1주차에서 중요한 점

1. 문제를 본다
2. 문제를 해석한다
3. 코드를 작성한다

가장 중요한 것은 2. 문제를 해석한다 이다.

• 최대, 최소 범위 파악
• 무식하게 for문이나 재귀로 풀 수 있는가?
• 최적해가 있는가?
• 단순 구현이라면 반례가 있는가?
• 단순 구현이 아니고 최단거리, 유니온파인드 등의 문제라면?

 

 

 

---

시간복잡도 연습

• 문제를 풀 때는 첫 번째로 무식하게 푼다고 생각하고,
• 그 후에 안될 경우, 그에 맞는 알고리즘을 생각한다.
• 시간복잡도를 좌우하는 것은 반복과 재귀이다.

int i, j, k = 0;
for (i = n/ 2; i <= 2; i++)          //=> N
	for (j = 2; j <= n; j =* 2)      //=> logN
		k = k + n / 2;       		 //=> 1