졍's 기술 블로그

Python의 시간/메모리 제한

Python 3.7로 Code를 작성할 때 1초에 2,000만 번의 연산을 수행한다고 가정(2020년 기준)

시간 제한	1초
메모리 제한	128 MB
데이터 개수	100만 개

시간 제한이 1초, 데이터 개수가 100만개인 문제가 있다면 일반적으로 시간 복잡도는 이내의 Algorithm을 이용해 문제를 풀어야 한다.
☞ 일 때 이기 때문

1. 구현(Impletmentation)

: 머릿속에 알고 있는 Algorithm을 Code로 바꾸는 과정

☞ 흔히 Algorithm 대회에서의 구현 유형 문제는 풀이를 떠올리는 것은 쉽지만 Code로 옮기기 어려운 문제를 지칭한다.

e.g., 완전 탐색, 시뮬레이션

완전 탐색(Brute Forcing)
: 가능한 모든 경우의 수를 탐색하는 방법

시뮬레이션(Simulation)
: 문제에서 제시한 Algorithm을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

2. 행렬(Matrix)

: 2차원 Data를 일종의 표와 같은 형태로 쉽게 나타내 줄 수 있도록 하는 수학 개념 중 하나 (Programming에서의 2차원 배열, 리스트)

☞ 일반적으로 Algorithm 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용되며 Simulation 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

# 동, 북, 서, 남
dx = [0, -1, 0, 1] # 가로 축(행)
dy = [1, 0, -1, 0] # 세로 축(열)

# 현재 위치
x, y = 2, 2

for i in range(4):
# 다음 위치 -> 동, 북, 서, 남의 방향으로 1번씩 이동
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)​

참고

https://youtu.be/2zjoKjt97vQ​