✅ 한 것들

---

• 코딩 인터뷰 완전 분석
• Project FDS

📖 코딩 인터뷰 완전 분석

---

VI big-O

파일 전송

• 온라인 전송 : O(s)
• 비행기로 전송 : O(1)
• 선형식은 언젠가 상수를 뛰어넘는다.

시간 복잡도

big-O, big-theta, big-omega

O(big-O)

• 학술적으로 실행 시간의 상한을 의미함
• O(N)으로 표현되는 알고리즘은 O(N^2), O(N^3)로도 표현 가능.

O(big-Omega)

• 알고리즘의 실행 시간 하한을 의미
• Omega(1)이면 전체 순회는 반드시 하게 된다는 뜻

O(big theta)

• big-O랑 big-Omega랑 같을 때
  업계의 big-O는 사실 학계의 big theta와 같은 의미

최선, 최악, 평균

최선의 경우는 아무 알고리즘이나 취한 뒤 특수한 입력을 넣으면 O(1)이다.
대부분의 알고리즘은 최악과 평균이 같다.

공간 복잡도

재귀 스택 공간도 공간 복잡도에 포함된다.
꼬리 재귀 최적화하면 안 늘어남.

상수항은 무시하라

O(2N)이 O(N)보다 빠를 수도 있다.
for문 안에 식 두 개 적으면 O(N),
for문을 따로 적으면 O(2N)이다.
둘 중 뭐가 더 빠를까? 고려할 세부사항이 너무 많다.

지배적이지 않은 항은 무시하라

O(X!) > O(2*x) > O(x^2)

상환 시간

Java의 ArrayList, C++의 vector 등의 동적 배열은 꽉 차면 크기를 늘린다.
이것까지 감안할 때 삽입 연산의 수행 시간은?

배열의 크기가 1,2,4,8,16 ... X 일 때
새 원소 삽입하면 배열의 크기를 두배로 증가시킨다.
원소들을 새 배열로 복사시켜줘야 한다
기존 원소 크기 1+2+4+...+X = 대략 2X
X로 분할 상환해보면 삽입에 필요한 시간은 O(1)

log N 수행 시간

어떤 문제에서 원소 개수가 절반씩 줄어들면 O(logN) 가능성 크다
big-O에선 로그의 밑을 고려할 필요 없다.

재귀적으로 수행 시간 구하기

재귀가 자신을 재호출하는 횟수를 A라 하고
호출 깊이를 B라 하면
이 재귀 함수의 수행 시간은 보통 A^B으로 표현된다

예제 및 연습 문제

O(AB)와 O(N^2) 혼동 조심

void printUnorderedParis(int[] arrA, int[] arrB {
	for(int i=0; i<arrA.length; i++) {
		for(int j=0; j< arrB.length; j++) {
			if(arrA[i] < arrB[j]) {
				if(arrA[i] < arrB[j]) // 뭔가 함
			}
		}
	}
}

이건 O(N^2)이 아니라 O(AB)이다

N 혼용 조심

문자열 배열이 주어졌다.
각각의 문자열을 정렬한 뒤,
전체 문자열을 사전순으로 정렬한다.
수행 시간은?

문자열 정렬이 O(NlogN)이고
그게 배열만큼 있으니까 O(N^2logN)
다시 정렬하면 O(NlogN + N^2logN)
라고 하면 틀린다

문자열 길이 S와 배열 길이 A를 혼동했기 때문
실제로는 문자열 정렬은 O(SlogS),
그걸 배열만큼 반복하면 O(ASlogS),
다시 정렬하면 O(AS(logA + logS)가 된다.
(배열에 대해 정렬할 때 문자열 비교 때문에 그냥 AlogA가 아니라 SAlogA)

변수 이름 붙일 때도 A,B,M,N 이런거 쓰지 말고
안 헷갈리게 연상 가능한 이름을 붙여라

🎮 Project FDS

---

스크립트 이름 변경, 컨벤션 수정, 폴더 정리