책에 대하여

• 소스 코드: https://github.com/onlybooks/python-algorithm-interview

• leetcode 풀이집이라고 볼 수 있다. 이 책의 큰 장점은, 실행 시간을 기준으로 문제마다 여러가지 풀이를 제공한다는 점이다.

• leetcode의 장점
  
  leetcode에서는 내 풀이의 runtime, memory별 %를 제공하고, 각 구역별 다른사람 풀이를 볼 수 있다.

• 고난이도 문제를 위한 책은 아니다. 대신, 코딩테스트 준비를 시작하는 단계에서 큰 도움을 줄 책이다. 🎇

---

1장 코딩 인터뷰

🔷 코딩 테스트의 사전 준비사항
1. 연습장과 필기도구
2. 어떤 프로그래밍 언어가 유리할까
3. 자신만의 코드 스니펫(snippet) 준비: 코드 스니펫 관리 추천: https://gist.github.com/
4. 모든 테스트 케이스를 통과하도록 풀어야 한다.
5. 타임 아웃이 발생하는 경우: $O(n^2)$은 거의 발생. $O(n)$ 또는 $O(nlogn)$는 되어야 한다. 파이썬은 특히 알고리즘 최적화에 좀 더 많은 고민이 필요.
6. 예외 처리를 잊지 말자: 가장 실수하기 쉬운 부분
7. 잘못 접근한 풀이, 어떻게 대처할까: 문제당 제한 시간을 정해두고 그 시간을 초과할 경우 바로바로 다음 문제로 넘어가자.
8. 풀이 시간을 초과했을 때, 포기해야 할까: 채용을 위한 코딩 테스트이며, 면접관의 이메일 주소를 아는 경우, 메일로 제출하는 것도 좋은 방법이다.
9. 코딩 도구가 필요할까: yes
10. REPL 도구로 코드 검증: read-eval(uate)-print-loop약어. 사용자 입력에 대한 실행 결과를 바로 되돌려 주는 상호작용 환경.

5장 빅오(big-O)

입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법

🔷 점근적인 실행 시간(Asymptotic Running TIme)를 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나
- 점근적 실행 시간: 입력값 n이 커질 때, $lim_{x \to \infty}$ 함수의 실행 시간의 추이
🔷 시간 복잡도(Time Complexity): 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)
- 빅오: 계산 복잡도를 표현하는 대표적인 방법.
- 표현할 때는 최고차항만을 표기한다.
$ex)$ $4n^2+3n+4$번만큼 계산하는 함수가 있다면, 최고차항의 $n^2$만을 고려. 시간 복잡도는 O($n^2$)이 된다.

🔷빅오 표기법의 종류

빅오 표기법	설명
$O(1)$	입력값이 커도 실행 시간이 일정. 최고의 알고리즘. ex) 해시테이블의 조회 및 삽입
$O(logn)$	입력값에 영향. 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편. ex) 이진 검색
$O(n)$	입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례. 선형 시간 알고리즘이라고 한다.(Linear_time). ex) 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우. 모든 입력값을 적어도 한 번 이상 보는 경우.
$O(nlogn)$	효율 좋은 정렬 알고리즘. ex)병합 정렬적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 $O(nlogn)$보다 빠를 수 없다. 입력값이 최선인 경우, 비교를 건너뛰어 $O(n)$이 될 수 있다. ex) Timsort(수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘)
$O(n^2)$	버블 정렬과 같은 비효율적인 정렬 알고리즘
$O(2^n)$	피보나치 수를 재괴로 계산하는 알고리즘
$O(n!)$	각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때(Travelling Salesman Problem). 가장 느린 알고리즘, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다.

🔹 시간과 공간이 트레이드오프(Space-Time Tradeoff)관계. 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.

🔷 상한과 최악

• 빅오($O$) = 상한(Upper Bound)
• 빅오메가($\Omega$) = 하한(Lower Bound)
• 빅세타($\theta$) = 평균
• 업계에서는 빅세타와 빅오를 하나로 합쳐 단순화해서 표현하려는 경향.

🔷 리스트의 주요 연산 시간 복잡도

연산	시간 복잡도	설명
len(a)	$O(1)$
a[i]	$O(1)$
a[i:j]	$O(k)$	객체$k$에 대한 조회가 필요함
elem in a	$O(n)$	순차탐색
a.count()	$O(n)$
a.index()	$O(n)$
a.append()	$O(1)$	리스트 마지막에 요소 추가
a.pop()	$O(1)$	리스트 마지막 요소 추출
a.pop(0)	$O(n)$	리스트의 첫번째 요소를 추출하므로, que연산이다. 이 경우 전체 복사가 필요하여 $O(n)$
del a[i]	$O(n)$	i에 따라 다름. 최악은 O(n)$
a.sort()	$O(nlogn)$	정렬. Timsort. 최선의 경우 O(n)에도 실행될 수 있다.
min(a), max(a)	$O(n)$	전체 선형 탐색
a.reserve()	$O(n)$

🔷 딕셔너리의 주요 연산 시간 복잡도

연산	시간 복잡도	설명
len(a)	$O(1)$
a[key]	$O(1)$
a[key] = value	$O(1)$	키/값 삽입
key in a	$O(1)$	딕셔너리에 존재하는 지 확인

🔹대부분 연산이 $O(1)$

6장 정렬 알고리즘과 팀소트

1. 병합 정렬: 존 폰 노이만이 설계한 병합 정렬(Merge Sort)

• 컴퓨터과학 역사상 최고의 천재라 일컬어지는 그 사람 🤔
• 일정하게 $O(nlogn)$의 안정적인 성능
• stable sort

2. Tim Peaters interview
   https://youtu.be/1wAOy88WxmY?si=Gz33Zf8pdKjLX0BY

• Peter Mcllroy의 1993년 논문을 기반으로 2002년도에 파이썬을 위해 C 로 구현한 알고리즘.
• '실제 데이터는 대부분 이미 정렬되어 있을 것이다.' 라고 가정.
• 고성능을 낼 수 있도록 설계된 알고리즘
• 개별적인 단일 알고리즘이 아닌, 삽입 정렬과 병합 정렬을 적절히 조합해 사용

2. About Timsort
   https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399

9장 선형 자료 구조

자료구조는 메모리 공간 기반의 연속(Contiguous) 방식과 포인터 기반의 연결(link) 방식으로 나뉜다.
배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다.
연결 방식의 가장 기본이 되는 자료형은 연결 리스트다.
추상 자료형 ADT의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다.