2021.04.01 오늘의 기록

파이썬 알고리즘 인터뷰 - 박상길

• 파이썬의 리스트는 c++의 vector나, 자바의 ArrayList처럼 동적 배열을 구현한 자료형이다.
• 파이썬 리스트를 사용하면 스택을 사용할지, 큐를 사용할지 고민하지 않아도 되며, 스택과 큐에서 사용 가능한 모든 연산을 함께 제공한다.
• 리스트에 주로 큐의 연산을 사용할 때는 시간 복잡도가 증가할 수 있음으로, 주의해야 한다.

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

len(a)	O(1)	전체 요소의 개수를 리턴
a[i]	O(1)	인덱스 i의 요소를 가져온다
a[i:j]	O(k)	i부터 j까지 슬라이스의 길이만큼인 k개의 요소를 가져옴. 이 경우 객체 k개에 대한 조회가 필요하기 때문에 O(k)가 된다
elem in a	O(n)	elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다
a.count(elem)	O(n)	elem 요소의 개수를 리턴한다
a.index(elem)	O(n)	elem 요소의 인덱스를 리턴한다
a.append(elem)	O(1)	리스트 마지막에 elem 요소를 추가한다
a.pop()	O(1)	리스트 마지막 요소를 추출한다. 스택의 연산이다.
a.pop(0)	O(n)	리스트 첫 번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 O(n)이다. 큐의 연산을 주로 사용한다면 리스트보다는 O(1)에 가능한 deque를 권장한다.
del a[i]	O(n)	i에 따라 다르다. 최악의 경우 O(n)이다
a.sort()	O(nlogn)	정렬한다. Timsort를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다
min(a), max(a)	O(n)	최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다
a.reverse()	O(n)	뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다

• 파이썬은 모든 것이 객체며, 파이썬의 리스트는 객체에 대한 포인터 목록을 관리하는 형태로 구현되어 있다. 사실상 연결 리스트에 대한 포인터 목록을 배열 형태로 관리하고 있으며, 그 덕분에 파이썬의리스트는 배열과 연결 리스트를 합친 듯이 강력한 기능을 자랑한다.
• defaultdict 객체는 존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다.
• Counter 객체는 아이템에 대한 개수를 계산해 딕셔너리로 리턴한다.
• OrderedDict 객체는 입력 그대로 순서가 유지된다. 그러나 파이썬 3.7 이후 딕셔너리 입력 순서를 유지하기 때문에,기본 딕셔너리만 사용해도 입력 순서가 충분히 유지된다.

---

PyTorch로 시작하는 딥 러닝 입문

• batch는 컴퓨터가 한 번에 처리하는 훈련 데이터의 크기이다. (예를 들어, 3000개의 훈련 데이터가 있는데, 컴퓨터가 여기서 64개씩 꺼내서 처리한다면 batch size는 64가 된다)
• 2D Tensor = (Batch size, dim)
• 3D Tensor 
  비전의 경우: (batch size, width, height) , 이미지는 가로랑 세로니까!
  NLP의 경우: (batch size, length, dim), length는 문장 길이, dim은 단어 벡터의 차원
• numpy에서 .ndim은 몇 차원인지를 출력하고, .shape는 크기를 출력한다.
• 파이토치에서는 크기가 다른 행렬 또는 텐서에 대해서 사칙 연산을 수행해야 할 때, 자동으로 크기를 맞춰서 연산을 수행하도록 하는 브로드캐스팅이라는 기능을 제공한다
• 브로드캐스팅은 자동으로 실행되기 때문에 굉장히 주의해서 사용해야 한다
• 파이토치 텐서의 행렬 곱셈은 matmul()을 통해 수행한다
• element-wise 곱셈은 동일한 크기의 행렬이 동일한 위치에 있는 원소끼리 곱하는 것을 뜻하는 것으로, * 또는 mul()을 통해 수행한다
• 인자로 dim을 준다면 해당 차원을 제거한다는 의미가 된다
• max()는 원소의 최대값을 리턴한다
• max()는 dim 인자를 주면 argmax도 함께 리턴하는 특징이 있다
• ArgMax()는 최대값을 가진 인덱스를 리턴한다