1. 시간 복잡도와 공간 복잡도의 정의와 차이를 설명해보세요.
시간 복잡도는 알고리즘이 실행되는 동안 수행하는 연산 횟수의 총량을 나타내고, 공간 복잡도는 알고리즘이 실행되는 동안 필요한 추가 메모리의 양을 나타낸 것입니다. 즉, 얼마나 빨리 실행 되는 지, 얼마나 많은 메모리를 쓰는지의 차이입니다.
2. Big-O 표기법이 무엇이고 왜 쓰나요?
빅오 표기법은 복잡도를 표기하는 표기법입니다. 구현 환경이나 상수에 상관없이 알고리즘의 성능을 비교할 수 있기 때문에 주로 사용합니다.
3. Big-O, Big-Theta, Big-Omega의 차이를 설명해보세요.
Big-O는 알고리즘의 최악의 경우 얼마나 느려질 수 있는지는 나타내며, 상한선을 의미합니다.
Big-Omega는 반대로 최선의 경우 얼마나 빠를 수 있는지를 나타내며, 하한선을 의미합니다.
Big-Theta는 평균적인 성장률을 의미합니다
👉왜 빅오는 최악 기준으로 많이 쓰나요?
→ 실무에서는 성능을 보장해야 하기 때문에 최악의 경우를 기준으로 설명하는 것이 안전합니다.
4. 복잡도의 예시를 들어보세요.
- O(1): 배열 인덱스 접근, 해시맵 조회
- O(n): 배열 전체 순회, 연결 리스트 탐색(선형 탐색)
- O(log n): 이진 탐색, 균형 BST 탐색
- O(n²) : 버블/삽입/선택 정렬
- O(2ⁿ) : 부분 집합 구하기, 피보나치 수열(재귀)
- O(n log n): 병합 정렬, 힙 정렬, 퀵 정렬(평균)
👉해시맵은 평균 O(1)인데 왜 최악은 O(n)인가요?
→ 해시맵 충돌이 모두 같은 버킷에 몰리면 연결리스트 탐색이 필요하기 때문입니다.
연결리스트 탐색은 복잡도가 O(n)이므로 해시맵의 최악은 O(n)입니다.
5. 공간 복잡도가 O(1)과 O(n)의 차이를 예시로 설명해보세요.
- 팩토리얼을 예시로 들 수 있습니다.
반복문으로 구현한 팩토리얼은 입력 크기가 커져도 변수 갯수가 변하지 않으므로 추가메모리가 필요하지 않습니다. 따라서 공간 복잡도는 O(1)입니다.
재귀로 구현한 팩토리얼은 함수를 호출할 때마다 호출 스택에 새로운 프레임이 쌓이며, 깊이가 N이라면 스택프레임도 N개 생기므로 공간 복잡도는 O(n)입니다.
6. 선형 탐색과 이진 탐색의 시간 복잡도는?
- 선형 탐색은 O(n), 이진 탐색은 O(log n)입니다. 이진탐색은 정렬된 자료 구조에서만 가능합니다.
7. 재귀 vs 반복 (시간/공간 복잡도)
- 시간복잡도 : 반복문 팩토리얼과 재귀 팩토리얼 둘다 O(n)이므로 같습니다.
- 공간 복잡도 : 재귀는 호출할때마다 스택을 사용하여 O(n)이고, 반복문은 O(1)입니다.
- 실무 작용 : 입력 크기가 크다면 스택 오버플로우 방지를 위해 반복문을 사용하는것이 안전합니다.
👉재귀는 반복문보다 불리한데 왜 씁니까?
→ 코드가 간결하고 문제 구조를 직관적으로 표현할 수 있다는 장점이 있어 사용합니다.
8. 정렬 알고리즘 중 평균적으로 O(n log n)을 보장하는 것은 어떤 것들이 있나
요?
- 병합 정렬, 힙정렬, 퀵 정렬, 팀소트가 있습니다.
👉 왜 퀵 정렬은 평균 O(n log n)인데 최악은 O(n²)인가요?
→ 분할이 불균형하게 일어나면 재귀 깊이가 n까지 가므로 O(n²)까지 가게됩니다.
9. 공간 복잡도 최적화를 위해 어떤 기법들을 사용할 수 있나요?
- 투포인터 : 배열에서 양쪽끝에서 움직이면서 문제를 해결하는 방식 -> 중복 순회 제거, 메모리 절약
- In-place 알고리즘 : 새로운 배열을 만들지 않고 원래 자료구조 안에서만 값 교환/처리 -> 퀵 정렬, 제자리 뒤집기
