[알고리즘] 기초 코드 작성 요령

바쁘다는 핑계롤 너무 알고리즘을 대충 공부했다.
결국 풀 수 있는 문제는 바로 풀지만, 못푸는 문제는 그냥 바로 인터넷을 뒤지는 사람이 되어버렸다..
6월 중순 전까지는 기초 개념을 그래도 다잡고 싶다 ㅜㅜ !

---

📌 시간복잡도

컴퓨터가 1초에 처리할 수 있는 연산량: 3-5억개(연산의 종류에 따라 다름)

예시

int func1 (int arr[], int n){
	int cnt = 0;
	for(int i = 0; i ‹ n;i++){
		if (arr [1] & 5 == 0) cnt++;
    }
	return ent;
}

총 연산량은 총 5n + 3이다.

1(cnt 할당) 
+ 2(for 문 내 변수 i 크기 비교 및 수 증가)
+ 2(if 문 내부 나눗셈 진행 및 0과 같은지 비교)
+ 1(cnt 값 증가)
+ 1(마지막 cnt 반환)

그렇다면 n이 100만개라면 연산이 가능하지만,
n이 10억개라면! 연산이 불가능하다.

그치만 이건 단순히 n에 비례하기 때문에 5n+3 의 시간 복잡도를 지닌다 가 아닌 ✨n의 시간복잡도를 지닌다✨ 고 하는 것이 맞다!

📝 log(N) (밑이 2인)

들을때마다 헷갈렸던 개념이다.
수학공부를 열심히 했다고 생각했지만 로그의 시간복잡도를 지닌다고 하니 머리가 아팠던 경험이 많다.
(그치만 알아볼 생각도 안했던 나.. 반성해)

이분탐색과 같은 문제에서 로그의 시간 복잡도를 지닌다고 한다.

log16 = 4이다. 한마디로! 16을 2로 계속 쪼개면 결국 4번 쪼개게 된다는 것이다.
따라서 16명의 사람이 순번을 부여받고 순서대로 서 있을때, 내가 원하는 사람을 찾는다면 최악의 경우 log16만큼의 시간이 걸린다.
(순서대로 서있으니 내가 찾는 사람이 이 사람보다 앞에 있는지, 뒤에있는지 정도는 알 수 있다. 따라서 중간부터 조사하는게 이득)

시간복잡도(Time Complexity)

입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관관계
➡️ 빅오표기법을 통해 나타낸다.

N의 크기	허용 시간복잡도
N <= 11	O($N!$)
N <= 25	O($2^N$)
N <= 100	O($N^4$)
N <= 500	O($N^3$)
N <= 3000	O($N^2logN$)
N <= 5000	O($N^2$)
N <= 백만	O($NlogN$)
N <= 천만	O($N$)
그 이상	O($logN$), O(1)

---

출처

바킹독의 실전 알고리즘