📕 기본

1. 리스트
   리스트의 사이즈: len(list)
   리스트 정렬: list.sort()

2. 공백으로 숫자 or 문자 입력받기

 arr = list(map(int,input().split()))

3. 리스트의 인덱스를 참조하여 for문 실행

for i in range(len(list))

4. [ [0] * n for _ in range(m) ] 과 [ [0] * n ] * m 의 차이
   전자는 배열 안에 2차원 배열을 선언한다.
   후자는 배열 안에 배열들을 선언하는 게 아니라 각 배열들을 선언한다.
   예시)

a = [[0] * 2] * 3
b = [[0] * 2 for _ in range(3)]

a[0][0] = 1
b[0][0] = 1

print(a)
print(b)

# 출력
[[1, 0], [1, 0], [1, 0]]
[[1, 0], [0, 0], [0, 0]]

📑 자료구조

1. 스택
   파이썬의 경우 스택 자료구조를 따로 제공하지는 않는다.
   따라서 list를 이용한다.
   stack의 생성과 push, pop은 다음과 같이 구현한다.
   stack의 top은 stack[-1]이다.

stack = []
stack.append(1)
stack.pop()

2. 큐
   큐는 라이브러리를 제공한다.

from collections import deque

c++에서 STL을 추가하듯이, 파이썬도 collections 모듈로부터 큐를 불러와야 한다.
사용하는 방법은 다음과 같다.

queue = deque([1, 2])
queue.append(3)
queue.popleft() -> 1이 반환된다.

3. heap
   우선순위 큐를 구현할 때 사용하는 힙이다.

import heapq
heapq.heappush(q, (start, 0))
heapq.heappop(q)

🧱 알고리즘

1. 에라토스테네스의 체
   소수를 구할 때, 시간초과 문제를 해결하기 위해 효과적이다. 기원전 200년대부터 쓴 검증된 로직이다.
   

n = 1000001 // 1부터 n인덱스까지 나타냄
prime_list = [True] * n // 일단 True로 박아둔다. 
화이트리스트방식이라고 할수있음
prime_list[1] = False // 1은 소수가 아님
m = int(n ** 0.5) // sqrt(n)
for i in range(2, m + 1): //2부터 m까지
  if prime_list[i] == True: 
    for j in range(2 * i, n, i):
    	//소수의 배수를 싹다 False 처리,
        range함수의 3번째 인자는 늘어나는 수를 뜻함.
        prime_list[j] = False

⏰ 시간초과에 대하여

1. 보통 1초에 10억 정도의 연산을 수행할 수 있다.
2. 10만개 이상 input을 받으면 시간초과가 난다. 이럴 때 사용할 수 있는 방법은 이분탐색 등이 있다.