- 파이썬은 1초에 대략 2000만번의 연산이 가능하다고 전제하면 안전하다.
- 대부분 코딩테스트 문제의 제한은 시간제한이 1-5초, 메모리가 128MB-512MB정도 이다.
- 시간제한이 1초인 문제를 만났을경우(대부분) N의 범위가 500이하인경우 O(N^3)으로도 충분히 해결가능하고, 2000이하인 경우, O(N^2)인 알고리즘으로 해결 가능하며 N의 범위가 100,000이하인 경우 O(NlogN)알고리즘으로 해결 가능하고 10,000,000인 경우 O(N)알고리즘으로 해결이 가능하다.
- 경험을 토대로 N이 만단위 이하일 경우 O(N^2)알고리즘으로 충분히 해결 가능하다. 그이상은 O(NlogN)알고리즘을 1순위로 염두해두는게 좋을것 같다.
- 위는 1초가 주어졌을때 추천되는 입력 갯수에따른 알고리즘 설계이다.
- 제일좋은방법은 걸리는 시간을 직접 측정해보는 습관을 가지는것!!!!
- 문제를 풀때마다 위의 코드로 시간을 측정하여 연습하여 대략적인 감을 잡는게 좋지만,,입력의 갯수가 비약적으로 커질때마다 테스트케이스를 일일이 입력하고 있을 시간이 없을것 같기 때문에 문제를 접근하기전에 눈대중으로 메모리와 시간을 고려한 알고리즘을 생각하고 접근하는 연습을하자!
- 위는 int자료형의 원소 갯수만큼 차지하는 메모리 사용량이다.
- 파이썬에서는 메모리 사용량을 꼭 생각해주는게 좋다.
- 파이썬에서 temp=[i for i in range(100000)]이라는 코드가 있다고 가정해보자, 매 for문마다 temp=[동일한 사이즈의 다른 원소]라는 작업을 하게되면, gc에의해 기존에 잡아먹고있던 메모리공간은 버려지고 동일한 사이즈의 다른 공간이 재할당 되게 된다. 즉, 메모리 사용량은 동일하지만, 시간이 더 걸릴수 있다.(시간이 널널하면 단순히 이런식으로 계산해도 무방하다.)
- 메모리를 효율적으로 관리하는 방법으로는 슬라이딩 윈도우기법이 있다.
- 핵심개념은 더이상 필요하지않은 값을 담고있는 저장공간을 갱신시켜나간다는 것이다.
- 무의식중에 사용하고 있을가능성이 높음
- hellominchan.tistory.com/256<<sliding window기법에 대하여 잘 설명해주는것 같다.
- 즉 메모리가 어떻게 사용지에 대한 개념이 확실하면 시간도 줄일수 있다.
'프로그래밍 언어별 tools > 파이썬' 카테고리의 다른 글
| [Python] 알파벳 자동 생성 방법(리스트, 딕셔너리 등) (0) | 2022.08.15 |
|---|---|
| 딕셔너리 (0) | 2022.04.15 |
| 구분자 여러개로 string to list (0) | 2022.04.14 |
| f-string (0) | 2022.04.14 |
| heapq모듈에 있는 nlargeest(), nsmallest() 함수 (0) | 2021.11.19 |