시간 제한과 메모리 제한

알고리즘 문제에서 시간 제한, 메모리 제한을 반드시 고려해야합니다, 파이썬으로 문제를 풀 때는 다음과 같은 점들을 고려해야 합니다.

 

1. 시간 복잡도

 

• 시간 제한이 1초라는 것은 대략적으로 1초 내에 실행될 수 있는 연산의 수를 의미합니다.

• 파이썬에서는 일반적으로 초당 약 1억 번(10^8)의 연산을 처리할 수 있다고 추정할 수 있습니다.

• 시간 복잡도에 따라 처리할 수 있는 최대 입력 크기는 다음과 같이 예상할 수 있습니다:

• O(1): 상수 시간, 입력 크기와 상관없이 즉시 처리 가능

• O(log N): 수백만 이상의 입력도 처리 가능

• O(N): 최대 약 10^7 ~ 10^8 크기의 입력을 처리 가능

• O(N log N): 최대 약 10^6 ~ 10^7 크기의 입력을 처리 가능

• O(N^2): 최대 약 10^4 크기의 입력을 처리 가능

• O(2^N): 최대 20 이하의 입력을 처리 가능

• O(N!): 최대 10 이하의 입력을 처리 가능

 

2. 메모리 제한

• 파이썬에서 각 데이터 타입의 메모리 사용량은 다음과 같습니다:

• int: 파이썬의 정수는 무제한 크기이지만, 일반적으로 28바이트를 사용합니다.

• float: 8바이트

• list: 요소의 개수에 비례하여 메모리 사용, 요소 자체의 메모리 사용량에 리스트의 오버헤드가 추가됩니다.

• dictionary: 요소의 개수와 각각의 키와 값의 메모리 사용량에 비례하여 메모리 사용

따라서, 예를 들어 리스트에 10^7개의 정수를 저장하면 대략 280MB 정도의 메모리를 사용하게 됩니다. 예를 들어 메모리제한이 256MB일 경우 제한을 넘어가므로, 이러한 대용량 데이터를 다룰 때는 효율적으로 메모리를 관리해야 합니다.

 

3. 입력과 출력

• 입력 데이터의 크기나 출력을 효율적으로 처리하기 위해 sys.stdin.readline과 같은 방법을 사용하여 I/O를 최적화하는 것도 중요합니다.