시간복잡도 & 공간복잡도

60~88P

• 보통 시간복잡도를 표현할 때 빅O가 많이 사용되나 O(상한), Omega(하한), Theta(평균)도 존재한다.
• 재귀 함수의 경우 일반적으로 O(분기^깊이)로 표현할 수 있다. 대표적으로 메모이제이션이 없는 피보나치는 O(2^n) 이다. 또한 재귀의 공간 복잡도는 O(깊이) 만큼 가져간다. 특정 시간당 잡아먹는 메모리는 제한적이므로 시간복잡도와 헷갈리지 말자.
• 보통 동적 배열은 배열 크기가 초과되면 Growth Factor만큼 복사를 하게 되는데, 배열 복사는 O(n)의 시간복잡도를 가진다. 루프문으로 일일히 값을 넣어줘야 하기 때문임

코딩 테스트 진행하는 방식

1. 듣기

   문제를 잘 듣고 어떤 알고리즘을 사용할지 파악하라.

2. 예제

   Test Case를 더 복잡하게 해서 늘려보기 (큰 크기의 테스트 케이스도 만들어보자)

3. 무식하게 풀기

   Brute Force로 먼저 접근한 후 사고를 확장하는 것을 추천함

4. 최적화

   BUD(병목현상, 불필요한 작업, 중복되는 작업) 최적화를 해서 개선하기 특히 시간과 공간 복잡도 비용을 계산해보는 습관을 들이는 게 좋다 (해시테이블 짱)

5. 검토

   최적화를 통해 해법을 찾았다면, 마지막 검토하기

6. 구현하기

   코드를 모듈화하면서 아름답게 코드 짜보기

7. 테스트

   개념적 테스트(그냥 읽어보기) → 엣지 케이스

기술면접

1. 배열과 문자열

특정 값을 찾을 때 유용한 방법으로 해시테이블이 있다.

• 해시테이블에서는 충돌 최소화로 구현하면 탐색시간은 O(1)이다.
• 해싱 → 배열 사이즈로 나누기 → 중복될 경우 Seperate Chaining이나 Open Addressing 사용하기 .